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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

Определение того, не пересекаются ни один из пересекающихся многоугольников, можно сделать в O(n*log(n)), применяя Shamos-Hoey algorithm. В зависимости от того, что возвращается алгоритм Шамоса-Хоя, многоугольник P i содержит многоугольник P _j, если any vertex from P_j is inside P_i, который делается в O(n) для двух полигонов.

Answer 3

Код, см. gpc.

Answer 4

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

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