将圆连接到多边形的算法
aar*_*arr 11 algorithm geometry polygon
将重叠圆组合成多边形的最佳方法是什么？
我给出了一个固定直径的圆心点列表.
我需要将任何重叠的圆圈连接在一起,并在结果多边形中输出一个点列表.
这似乎是一个相当普遍的问题(GIS系统,载体等).这可以通过Google Maps API完成,但我正在寻找实际的算法.
我试图通过计算每个圆周围的点来解决这个问题.
然后删除任何圆圈内的任何点.
这为我提供了所需多边形中正确的点列表.
但是,点的顺序是该解决方案的问题.每个圆的点都存储在一个数组中.要将它们正确地与2个重叠的圆圈合并,这是相对简单的.但是,当处理多个重叠的圆圈时,它会变得复杂.
希望您有一些想法可以使这个解决方案工作或另一个算法,以实现所需的结果.
提前致谢!
您应该能够使用如下方法：
- 首先，识别属于同一组重叠圆的圆。显然，如果两个圆的圆心的绝对距离小于它们的组合半径，则两个圆重叠。对于每个圆，将其迭代的圆存储在哈希图/字典中。（您可以使用并查找算法或不相交集将其扩展到整个圆组，但这并不是真正需要的。）
- 创建属于一个圆的点时，请记住每个点的左右邻居。只需将它们存储在有序数组中即可免费获得它。
- 删除“内部”点，即距离与第一个圆相交的任意圆心比一个半径更近的点。
- 将邻居标记为那些未移除圆的“松散末端”的内部点。
- 将未删除的点（包括松散的末端）连接到其原来的左右邻居。
- 对于每个松动端点，找到同一组中不同圆的最接近的松动端点并将它们连接起来。
这是一张图片来说明该方法。
- 红点是被移除的“内部”点
- 蓝点是“未解决的问题”，与“内部”点相邻；每个“松散端”都有另一个不同圆的“松散端”，距离小于两个“点距离”
- 绿点可以通过它们在圆周围排列的顺序轻松地连接到它们的邻居（包括“松散的末端”）。
您可以通过区分左松散端和右松散端，并利用一个圆的每个左松散端必须连接到另一个圆的右松散端这一事实，进一步减少可能的组合数量。对于n一组中的圆，只留下(n-1)!连接这些圆的方法，而不管每个圆的点数是多少。
如果您只考虑组中与松散端实际相交的那些圆（只需将它们存储在哈希图/字典中），那么甚至可以进一步减少这种情况。因此，如果您的n圆平均与k其他圆相交，则只有n*k可能的组合。
您还可以利用这样一个事实：另一个松散端的距离不能超过圆上两点之间距离的两倍。我们将这个距离称为距离d，然后您可以创建一个具有分辨率的空间图d（例如散列图，或只是一个二维数组）并将每个松散端分配给该地图中的单元格，然后另一个松散端必须与其中一个松散端相同第一个松散端的周围细胞。
因此，点相互连接的方式数量大大减少（特别是，它们在最终图像中的连接方式一开始就不允许）：即使使用蛮力，这也应该是可行的，除非你在同一组中有很多重叠的圆圈，并且您可以使用更智能的最近邻搜索算法。
更新：一段时间后回顾这个答案，似乎您可以相当容易地确定“松散端”点的匹配对：假设您在圆 A 中有一个“右”松散端，那么匹配的“左”松散端必须属于半径与第一个“松散端”的下一个“内部”点重叠的圆。因此，如果您将该关系存储在另一个映射中，您可以立即确定匹配的松散末端。（如果内部点与多个其他圆重叠，则地图应包含与其重叠最多的圆。）