Как пересечь несколько полигонов?

Question

Я ищу алгоритм со следующими входами и выходами:

Вход: набор многоугольников на плоскости.Например, P1 ... Pn и S. (P1 ... Pn может быть вогнутым, S выпуклым.)

Вывод: Площадь этих полигонов в этой плоскости, равная разности S и объединенияиз P1 ... Pn.

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

Итак: Как обрабатывать пересечение нескольких полигонов?

Было бы хорошо, если бывсе многоугольники связаны между собой, так как я ищу только область.Я думал о том, чтобы использовать направленные полигоны для имитации дырок, но потом у меня снова возникла проблема, чтобы выяснить, есть ли у меня «минимальное представление», поскольку n может взорваться.[Ты понимаешь о чем я говорю?Это довольно странно ...)

Answer 1

Вы можете объединить все ребра в алгоритм строчной линии .Это может быть не оптимально (?), Но, по крайней мере, вы получите минимальное представление, которое вы ищете.

Answer 2

Самый простой подход - разложить ваши вогнутые полигоны на выпуклые.Тогда пересечение двух выпуклых многоугольников почти тривиально.

Answer 3

Одним из решений является преобразование каждого многоугольника в группу треугольников.Как только вы это сделаете, довольно легко найти объединение / пересечение / разницу между множеством областей, поскольку вы можете выполнять одни и те же функции тривиально в треугольнике (результат для двух треугольников может включать до 6 треугольников).