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

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

alt text

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот идея:

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

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

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

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

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

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

Как распределить приложение ios без проводов без управления UDID и перекомпиляции

Почему некоторые веб-сайты отображают название компании рядом с URL-адресом?

Как вызвать функции controllerа с помощью JQuery в ASP.NET MVC

Как восстановить информацию с мертвого жесткого диска?

Является ли ключ продукта Windows 10 в BIOS?

Вставка кода в окно терминала в vim на Mac OS X

Как я могу создать сценарий создания резервных копий недавно измененных файлов в Bash?

Загрузка нескольких изображений в MATLAB

Контейнер-жидкость против контейнера

Как получить сетевой интерфейс и его правый IPv4-адрес?

Как DNS используется отдельными процессами?

Исключение ResultSet – до начала набора результатов

Переопределение controllerа AuthorizeAttribute всего за одно действие

Сделать Chrome автоматически загружать небезопасный контент для определенных страниц / веб-сайтов

Сгладить список, используя только формы в «The Little Schemer»

Давайте будем гением компьютера.