Тестирование для пересечения между двумя дугами

Question

У меня есть две дуги, определяемые объектами, содержащими их начальный и конечный углы, их центры и их радиусы.

определение выглядит следующим образом:

arc = { 
    start: 0, 
    end: Math.PI, 
    radius: 10, 
    centre: [0, 0] 
} 

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

Как проверить, пересекаются ли две дуги? (Для чего это стоит, я использую JavaScript, но любой язык будет работать как ответ)

Answer 1

Ну, это немного старый, но ему нужен ответ. Но, во-первых, структура дуги не имеет достаточной информации для работы с вопросом так, как она была заявлена. Нет ничего, что говорит о том, что дуга проходит больше, чем 2pi радианов и сколько раз вокруг. Если бы это было так, идея дуги более 2pi геометрически абсурдна в любом случае, и этой возможности следует избегать. Если вы хотите написать много кода для обработки негеометрических понятий здесь, это выходит за рамки того, что я адресую, и вам решать включить больше данных в структуру и проверить ее правильно. Также нет ничего, что говорит нам, если дуга определена как всегда по часовой стрелке, против часовой стрелки. Но проблему легко решить, если направление четко определено. Пока давайте сделаем предположение, что дуги нулевой длины никогда не используются и что дуги никогда не обходят больше, чем 2pi радианов. Предположим также, что дуги всегда задаются по часовой стрелке.

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

Получить угол точки пересечения. Если угол начала дуги меньше, чем конечный угол, то просто проверьте, не находится ли угол пересечения с этими двумя углами или между ними. Но если начальный угол больше, чем конечный угол дуги, то выполните два теста: один, чтобы увидеть, находится ли угол пересечения на уровне или выше угла начала, а также на уровне или ниже 2pi радианов, а также, если необходимо, проверить, если угол пересечения находится на уровне нуля или выше нуля и ниже или ниже угла конца дуги.

Я думаю, что псевдо-код будет выглядеть примерно так:

on_arc = false; 
if(start > end) 
{ 
    if(intersect >= start && intersect <= 2pi) 
     on_arc = true; 
    else if(intersect >= 0 && intersect <= end) 
     on_arc = true; 
} 
else if(start == end) 
    on_arc = true; // arc is the entire circle since we are not handling zero length arcs. 
else 
{ 
    if(intersect >= start && intersect <= end) 
     on_arc = true; 
} 

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

Просто избегайте идеи дуги> 2pi, потому что это не полезно. Независимо от того, что вычисляет дуга, это либо своего рода геометрическая 2D-концепция, либо это то, что может иметь ограничение в 2pi.

Answer 2

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

Выяснить, как рассчитать один или два круга мест, накладываются друг на друга, а затем выяснять, существует ли одна точка внутри обеих дуг.

Для последней части я нормализую диапазон, чтобы start находился между (-pi, pi] (тот же диапазон возврата, что и atan2()).

while (start > M_PI) { start -= 2 * M_PI, end -= 2 * M_PI ; } 

Затем с помощью atan2() найти угол, что точка пересечения падает в пределах круга, и испытание, что она находится между start и end.

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