Построение полигонов из объединения множества полигонов

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

] Для моей цели, вы можете представить каждый кусок многоугольника как кусок головоломки, когда вы соберете их, вы получите красивую картинку. Но загвоздка в том, что отсутствует небольшая часть (скажем, <5%) лобзика, и вам все равно необходимо сформировать изображение как можно более полно; который' s многоугольник (или многоугольники) - возможно, с отверстиями - который я хочу сформировать.

Мой наивный подход состоит в том, чтобы взять два многоугольника, объединить их и взять еще один многоугольник, объединить его с объединением двух многоугольников, и повторяйте этот процесс, пока каждая деталь не станет единой. Затем я пробегу по списку объединяемых полигонов и проверю, есть ли еще какие-то полигоны, которые можно объединить, и буду повторять этот процесс до тех пор, пока не будет достигнут удовлетворительный результат.

Но это кажется крайне наивным подходом. Мне просто интересно, есть ли другой лучший алгоритм?

10
задан Graviton 26 December 2010 в 13:37
поделиться