Столкновение сегмента от круга к кругу

Question

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

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

Я понимаю, как быстро исключать экстремальные случаи, я отбрасываю любые цели, которые не сталкиваются с целым кругом, и любые случаи, когда центр основного круга находится внутри целевого круга, автоматически становятся истинными (E на диаграмме).

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

В частности, это кажется странным, если целевой круг находится близко к центру, но не касается его (где-то между E и B ниже), или если сегмент ужечем целевой круг (чтобы центр находился внутри сегмента, но оба ребра находились за его пределами).

Есть ли надежный способ сделать это?

Дополнительная информация: Сегмент описывается положением P, ориентацией O (величина которой равна радиусу окружности) и размером вида S.

Моя самая успешная попытка на сегодняшний день состоит в определении углов векторов ca1 и ca2,и проверка, лежит ли один из них между углами векторов a1 и a2.Это работает для некоторых случаев, как объяснено выше, но не для ситуаций, когда целевой круг больше, чем сегмент.

Изменить 2 После реализации наилучшего предложения снизу все еще существует ложный положительный результаткоторый я не уверен, как лучше устранить.Смотрите розовую диаграмму ниже.Круг в нижнем правом углу сообщает, что он сталкивается с сегментом, поскольку его границы перекрывают оба полупространства и основной круг.

---

Окончательное редактирование

Обнаружив еще один крайний случай (4-е изображение), я остановился на подходе, который объединяет два главных ответа снизу и, кажется,охватывают все основы.Я опишу это здесь для тех, кто следует.

Сначала исключите все, что не проходит быстрый тест от круга к кругу.

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

Наконец, выполните пару тестов точка-полупространство, используя центр окружности и две внешние линии (как описано Гаретом ниже).Если он проходит оба из тех, в которых он находится, в противном случае верните false.

Answer 1

A. Проверьте, не пересекает ли он весь круг.
B. Проверьте, не пересекается ли она ни с одной из прямых отрезков.
C. Если нет, проверьте, лежит ли угол между центрами окружностей в диапазоне углов сегмента (для этого подходит точечное произведение)

Пересечение требует A && (B || C)

Answer 2

Круглый сегмент (с центральным углом менее 180 °) - это пересечение трех фигур: круга и двух полуплоскостей:

Таким образом, фигура пересекает круговой сегмент, только если она пересекает все три фигуры. [Это только если , но не , если ; см. ниже.]

Пересечение окружности / окружности легко (сравните расстояние между их центрами с суммой их радиусов).

Для пересечения окружности / полуплоскости представьте полуплоскость в виде p · n ≤ k (где p - это проверяемая точка, n - единичный вектор, который является нормальным для линии, определяющей полуплоскость, а k - это константа). Тогда окружность с центром x и радиусом r пересекает полуплоскость, если x · n ≤ k + r .

(Если вам нужно обработать круговой сегмент с центральным углом более 180 °, разделите его на два сегмента с центральным углом менее 180 °. Если я правильно понимаю описание вашей проблемы, вам не нужно будет делать это, поскольку ваше поле зрения всегда будет меньше 180 °, но стоит упомянуть.)

Отредактировано, чтобы добавить: Как указывает beeglebug, круг может пересекать все три фигуры, не пересекая их пересечения. К сожалению. Но я полагаю, что это может произойти только тогда, когда окружность находится за центром сегмента, как показано на диаграмме ниже, и в этом случае мы можем применить тест для разделительной оси для выпуклых фигур.

Теорема о разделяющей оси говорит, что две выпуклые фигуры не могут пересекаться, если существует такая линия, что одна фигура полностью падает на одной стороне линии, а другая - на другой.

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

Пусть центр сегмента находится в начале координат, пусть круг имеет центр x и радиус r , и пусть две полуплоскости имеют (внешние) нормали n₁ и n₂ . Круг находится «позади» отрезка, если

x · n₁ > 0 и x · n₂ > 0

и ось отделяет его от сегмента, если

| х | > r