Определение пересечения и локализации многоугольника

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

Мне также необходимо определить дерево сдерживания, которое представляет собой набор отношений, которые говорят, что многоугольник содержит любой заданный многоугольник. Так как ни один полигон не может пересекать ни один другой, то любой содержащийся многоугольник имеет уникальный контейнер; "следующий". Другими словами, если A содержит B, содержит C, то A является родительским элементом B, а B является родительским элементом C, и мы не рассматриваем A родительский элемент C.

Вопрос: как эффективно определить отношения сдерживания и проверить критерий непересечения? Я задаю это как один вопрос, потому что, возможно, комбинированный алгоритм более эффективен, чем решение каждой проблемы отдельно. Алгоритм должен взять в качестве входного списка список полигонов, заданный списком их вершин. Он должен вызывать логическое B, указывающее, что ни один из многоугольников не пересекает какой-либо другой многоугольник, а также если B = true, список пар (P, C), где многоугольник P является родителем дочернего элемента C.

Это не домашнее задание. Это для проекта хобби, над которым я работаю.

Ответ 1

Во-первых, ваш алгоритм тестирования сдерживания не проверяет правильность пересечения. Представьте себе два прямоугольника:

    +--+
 +--+--+--+
 |  |  |  |
 +--+--+--+
    +--+

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

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

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

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

Ответ 2

Определение того, можно ли пересечь ни один из полигонов в O(n*log(n)), применяя алгоритм Shamos-Hoey. В зависимости от того, что возвращает алгоритм Шамоса-Хоя, многоугольник P _i содержит многоугольник P _j, если любая вершина из P _j находится внутри P _i, что сделано в O(n) для двух полигонов.

Ответ 3

Чтобы проверить пересечения, вы можете использовать мою бесплатную библиотеку клиперов: http://sourceforge.net/projects/polyclipping/.

Чтобы проверить защиту, сначала исключите пересечения, как указано выше. Затем используйте Clipper снова, добавляя все полигоны - Clipper.AddPolygon(). Затем выполните операцию объединения (логическое ИЛИ) на многоугольниках - Clipper.Execute(ctUnion, solution). Если свойство Clipper.ForceAlternateOrientation истинно, Clipper вернет в решение внешние полигоны по часовой стрелке и содержит полигоны (отверстия) в направлении против часовой стрелки. Затем должно быть простым вопросом проверки ориентации полигонов и применения PointInPolygon из одной вершины в противном против часовой стрелки многоугольника против других полигонов по часовой стрелке.

Ответ 4

Для кода см. gpc.