Я создаю объединение полигонов без дыр. Входные многоугольники без дырок, а на выходе тоже должны быть. У меня уже есть рабочий алгоритм нахождения его для двух полигонов. Но если их больше двух, возникает проблема. Поскольку объединение не должно быть непересекающимся многоугольником, когда я пытаюсь вычислить их сумму один за другим, у меня возникает проблема в таком случае:
Тогда многоугольник 1 пересекает многоугольник 2, объединение не пересекается (поэтому мой алгоритм не вычисляет сумму). Во втором цикле ofc выполняется объединение с 3-м и 4-м многоугольниками, но на выходе получается без 2-го многоугольника. Так знает ли кто-нибудь быстрый и точный алгоритм этого? Вероятно, хорошей идеей было бы сначала отсортировать полигоны по пересечениям, но я не могу придумать для этого быстрых алгоритмов, а также не совсем уверен, как их следует сортировать.