Как определить, пересекаются ли два выпуклых многоугольника?

Question

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

Чтобы проверить, перекрываются ли два многоугольника P и Q , сначала я могу проверить каждое ребро в P , чтобы увидеть, пересекается ли оно с любым из ребер в Q . Если пересечение найдено, я объявляю, что P и Q пересекаются. Если ничего не пересекается, я должен проверить, что P полностью содержится в Q , и наоборот. Далее, есть случай, что P == Q . Наконец, есть случай, который разделяет несколько ребер, но не все. (Эти два последних случая, вероятно, можно рассматривать как один и тот же общий случай, но это может не иметь значения.)

У меня есть алгоритм, который определяет, где пересекаются два отрезка. Если два сегмента коллинеарны, они не считаются пересекающимися для моих целей.

Правильно ли я перечислил дела? Любые предложения для тестирования в этих случаях?

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

Answer 1

Вы можете использовать этот алгоритм столкновения :

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

• Если два выпуклых многоугольника не пересекаются, существует линия, проходящая между ними.
• Такая линия существует, только если одна из сторон одного из многоугольников образует такую ​​линию.

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

Так, как это конкретно помогает нам решить, пересекаются ли многоугольники A и B? Что ж, мы просто переходим каждую сторону каждого многоугольника и проверяем, образует ли он разделяющую ось. Для этого мы будем использовать некоторую базовую векторную математику, чтобы раздвинуть все точки обоих многоугольников на линию, которая перпендикулярна потенциальной разделительной линии (см. Рисунок 2). Теперь вся задача удобно одномерна. Мы можем определить область, в которой лежат точки для каждого многоугольника, и эта линия является разделительной осью, если эти области не перекрываются.

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

Answer 2

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

• для устранения краев, начните с многоугольника слева. Возьмите отрезок линии от центра многоугольника, который перпендикулярен отрезку линии от предыдущей маркировки, и коснитесь обеих сторон многоугольника. Назовите этот отрезок линии p с вершинами p1 и p2. Тогда для всех вершин, если координата x меньше p1.x и p2.x, эта вершина может войти в «безопасное ведро».

• если этого не произойдет, вы должны убедиться, что он находится на «безопасной» стороне линии (просто проверьте координаты y)

- если у отрезка линии в многоугольнике есть все вершины в «безопасном ведре», вы можете его игнорировать.

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

Answer 3

GJK столкновение обнаружение должно работать .

Answer 4

Вот идея:

• Найти центральную точку каждого многоугольника

• Найдите две точки каждого многоугольника, расположенные ближе всего к центральной точке другой. Они будут смежными точками в выпуклых многоугольниках. Они определяют ближайшее ребро каждого многоугольника, назовем точки {A, B} и {Y, Z}

• Найдите пересечение прямых AB и YZ. Если отрезки отрезков пересекаются (пересечение на AB лежит между A и B), ваши полигоны пересекаются. Если AB и XY параллельны, игнорируйте это условие, следующий шаг решит проблему.

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

Answer 5

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

Answer 6

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

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

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

Answer 7

Существует несколько способов обнаружения пересечения и / или локализации между выпуклыми многоугольниками. Все зависит от того, насколько эффективным вы хотите, чтобы алгоритм был. Рассмотрим два выпуклых многоугольника R и B с r и b вершинами соответственно:

1. Линейка развертки алгоритм на основе. Как вы упомянули, вы можете выполнить процедуру линии развертки и сохранить интервалы, возникающие в результате пересечения полигонов с линией развертки. Если в любое время интервалы перекрываются, то полигоны пересекаются. Сложность O ((r + b) log (r + b)) времени.
2. Вращающиеся штангенциркули алгоритм на основе. См. здесь и здесь для получения более подробной информации. Сложность O (r + b) времени.
3. Наиболее эффективные методы можно найти здесь и здесь . Эти алгоритмы занимают время O (log r + log b).