合并多边形的有效算法
我有一个多边形列表，在这个列表中，一些多边形重叠，或触及其他多边形。
我的任务是合并彼此重叠或触摸的所有多边形。 我有一个union方法来做到这一点。
最有效的方法是什么？ 我现在能想到的是循环多边形列表，检查合并列表以查看此多边形是否已经某种方式属于合并列表中的一个多边形，如果是，则将它们联合起来，如果不是，则添加此多边形到合并列表的末尾。
再次重复上述步骤几次，以确保所有多边形都正确组合。
这种方法似乎非常不优雅; 有一个更好的方法吗？
如果它不是union方法的一部分，你可以使用边界框/圆进行预测试，但是你的琐碎实现似乎可以在1000左右的多边形，甚至10000，这取决于它们的复杂程度。 在此之后，您可以改进的一种方法是将多边形存储在某种空间树中，如quad-kd，bsp或R-tree。 请注意，将数据放入这些树中往往相对于它们的操作而言是昂贵的，因此在这种情况下您必须在整个软件中使用它。
这里有一个想法：执行扫描以确定哪些多边形仍然重叠，然后执行合并。
假设所有多边形都在输入列表中。
-
对于每个Polygon P_i构建一个多边形的OVERLAP，它覆盖了P_i。
-
从OVERLAP获取Polygon P_i和任何仍然存在的Polygon P_k，将它们联合起来并将P_k的OVERLAP列表添加到P_i的重叠列表中。 从输入列表和P_i的OVERLAP列表中删除P_k。
-
如果P_i的OVERLAP列表为空，则表示已找到P_i的传递并集。 前进到输入列表中的下一个剩余多边形。
这种方法有很多好处：
-
您只需要对输入多边形进行交集测试（输入多边形可能更小，并且与生成的联合更不复杂）。
-
您可以使用空间索引来加速多边形交叉检查，而不必为合并的多边形更新它。
-
您可以确定要合并哪些多边形而不实际进行并集 。 这意味着您可以计算不同合并组的列表，并将实际合并移交给某些专用算法（如果要合并两组多边形，则可以并行执行此操作！）
这是一些伪代码：
-- these are the input arrays var input:array[Polygon]; -- if Polygon #3 overlaps with #7 and #8 then overlaps[3] contains the list {7,8} var overlaps:array[list[integer]]; -- compute the overlaps for i=1..input.size overlaps[i]=new list[integer]; for k=i+1..input.size if input[i] *overlaps* input[k] then overlaps[i].append(k); end if end for end for var check:integer -- for all polys for i=1..input.size -- if this poly is still in the input list (and not neutered with null) if input[i] then -- check all the polys that overlap with it for k=1..overlaps[i].size -- 'check' is a candidate check=overlaps[i][k] -- is this poly still in the input array? if input[check] then -- do the merge input[i] = input[i] *union* input[check] -- and delete this polygon from the input array input[check]=null -- and let input[i] inherits the overlapping polygons of check. overlaps[i].append(overlaps[check]) end if end for end if end for
之后，’input’应仅包含非重叠多边形（或null以指示多边形已在某处合并）
我没有多想过这个，但看看这是否有效……
//let L be the list of all polygons, M be the list of all merged polygons //let head(L) be the first polygon in the list and tail(L) be the //remaining polygons other than the head polygon. let h = head(L) let t = tail(L) while(length(t) > 0) foreach(polygon p in t) if(p intersects h) let h = p union h t.remove(p) M.append(h) let h = head(t) let t = tail(t)