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

Question

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

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

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

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

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

Answer 1

Вы можете использовать this collision algorithm:

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

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

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

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

Answer 4

Поскольку altCognito уже дал вам решение, я укажу только an excellent book on computational geometry, которые могут вас заинтересовать.

Answer 5

Вот идея:

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

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

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

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

Answer 6

GJKcollisiondetectionshouldwork.

Answer 7

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

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