构造多边形联合多边形

Question

假设我有很多多边形,构造多边形的最佳算法是什么 - 可能是所有这些多边形的并集孔？

为了我的目的,你可以想象每个多边形作为一个拼图块,当你完成它们你会得到一个很好的图片.但问题是,缺少一小部分(比如<5%)的拼图,你仍然要求尽可能完整地形成一幅画面; 这是多边形(或多边形) - 可能有孔 - 我想形成.

我天真的方法是取两个多边形,合并它们,然后取另一个多边形,将它与两个多边形的并集联合起来,然后重复这个过程,直到每个单元都结合在一起.然后我将遍历联合多边形列表并检查是否仍然可以组合一些多边形,并且我将重复此过程,直到获得满意的结果.

但这似乎是一种非常天真的方法.我只是想知道还有其他更好的算法吗？

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）这样的框架来为您实现这些算法。