假设我有很多多边形，从所有这些多边形的并集构造一个多边形(可能有洞)的最佳算法是什么？
就我的目的而言，您可以将多边形的每一 block 想象成一 block 拼图，当您完成它们时，您会得到一张漂亮的图片。但美中不足的是拼图少了一小部分(比如说<5%)，你还是需要拼图尽可能完整；这就是我想要形成的多边形(或多边形)——可能带有孔洞。
我天真的方法是取两个多边形，将它们并集，然后取另一个多边形，将其与两个多边形的并集并集，并重复此过程，直到每一 block 都成为并集。然后我会遍历联合多边形列表，检查是否还有一些多边形可以合并，我会重复这个过程，直到得到满意的结果。
但这似乎是一种极其幼稚的做法。我只是想知道还有其他更好的算法吗？
最佳答案
您需要一个多边形裁剪库 - 我会插入我自己的 Clipper库，因为它是用 C#(以及 C++ 和 Delphi)编写的，它是开源免费软件，并且可以完全满足您的需求。
My naive approach is to take two polygons, union them, and take another polygon, union it with the union of the two polygons, and repeat this process until every single piece is union
那将是一种非常低效的方法。一种更好的方法是在一个操作中将它们全部“合并”...
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.
关于c# - 从许多多边形的并集构造多边形，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4526143/