这个问题是一些计算细节的扩展这个问题 https://stackoverflow.com/questions/1667310/combined-area-of-overlapping-circles.
假设有一组（可能重叠的）圆，并且希望计算这组圆所覆盖的面积。 （为简单起见，可以假设已经进行了一些预计算步骤，例如消除完全包含在其他圆中的圆，以及这些圆引起一个连通分量。）
提到了一种方法来做到这一点在 Ants Aasma 和 Timothy Shields 的回答中 https://stackoverflow.com/questions/1667310/combined-area-of-overlapping-circles，因为重叠圆的面积只是圆切片和多边形的集合，两者的面积都很容易计算。
然而，我遇到的麻烦是这些多边形的计算。多边形的节点（由圆心和“外部”交点组成）很容易计算：
起初，我认为选择一个随机节点并按顺时针顺序访问邻居的简单算法就足够了，但这可能会导致构建以下“外部”多边形，该多边形不是正确多边形的一部分。
所以我想到了不同的方法。广度优先搜索来计算最小循环，但我认为前面的反例可以很容易地修改，以便这种方法产生包含孔的“内部”多边形（因此不是正确的多边形）。
我正在考虑运行拉斯维加斯风格的算法，随机取点，如果所述点位于圆的交点中，则尝试计算相应的多边形。如果存在这样的多边形，则去除构成该多边形的圆心和交点。重复此操作，直到不再有圆心或交点。
这将避免最终计算“外部”多边形或“内部”多边形，但会引入新问题（除了潜在的高运行时间之外）e.g.在计算一个多边形时，在单个交点相交的两个以上圆可以删除该交点，但对于下一个多边形仍然是必要的。
最终，我的问题是：如何计算这样的多边形？
PS：作为计算多边形后的一个额外问题，如何知道在计算 θ 和 2PI - θ 之间的某个圆切片的面积时要考虑哪个角度？
一旦我们按照正确的顺序获得了多边形的点，计算面积就是不太难 https://stackoverflow.com/a/34327761/2144669.
实现这一目标的方法是利用平面对偶性。请参阅维基百科文章双连通边列表 https://en.wikipedia.org/wiki/Doubly_connected_edge_list图表的表示，但要点是，给定一条右面在多边形内的定向边，该多边形中的下一个定向边是按顺时针顺序具有相同头的前一个定向边的相反方向。
因此，我们将问题简化为找到多边形联合的定向边并确定每个头的正确顺序。我们实际上先解决后一个问题。圆盘的每个交点都会产生一个四边形。我们将中心称为C和D以及交点A和B。不失一般性地假设以C为中心的圆盘不小于以D为中心的圆盘。A→C←B形成的内角小于180度，因此当且仅当绕 C 顺时针顺序 A→C 先于 B→C 时，该三角形的有符号面积为负，反过来当且仅当绕 D 顺时针顺序 B→D 先于 A→D 时。
现在我们确定哪些边实际上是多边形边界。对于特定的圆盘，我们在其中心周围有一堆角度间隔（每个角度间隔从第一个端点到第二个端点扫过顺时针扇区）。我们需要的是计算段并集的常见面试问题的更复杂版本。通常的扫描线算法，每当扫描开放端点时就增加覆盖计数，而每当扫描封闭端点时就减少覆盖计数，这可以在这里发挥作用，但我们需要将计数初始化为 0，而不是 0。起始角度的正确覆盖计数。
有一种方法可以完成所有这些，无需三角学，只需减法、行列式和比较。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
