algorithm - 如何从一组重叠的圆计算多边形组？

Question

这个问题是对this question的一些计算细节的扩展。 .
假设一个人有一组(可能重叠的)圆，并且希望计算这组圆覆盖的面积。 (为简单起见，可以假设已经进行了一些预计算步骤，例如去除完全包含在其他圆中的圆，以及这些圆包含一个连通分量。)

提到了一种方法来做到这一点 in Ants Aasma's and Timothy's Shields' answers ，因为重叠圆的面积只是圆切片和多边形的集合，两者的面积都很容易计算。


然而，我遇到的麻烦是这些多边形的计算。多边形的节点(由圆心和“外部”交点组成)很容易计算:

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

所以我想到了不同的方法。广度优先搜索来计算最小循环，但我认为可以轻松修改前面的反例，以便这种方法导致包含孔的“内部”多边形(因此不是正确的多边形)。
我正在考虑可能运行拉斯维加斯风格的算法，取随机点，如果所述点在圆的交点中，则尝试计算相应的多边形。如果存在这样的多边形，则删除构成该多边形的圆心和交点。重复直到没有圆心或交点。
这将避免最终计算“外部”多边形或“内部”多边形，但会引入新问题(在潜在的高运行时间之外)，例如在计算一个多边形时，在一个交点处相交的 2 个以上的圆可以去除所述交点，但对于下一个多边形仍然是必要的。
最后，我的问题是:如何计算这样的多边形？
PS:作为计算多边形后的额外问题，如何知道在计算θ和 2PI - theta 之间的某个圆形切片的面积时要考虑哪个角度？

Answer 1

一旦我们以正确的顺序获得多边形的点，计算面积就是 not too difficult .
实现这一目标的方法是利用平面二元性。请参阅 doubly connected edge list 上的维基百科文章图的表示，但要点是，给定一个右面在多边形内的定向边，该多边形中的下一个定向边是前一个定向边的相反方向，按顺时针顺序具有相同的头部。
因此，我们将问题简化为找到多边形联合的定向边并确定每个头部的正确顺序。我们实际上是先解决后一个问题。圆盘的每个交叉点都会产生一个四边形。我们称中心C和D以及交点A和B。不失一般性，假设以C为中心的圆盘不小于以D为中心的圆盘。由A→C←B形成的内角小于180度，所以该三角形的有符号面积为负当且仅当 A→C 在 C 周围顺时针顺序在 B→C 之前，反过来当且仅当 B→D 在 D 周围顺时针顺序在 A→D 之前。
现在我们确定哪些边实际上是多边形边界。对于一个特定的磁盘，我们在它的中心周围有一堆角度间隔(每个间隔从第一个端点到第二个端点扫过顺时针扇区)。我们需要的是计算段联合的常见面试问题的更复杂版本。通常的扫描线算法在扫描打开端点时增加覆盖计数并在扫描关闭端点时减少覆盖计数可以在这里工作，我们需要将计数初始化为不为 0 而是初始化为起始角度的正确覆盖计数。
有一种方法可以在没有三角函数的情况下完成所有这些，只需减法、行列式和比较。