如何从一组重叠的圆中计算出多边形集合？

Question

如何从一组重叠的圆中计算出多边形集合？

algorithmgeometryareacomputation

4

这个问题是这个问题一些计算细节的扩展。

假设有一组（可能重叠的）圆，希望计算出此组圆覆盖的面积。（为简单起见，可以假设已经进行了一些预处理步骤，例如消除完全包含在其他圆中的圆，以及这些圆形成一个连通分量。）

其中一种方法提到了Ants Aasma和Timothy Shields的答案，即重叠圆形区域只是圆片和多边形的集合，这两者的面积都很容易计算。

然而，我遇到的问题是计算这些多边形。多边形的节点（由圆心和“外部”交点组成）很容易计算：

起初我认为一个简单的算法，随机选择一个节点并按顺时针顺序访问邻居节点就足够了，但这可能会导致构建以下“外部”多边形，而这不是正确多边形的一部分。

所以我考虑了不同的方法。广度优先搜索来计算最小循环，但我认为之前的反例很容易被修改，使得这种方法导致包含孔的“内”多边形（因此不是正确的多边形）。

我想也许可以运行一个拉斯维加斯风格的算法，取随机点，如果该点在圆的交点上，则尝试计算相应的多边形。如果存在这样的多边形，则删除组成该多边形的圆心和交点。重复直到没有圆心或交点剩余。这将避免最终计算“外”多边形或“内”多边形，但会引入新问题（除了潜在的高运行时间之外），例如：多于2个圆在单个交点相交时，在计算一个多边形时可能会删除该交点，但对于下一个圆仍然是必要的。

最终，我的问题是：如何计算这些多边形？ PS：在计算多边形后作为奖励问题，如何知道在θ和2PI-θ之间计算某个圆切片的面积时考虑哪个角度？

- J. Schmidt

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

一旦我们按正确顺序获取了多边形的点，计算面积就不是太难。为了实现这一目标，可以利用平面对偶性。参见维基百科上关于双连通边列表表示的文章以获取图表，但其要点是，给定一个有向边，其右侧面在多边形内部，那么该多边形中的下一个有向边是前一个有向边在顺时针方向上与相同头部相反的方向。因此，我们已经将问题简化为查找多边形联合体的有向边，并确定每个头部的正确顺序。我们实际上首先解决后者的问题。每个圆盘交点都会产生一个四边形。让我们称它们为中心C和D，交点A和B。不失一般性地假设以C为中心的圆盘不小于以D为中心的圆盘。由A→C←B形成的内角小于180度，因此如果且仅当B→C在顺时针方向上在C周围的顺序上先于A→C时，该三角形的有符号面积为负，反之亦然，进而如果且仅当B→D在顺时针方向上在D周围的顺序上先于A→D时，该三角形的有符号面积为负。

现在我们确定哪些边实际上是多边形的边界。对于特定的圆盘，我们之前有一堆关于其中心的角度间隔（每个从第一个端点到第二个端点的顺时针扫描扇形）。我们需要的相当于计算线段并集的常见面试问题的更复杂版本。通常的扫描线算法会在扫描开放端点时增加覆盖计数，并在扫描关闭端点时减少覆盖计数，这里可以使用，但需要调整的是，我们需要将计数初始化为起始角度的适当覆盖计数，而不是0。

这可以通过减法、行列式和比较完成，而无需三角函数。