将圆加入多边形的算法

Question

将重叠的圆组合成多边形的最佳方法是什么？

我给出了一个具有固定直径的圆的中心点列表。

我需要加入任何重叠的圆圈一起和输出点的列表中所产生的多边形。

这似乎是一个相当普遍的问题（GIS系统，矢量等）。这可以通过Google Maps API完成，但我正在寻找实际的算法。

我试图通过计算每个圆周围的点来解决这个问题。

然后删除位于任何圆圈内的任何点。

这给了我想要的多边形中正确的点列表。

但是，点的顺序是这个解决方案的问题。每个圆都将其点存储在一个数组中。将它们与2个重叠圆圈正确合并是相对直接的。但是，当处理多个重叠的圆时，它变得复杂。

希望你有一些想法，使这个解决方案的工作或其他算法，将达到预期的结果。

在此先感谢！

Answer 1

您应该能够使用appraoch类似如下：

1. 首先，确定属于同一组重叠圆圈圈。显然，如果两个圆的中心的绝对距离小于它们的组合半径，则两个圆重叠。对于每个圈子，将圈出的圈子存储在hashmap/dictionary中。 （您可以使用union-find algorithm, or disjoint sets将它扩展到整个圆圈组，但这不是真的需要。）
2. 创建属于一个圆的点时，请记住每个点的左右邻居。您只需将它们存储在有序数组中即可免费获得此内容。
3. 删除“内”点，即那些比一个半径更接近与第一个圆相交的圆的任何中心的点。
4. 将邻居标记为那些没有去除圈子“松散结尾”的内点。
5. 将未移除的点（包括松散结束点）连接到其原始左侧和右侧邻居。
6. 对于每个松散的终点，找到同一组中最近的另一个圆的松散端并将它们连接起来。

下面是一张照片来说明方法。

• 红点是被除去
• 蓝点是“松散端”通过被邻居“内”点“内”点;每个“松散的末端”具有另一个“松散的末端”，其距离小于两个“点距离”
• 绿点可以容易地通过其顺序与其邻居（包括“松散的末端”他们被安排在圆周围。

可以进一步通过区分左和右松散端部，并使用该一个圆的每个左松散端部具有将被连接到的另一个右松动端的事实降低的可能组合的数量圈。对于组中的n圈，仅留下(n-1)!方式来连接这些圈，而不考虑每圈的点数。

即使只考虑组中实际上与松散结束的圆相交的那些圆（只是将它们存储在散列表/字典中），也可以进一步降低这一点。所以如果你有n的圈子平均与k其他圈子相交，那么只有n*k可能的组合。

您也可以使用这样的事实，即其他松散端不能比圆上两点之间距离的两倍更远。我们称这个距离为d，然后您可以创建一个分辨率为d的空间图（例如一个散列图或二维数组），并将每个松散端分配给该地图中的单元格，然后另一个松散端必须与另一个相同的第一个松散的末端周围的细胞。

因此，点之间可以相互连接的方式的数量大大减少了（特别是，它们在最终图像中的连接方式不允许从头开始）：这应该是可行的即使有蛮力，除非您在同一组中有批次重叠的圆圈，并且您可以使用更智能的nearest-neighbor search算法。

---

更新：回顾一段时间后这个答案，似乎就可以比较容易地确定的“宽松结束”点匹配对：假设你有在圈A中的“右”宽松结束，则匹配“左”松散的末端必须属于其半径重叠下一个“内”点到第一个“松散末端”的圆。因此，如果您将该关系存储在另一张地图中，则可以立即确定匹配的松散结束。 （如果内点与其他多个圆重叠，则该图应该包含与其重叠的圆）。

Answer 2

下面是O（n log n）时间算法的草图。

1. 使用您最喜欢的算法/库来计算圆心上的Delaunay triangulation。

2. 删除不重叠的圆之间的边。

3. 漫步每个连接组件的无限面。用doubly connected edge list表示法很容易实现，其中边缘列表的排序用于指示平面图的拓扑。在这个边界上的每个半边都变成了一个顶点，其中属于它的尾点的弧段终止并且属于它的头点的弧段开始。

4. （可选）用折线近似每个弧段。

_{如果有人来自谷歌正在阅读本文，请注意，我没有看过相关的代码。}