Пересечение между двумя дугами?(дуга = расстояние между парой углов)

Question

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

Edit: Я сожалею, что предыдущая иллюстрация была предоставлена, когда моя голова была слишком тяжелой после хрустящих углов Я попробую объяснить еще раз:

В по этой ссылке вы можете видеть, что я разрезал дугу в середине на две половины, правая часть дуги содержит 135 градусов, а левая часть имеет 90 градусов.

Эта Дуга начинается в -180 и заканчивается в 45. (или начинается в 180 и заканчивается в 405, если нормализовано).

Мне удалось создать этот код, чтобы вычислить количество градусов дуги, содержащихся в правой части и в левой части:

f1 = (angle2>270.0f?270.0f:angle2) - (angle1<90.0f?90.0f:angle1);
if (f1 < 0.0f) f1 = 0.0f;
f2 = (angle2>640.0f?640.0f:angle2) - (angle1<450.0f?450.0f:angle1);
if (f2 < 0.0f) f2 = 0.0f;
f3 = (angle2>90.0f?90.0f:angle2) - angle1;
if (f3<0.0f) f3=0.0f;
f4 = (angle2>450.0f?450.0f:angle2) - (angle1<270.0f?270.0f:angle1); 
if (f4<0.0f) f4=0.0f;

Он прекрасно работает после нормализации углов, чтобы быть неотрицательным, но, конечно, начиная с 360 градусов. Тогда f1 + f2 дает мне сумму левой половины, а f3 + f4 дает мне сумму правой половины. Он также не учитывает случай, когда дуга определена как более 360, что может быть ошибкой.

НО, это выглядит скорее как «обходной путь», а не как правильное математическое решение. Я ищу более элегантное решение, которое должно основываться на "пересечении" между двумя дугами (потому что у математики нет "сторон", она не визуальная ";

Спасибо !!

Answer 1

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

Сначала «нормализуйте» свои дуги, то есть уменьшите все углы в них, чтобы они лежали в [0,360), поэтому уберите кратные 360 градусов и сделайте все углы + ve. Убедитесь, что угол остановки каждой дуги лежит по часовой стрелке от начального угла.

Далее выберите начальный угол одной из ваших дуг, не важно, какая именно. Сортируйте все ваши углы (4 из них) в числовом порядке. Если любой из углов численно меньше выбранного начального угла, добавьте к ним 360 градусов.

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

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

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

3) Если это угол остановки другой дуги, то перекрытие включает угол между начальным углом первой дуги и этим углом. Стоп.

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

И смотрите, никакой тригонометрии вообще!

EDIT

Вот более «математический» подход, поскольку вы, похоже, чувствуете необходимость.

Для угла тета в (-pi,pi] функция гиперболического синуса (часто называемая sinh) отображает угол на интервал на реальной линии в интервале (приблизительно) (-11.5,11.5]. В отличие от arcsin и arccos обратная функция этой функции также однозначна в том же интервале. Выполните следующие действия:

1) Если дуга содержит 0, разбейте ее на 2 дуги, (start,0) и (0,stop). Теперь у вас есть 2, 3 или 4 интервала на реальной линии.

2) Вычислить пересечение этих интервалов и преобразовать обратно из линейного измерения в угловое измерение. Теперь у вас есть пересечение двух дуг.

Answer 2

Этот тест можно возобновить с помощью теста в одну строку. Даже если хороший ответ уже опубликован, позвольте мне представить мой.

Предположим, что первая дуга равна A:(a0,a1), а вторая - B:(b0,b1). Я предполагаю, что значения углов уникальны, то есть в диапазоне [0°,360°[, [0,2*pi[ или ]-pi,pi] (сам диапазон не важен, мы увидим, почему). Я возьму диапазон ]-pi,pi] как диапазон всех углов.

---

Чтобы подробно объяснить подход, я спроектировал тест для пересечения интервалов в R . Таким образом, мы имеем здесь a1>=a0 и b1>=b0. Следуя тем же обозначениям для реальных интервалов, я вычисляю следующее количество:

S = (b0-a1)*(b1-a0)

Если S>0, два сегмента не перекрываются, иначе их пересечение не является пустым. Действительно легко понять, почему эта формула работает. Если S>0, у нас есть два случая:

• b0>a1 подразумевает, что b1>a0, поэтому пересечения нет: a0=<a1<b0=<b1.

• b1<a0 означает, что b0<b1, поэтому пересечения нет: b0=<b1<a0=<a1.

Итак, у нас есть единственное математическое выражение, которое хорошо работает в R .

---

Теперь я расширяю его по круговой области ]-pi,pi]. Гипотезы a0<a1 и b0<b1 больше не верны: например, дуга может перейти от pi/2 до -pi/2, это левый полукруг. Поэтому я вычисляю следующее количество:

S = (b0-a1)*(b1-a0)*H(a1-a0)*H(b1-b0)

где H - шаговая функция, определяемая как H(x)=-1 if x<0 else H(x)=1

Опять же, если S>0, между дугами A и B нет пересечения. Есть 16 случаев, которые я хочу исследовать, и я не буду здесь это делать ... но их легко сделать на листе :) .

Замечание : Значение S не важно, только знаки терминов. Прелесть этой формулы в том, что она не зависит от выбранного вами диапазона. Также вы можете переписать его как логический тест:

T := (b0>a1)^(b1>a0)^(a1>=a0)^(b1>=b0)

где ^ является логическим XOR

---

EDIT

Увы, в этой формуле есть очевидный случай отказа ... Поэтому я исправляю это здесь. Я понимаю, что здесь есть случай, когда пересечение двух дуг может быть двумя дугами, например, когда -pi<a0<b1<b0<a1<pi.

Чтобы исправить это, нужно ввести второй тест: если сумма углов больше 2*pi, дуги точно пересекаются.

Таким образом, формула оказывается:

T := (a1+b1-a0-b0+2*pi*((b1<b0)+(a1<a0))<2*pi) | ((b0>a1)^(b1>a0)^(a1>=a0)^(b1>=b0))

Хорошо, это менее элегантно, чем предыдущий, но теперь это правильно.