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

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

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

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