Способ обнаружить пересечение между прямоугольником и многоугольником?

Question

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

Answer 1

Есть четыре случая.

1. Rect находится за пределами Poly
2. Rect пересекает Poly
3. Rect находится внутри Poly
4. Поли внутри Rect

Во-первых: проверьте произвольную точку в вашем Rect против Poly (см. Point in Polygon). Если это внутри, вы сделали, потому что это либо случай 3 или 2. Если это за пределами, исключается случай 3.

Второе: сопоставьте произвольную точку вашего Поли с Rect, чтобы проверить / исключить случай 4.

В-третьих: проверьте линии вашего Rect относительно Poly для пересечения, чтобы подтвердить / исключить вариант 2.

Это также должно работать для полигонов и полигонов (выпуклых и вогнутых), но таким образом это более читабельно.

Answer 2

Если ваш многоугольник не выпуклый, вы можете использовать тесселяция , чтобы подразделить его на выпуклые части.Поскольку вы ищете способы обнаружения возможного столкновения, я думаю, вы могли бы взглянуть и на алгоритм GJK .Даже если вам не нужно что-то настолько мощное (оно предоставляет информацию о минимальном расстоянии между двумя выпуклыми фигурами и связанными точками-свидетелями), это может оказаться полезным, если вы решите обрабатывать больше различных выпуклых форм.Кристер Эриксон сделал отличную презентацию в Powerpoint , если вы хотите узнать больше об этом алгоритме.Вы также можете взглянуть на его книгу Обнаружение столкновений в реальном времени , которая является полной и доступной для любого, кто обнаруживает алгоритмы обнаружения столкновений.

Answer 3

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

Answer 4

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

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

Answer 5

Просто чтобы определить, есть ли перекресток, я думаю, что вы можете объединить два алгоритма.

1) Алгоритм наведения лучей. Используя вершины каждого многоугольника, определите, находится ли одна из вершин в другой. Предполагая, что вы не беспокоитесь о фактической области пересечения, а просто о ее существовании. http://en.wikipedia.org/wiki/Point_in_polygon

2) Пересечение линии. Если шаг 1 ничего не дает, проверьте пересечение линии.

Я не уверен, что это на 100% правильно или оптимально.

Если вам действительно нужно определить область пересечения, которая является более сложной, см. Предыдущий ответ SO:

Простой алгоритм пересечения полигонов