У меня есть многоугольник (иногда выпуклый, но часто вогнутый) и несколько кругов с разными радиусами. Как я могу узнать, пересекается ли / пересекается ли круг с многоугольником?
Я мог бы разбить мой вогнутый многоугольник на выпуклые части. Это поможет?
Есть два случая этой проблемы. Первый - это пересечение, а второй - перекрывающий (содержащий).
Первый (пересечение / многоугольник внутри круга):
Найдите ближайшую точку на каждом краю многоугольника к центру круга. Если любое расстояние между ближайшей точкой к центру меньше радиуса, вы получили пересечение или перекрытие.
Второе (круг - многоугольник): снимите луч из центра круга вправо (или влево / вверх / вниз) и пересчитайте пересечения луча / сегмента (ребра многоугольника). Если количество пересечений четное, круг находится за пределами многоугольника. Если это странный круг внутри.
Я поделюсь картинкой из лекции для этого случая:
И заботиться о единичных случаях.
Надеюсь, это поможет.
редактировать: я думаю, что это просто справедливо, чтобы добавить кредиты на картинку. Автор Петр Фелькель, доцент Чешского технического университета в Праге
Первый шаг, как вы думаете, состоит в том, чтобы разбить вогнутый многоугольник на несколько выпуклых. Причина этого в том, что вы будете использовать теорему о разделительной оси , которая работает только на выпуклых многоугольниках.
SAT per se работает только на двух выпуклых многоугольниках. «Разделительная ось» в названии относится к осям, перпендикулярным краям многоугольника. Круги, к сожалению, имеют бесконечное их количество. Однако оказывается, что существует довольно простой способ выяснить, какие из этих осей актуальны, если посмотреть на то, какой проект направлен наружу, чтобы пересекать вершины многоугольника.
Вместо того, чтобы рассматривать весь алгоритм здесь, у Metanet Software (создателей N / N +) есть хорошее руководство по обнаружению столкновений с использованием SAT , третий раздел которого посвящен SAT, когда один из объектов представляет собой круг .
источник
Вот что я делаю.
источник