Нахождение угла, который находится в большинстве интервалов углов

Question

Нахождение угла, который находится в большинстве интервалов углов

У меня есть угловые интервалы (в радианах) [0,2π)

например, интервалы [(2π) / 3, (3π) / 4], [π / 2, π] и т. д.
но также может быть интервал [(3π) / 2, π / 3]

Я должен найти угол, который расположен в большинстве интервалов.
Какой лучший способ найти его в C ++?
Как я могу представить угловые интервалы?

2

algorithm angle c++implementation intervals

Решение

Другие решения

Вы могли бы реализовать простой алгоритм стреловидности Для решения этой проблемы.

Для каждого интервала добавьте начало и конец интервала к вектору; отсортировать этот вектор, а затем повторить его. Если у вас есть какие-либо интервалы, которые пересекают 2π-границу, просто разбейте ее на два интервала, которые находятся внутри (0, 2π).

Выполняя итерацию по списку, следите за тем, сколько перекрывающих итервалов существует в текущей точке, и каким был наилучший угол, который вы видели до сих пор (и сколько интервалов перекрывались под этим углом). Как только вы дойдете до конца, вы узнаете, каков оптимальный угол.

Если вам нужно более одного угла, вы можете довольно легко адаптировать этот подход для запоминания интервалов с максимальным перекрытием, а не отдельных углов.

4

Мое решение будет включать в себя список пар начала интервала и сколько интервалов перекрывают его:

     1        2       3       2              1
|---------|--------|-----|---------------|------|

|------------------|
|--------------|
|---------------------|
|----------------------------|

Итак, отсортируйте все начальную и конечную точки и просмотрите список, назначая каждому новому интервалу количество интервалов, с которыми он перекрывается (увеличивая его, если это начальная точка, уменьшая в противном случае). Затем возьмите максимум из подсчета перекрытия.

1

Я думаю, что вы столкнетесь со странными крайними случаями, если не сделаете это символически.

Ваши угловые диапазоны не только не точно представлены в виде двоичных дробей (с ошибками округления), но иррациональны. (Pi больше 3,14159265359, но меньше 3,14159265360; как вы говорите, что угол равен Pi/ 2 к тому же символически?)

Самый надежный способ сделать это — поочередно взять все комбинации интервалов, определить их пересечение и посмотреть, какие из этих комбинированных интервалов являются результатом пересечения самых отдельных интервалов.

Это также дает вам бонус не только один, но все из углов, которые удовлетворяют вашему состоянию.

0

Источник

Accepted Answer

Я бы сделал это, поддерживая разбиение [0, 2π] на диапазоны, соответствующие интервалу покрытия, с подсчетом для каждого диапазона. Во-первых, вот как алгоритм будет работать при условии, что ни один из интервалов не пересекает 0 (или 2π). Также предполагается, что интервалы нормализованы следующим образом: если интервал заканчивается в 0, он меняется на конец в 2π; если он начинается с 2π, он меняется на 0.

создать список пар (диапазон, количество), инициализированных одним диапазоном [0, 2π] и счетчиком 0. (Список будет упорядочен по началу диапазона. Диапазоны в списке будут перекрываться только при их конечные точки и всегда будут покрывать [0, 2π]).
обрабатывать каждый интервал, как описано ниже
отсканируйте список для пары (диапазон, количество) с наибольшим количеством. Разрешите связи произвольно. Вернуть произвольный угол в пределах диапазона.

Обработать интервал i:

Найдите первую (диапазон, количество) пару (назовите ее) s) для которого i.start >= s.range.start (т.е. диапазон содержит i.start). (Обратите внимание, что если i.start это конец одного диапазона, тогда это будет начало другого; это выбрать пару, для которой это начало.)
Найти последнюю пару (диапазон, количество) e для которого i.end <= e.range.end, (Обратите внимание, что если i.end это начало одного диапазона, тогда это будет конец другого; это выбирает пару, для которой это конец.)
Если i.start > s.range.start (i.range начинается в интерьере s), Трещина s на две пары (диапазон, количество) s1 = ([s.range.start, i.start], s.count) а также s2 = ([i.start, s.range.end], s.count), замещать s в списке с s1 а также s2 (в этой последовательности).
Если i.end < e.range.endзаменить e параллельно предыдущему шагу, используя i.end сделать раскол.
Для каждой пары из s (или же s2 если s был разделен на шаге 3) до e (или же e1 если e был разделен на шаге 4), добавьте 1 к счету.

Если вам не нужно отслеживать фактическое количество интервалов, которые содержат определенный угол, только то, что это максимум, ведение учета для интервалов, которые пересекают 0 (или 2π), проще: просто возьмите дополнение к интервалу (обратный начало и конец) и вычтите одно из чисел в шаге 5 вместо сложения. Если вам нужны абсолютные значения, выполните трюк с дополнением и добавьте 1 к каждому счету в списке.

Вышеупомянутое не будет правильно работать с интервалами, которые упираются (например: [0, π / 3] и [π / 3, π]; или [2π / 3, 2π] и [0, 1]). В тех случаях, насколько я понимаю, угол, под которым они примыкают (π / 3 или 0), следует считать находящимся в двух интервалах. Приведенный выше алгоритм можно настроить так, чтобы, когда начало интервала совпадает с конечной точкой диапазона, новая пара (диапазон, число) вставляется после рассматриваемой пары; новая пара будет иметь диапазон одного угла (то есть range.start == range.end). Аналогичная процедура будет применяться для диапазона, который начинается в конце интервала. Я думаю, что с этими настройками вышеуказанный алгоритм корректно обрабатывает все случаи.

1