Построить многоугольники из объединения многих многоугольников

Question

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

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

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

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

Answer 1

Вам нужна библиотека отсечения полигонов - и я подключу свою собственную библиотеку Clipper , так как она написана на C # (и C ++ и Delphi), это бесплатное программное обеспечение с открытым исходным кодом, и оно будет делать именно то, что вы хочу.

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

Это был бы очень неэффективный подход. Гораздо лучшим способом было бы объединить их всех в одну операцию ...

using ClipperLib;
using Polygon = List<IntPoint>;
using Polygons = List<List<IntPoint>>;
...

//precondition: all your polygons have the same orientation 
//(ie either clockwise or counter clockwise)
Polygons polys = new Polygons(PolyCnt);
for (int i = 0; i < PolyCnt; i++)
    polys.Add(loadPolyFromFile(String.Format("poly{0}.txt", i +1)));

Polygons solution = new Polygons();
Clipper c = new Clipper();
c.AddPolygons(polys, PolyType.ptSubject);
c.Execute(ClipType.ctUnion, solution, 
    PolyFillType.pftNonZero, PolyFillType.pftNonZero);

//code to display solution here.

Answer 2

Это грубая сила, что ты делаешь.Лучший способ сделать грубую силу - это ветвление и связывание.Но это все еще ужасно масштабируется.

Следующим шагом является попытка метаэвристических алгоритмов (поиск по табу, имитация отжига, ...) или просто повторное использование фреймворка, например Drools Planner (с открытым исходным кодом, Java), который реализует их для вас.