Как правильно сравнивать диапазоны углов?

Question

[Сергей Соколов]

Даны два сектора: от угла A1 радиан до угла A2 радиан, и от угла B1 рад. до B2 рад.
Надо определить, есть ли у них пересечения.

Как это решить правильно-красиво?

Что-то забуксовал с неопределённостями, когда угол может быть задан и как 7 * PI / 4, и он же как -PI / 4.

иллюстрация

Заданы углы от оси X к лучам OA, OB, OC и OD.
Интересует, пересекаются ли диапазоны AOB и COD.

Для однозначности можно считать каждый диапазон заданным углом его биссектрисы и полу-шириной.

Как «правильно» нормализовать значения?

Answer 1

[Taus]

Одно из решений. Пусть сектор A описывается упорядоченной парой {A1,A2}, т.е. сектором считается область получающаяся при обходе окружности по часовой стрелке от точки А1 до точки А2.
1. Привести значения всех углов к диапазону от [0, 2pi).
2. Если A1 > A2, то разобъём сектор на два: S1 = [A1, 2pi) U [0, A2].
3. С помощью алгебры множеств и алгоритма пересечения обычных отрезков можно найти пересечение:
[A1, A2] ∩ [B1, B2] - обычный алгоритм
( [A1, 2pi) U [0, A2] ) ∩ [B1, B2] = ( [B1, B2] ∩ [A1, 2pi) ) U ( [B1, B2] ∩ [0, A2] ) - для каждого из пересечений обычный алгоритм
( [A1, 2pi) U [0, A2] ) ∩ ( [B1, 2pi) U [0, B2] ) - очевидно, что пересекаются как минимум в точке 0

Answer 2

[Zolg]

Что-то забуксовал с неопределённостями, когда угол может быть задан и как 7 * PI / 4, и он же как -PI / 4

Самый простой способ избежать буксование с неопределенностями - нормализовывать входные значения и дальше работать с чистой арифметикой

Comments

[Taus]

Этого будет мало, потому что секторы могут пересекаться 2 раза.

[Zolg]

Taus, что вы имеете в виду ?

[Taus]

Всё в градусах, у секторов [135, 315] и [270;180] пересечением будет [135;180]+[270;315]. Какую нормализацию надо использовать, чтобы работать с арифметикой (как я понимаю, с обычными отрезками)?

[Zolg]

Нормализацию угла к [0;2*pi), чтобы убрать лишние полные обороты.
Отдельно обработать случай, когда углы начала и конца сектора в нормализованом виде равны, а в исходном - нет (=> сектор равен полной окружности => пересечения есть по определению)
плюс, вычисляя угол между лучами помнить, что он [0; pi]

для простоты сразу считаем

каждый диапазон заданным углом его биссектрисы и полу-шириной

(из углов A1, A2, B1,B2 вычисляется элементарно)

находим угол между биссектрисами
если сумма полуширин больше угла между биссектрисами, сектора пересекаются. если нет - не пересекаются

в вашем примере углы биссектрис 225 и 45, полуширины 90 и 135
угол между биссектрисами - 180, сумма полуширин - 225