Как мне определить, пересекаются ли два выпуклых многоугольника?
https://stackoverflow.com/questions/753140
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Предположим, на плоскости имеется несколько выпуклых многоугольников, возможно, карта.Эти многоугольники могут соприкасаться друг с другом и иметь общее ребро, но не могут перекрываться.
Чтобы проверить, есть ли два многоугольника P и Q перекрытие, сначала я могу протестировать каждое ребро в P чтобы увидеть, пересекается ли она с каким-либо из ребер в Q.Если пересечение найдено, я заявляю, что P и Q пересекаться.Если ни один из них не пересекается, я должен проверить случай, когда P полностью содержится в Q, и наоборот.Далее, есть случай, когда P==Q.Наконец, есть случай, который имеет несколько общих ребер, но не все из них.(Эти последние два случая, вероятно, можно рассматривать как один и тот же общий случай, но это может быть и не важно.)
У меня есть алгоритм, который определяет, где пересекаются два отрезка линии.Если два сегмента являются коллинеарными, то для моих целей они не считаются пересекающимися.
Правильно ли я перечислил случаи?Есть какие-нибудь предложения по тестированию в этих случаях?
Обратите внимание, что я не пытаюсь найти новый выпуклый многоугольник, который является пересечением, я просто хочу знать, существует ли пересечение.Существует много хорошо документированных алгоритмов для нахождения пересечения, но мне не нужно прилагать столько усилий.
Решение
Вы могли бы использовать этот алгоритм столкновения:
Чтобы иметь возможность решить, пересекаются ли два выпуклых многоугольника (касаются друг друга), мы можем использовать теорему о разделяющей оси.По существу:
- Если два выпуклых многоугольника не пересекаются, то существует линия, которая проходит между ними.
- Такая линия существует только в том случае, если одна из сторон одного из полигонов образует такую линию.
Первое утверждение очень простое.Поскольку оба многоугольника выпуклые, вы сможете нарисовать линию с одним многоугольником на одной стороне и другим многоугольником на другой стороне, если только они не пересекаются.Второй способ немного менее интуитивно понятен.Посмотрите на рисунок 1.Если ближайшие стороны полигонов не параллельны друг другу, точка, в которой они становятся ближайшими друг к другу, - это точка, в которой угол одного многоугольника становится ближайшим к стороне другого многоугольника.Затем эта сторона образует разделяющую ось между полигонами.Если стороны параллельны, то они обе являются разделяющими осями.
Итак, как это конкретно помогает нам решить, пересекаются ли многоугольники A и B?Что ж, мы просто проходим по каждой стороне каждого многоугольника и проверяем, образует ли он разделяющую ось.Чтобы сделать это, мы будем использовать некоторую базовую векторную математику, чтобы поместить все точки обоих полигонов на линию, перпендикулярную потенциальной разделяющей линии (см. рис. 2).Теперь вся проблема удобно является одномерной.Мы можем определить область, в которой лежат точки для каждого многоугольника, и эта линия является разделяющей осью, если эти области не перекрываются.
Если после проверки каждой линии из обоих полигонов разделяющая ось не была найдена, было доказано, что многоугольники пересекаются, и с этим нужно что-то делать.
Другие советы
если многоугольники всегда выпуклые, сначала вычислите угол линии, проведенной от центра к центру многоугольников.тогда вы сможете исключить необходимость проверки сегментов ребер в половине многоугольника(ов), расположенной на расстоянии 180 градусов от другого(их) многоугольника(ов).
Чтобы удалить края, начните с многоугольника слева.возьмите отрезок линии из центра многоугольника, который перпендикулярен отрезку линии из предыдущего маркера и касается обеих сторон многоугольника.назовем этот отрезок p с вершинами p1 и p2.Затем для всех вершин, если координата x меньше p1.x и p2.x, эта вершина может попасть в «безопасное ведро».
если это не так, вам нужно убедиться, что он находится на «безопасной» стороне линии (просто проверьте также координаты y)
- если у сегмента многоугольника все вершины находятся в «безопасном сегменте», вы можете его игнорировать.
- поменяйте полярность, чтобы вы были «ориентированы вправо» для второго многоугольника.
Ваши тестовые примеры должны работать, поскольку вы проверяете случай, когда многоугольники вообще не пересекаются (полностью снаружи или полностью внутри), а также когда есть какая-либо форма частичного пересечения (края всегда пересекаются, если есть перекрытие) .
Для тестирования я бы просто проверил каждую потенциальную комбинацию.Из того, что я вижу выше, отсутствует одно общее ребро, но один поли содержится в другом.Я бы также добавил тесты для некоторых более сложных полиформ, от трех до многосторонних, просто в качестве меры предосторожности.
Кроме того, если у вас есть U-образный полигон, который полностью окружает полигон, но не перекрывается, я думаю, что ваш случай с этим справится, но я бы добавил и это в качестве проверки.
Поскольку altCognito уже дал вам решение, я лишь укажу отличная книга по вычислительной геометрии это может вас заинтересовать.
Вот идея:
Найдите центральную точку каждого многоугольника
Найдите две точки каждого многоугольника, ближайшие к центральной точке другого.Это будут смежные точки выпуклых многоугольников.Они определяют ближайший край каждого многоугольника, назовем точки {A, B} и {Y, Z}.
Найдите пересечение линий AB и YZ.Если отрезки линий пересекаются (пересечение AB лежит между A и B), ваши многоугольники пересекаются.Если AB и XY параллельны, игнорируйте это условие, следующий шаг устранит проблему.
Есть еще один случай, который вам нужно проверить: когда полигоны пересекаются достаточно сильно, что AB и XY полностью проходят друг за другом и фактически не пересекаются.Чтобы уловить этот случай, вычислите перпендикулярные расстояния AB и XY к центральным точкам каждого многоугольника.Если любая центральная точка находится ближе к сегменту линии противоположного многоугольника, ваш многоугольник сильно перекрывается.
Существует несколько способов обнаружения пересечения и/или включения между выпуклыми многоугольниками.Все зависит от того, насколько эффективным вы хотите видеть алгоритм.Рассмотрим два выпуклых многоугольника R и B с r и b вершинами соответственно:
- Развертка линии основанный алгоритм.Как вы упомянули, вы можете выполнить процедуру развертки линии и сохранить интервалы, возникающие в результате пересечения многоугольников линией развертки.Если в какой-то момент интервалы перекрываются, то полигоны пересекаются.Сложность составляет O((r + b) log (r + b)) времени.
- Вращающиеся суппорты основанный алгоритм.Видеть здесь и здесь Больше подробностей.Сложность составляет O(r + b) времени.
- Самые эффективные методы можно найти здесь и здесь.Эти алгоритмы занимают время O(log r + log b).
