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

Question

Я отправил несколько дней назад этот вопрос: Как пересечь несколько полигонов? .Теперь я реализовал алгоритм строчной линии в соответствии с рекомендациями (в частности, от Martinez, Rueda и Feito).

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

Изображение того, что я имею в виду:

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

Теперь мне нужна область многоугольников (отмечена серым цветом).Моей первой идеей было добавить многоугольник за многоугольником и проверить, содержат ли они друг друга, и использовать какой-то интеллектуальный механизм выбора, чтобы выбирать только нужные многоугольники.Но это порождает некоторый алгоритм O (n ^ 2): для обработки каждого полигона каждое ребро должно сравниваться с каждым ребром, которое уже обработано.

Не очень хорошо.Можете ли вы дать мне подсказку, как рассчитать общую площадь?

Answer 1

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

Если они у вас в другом порядке, значит, у вас проблема. Лучше исправить это сейчас.