Объединение многих (более двух) полигонов без дырок

Question

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

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

Answer 1

Вы можете сделать это итеративно и создать набор связанных компонентов (вместо всегда только одного подключенного компонента):

1. Поместить все полигоны в «открытый» список.Инициализируйте пустой список компонентов .
2. Пока open не пусто:
   • Удалите многоугольник p из открыть и установить флаг изменено на истинное значение.
   • Повторить, пока изменено верно:
     • установить изменено в false
     • для каждого многоугольника q in open :
       • , если q пересекается p ,удалите q из open , установите , изменив в true, и установите p в объединение p и q .
   • добавление p к компонентам .

В конце компоненты будут состоять из всех непересекающихся, связанных компонентов, которые могут быть сформированы путем объединения входных многоугольников.В вашем опубликованном образце он должен создать один полигон.

Это не самый эффективный подход (см. Алгоритмы в ссылке, размещенной Рики Бобби), но он имеет преимущество простоты.При условии, что вы не имеете дело с сотнями полигонов, он должен работать очень хорошо.

PS Как указывает @japreiss, объединение может иметь отверстия, даже если ни один из входных полигонов не имеет отверстия, даже если входные данныевсе выпуклые многоугольники.Если входы могут быть вогнутыми, то даже объединение 2-х полигонов может иметь отверстие.Ваш алгоритм с двумя полигонами уже справился с этим?

Answer 2

Вы не должны смотреть на многоугольники один за другим.

Вы можете применить любой из 2 алгоритмов из этого вопроса объединение многоугольников без дырок напрямую с n многоугольниками.

надеюсь, это поможет

Answer 3

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