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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

Код см. gpc .