如何从一组重叠的圆计算多边形组? [英] How to compute the set of polygons from a set of overlapping circles?

问题描述

这个问题是对

然而，我遇到的问题是这些多边形的计算.多边形的节点(由圆心和外部"交点组成)很容易计算:

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

所以我想到了不同的方法.广度优先搜索来计算最小循环，但我认为可以轻松修改前面的反例，以便这种方法导致内部"循环.包含洞的多边形(因此不是正确的多边形).

我在考虑可能运行拉斯维加斯风格的算法，取随机点，如果所述点在圆的交点中，则尝试计算相应的多边形.如果存在这样的多边形，则删除构成该多边形的圆心和交点.重复直到没有圆心或交点.这将避免最终计算外部"变量.多边形或内部"多边形，但会引入新问题(在潜在的高运行时间之外)例如 在单个交点中相交的 2 个以上的圆可以在计算一个多边形时移除所述交点，但对于下一个.

最终，我的问题是:如何计算这样的多边形?

PS:作为计算多边形后的额外问题，在计算某个圆切片的面积时，如何知道在 theta 和 2PI - theta 之间考虑哪个角度?

解决方案

一旦我们按照正确的顺序获得了多边形的点，计算面积就是一个 不太难.

实现这一目标的方法是利用平面二元性.请参阅有关图表的双连接边列表表示的维基百科文章，但要点是，给出右面在多边形内的有向边，该多边形中的下一个有向边是前一个有向边的相反方向，按顺时针顺序具有相同的头部.

因此，我们将问题简化为找到多边形联合的定向边并确定每个头部的正确顺序.我们实际上是先解决后一个问题.圆盘的每个交叉点都会产生一个四边形.我们称中心C和D以及交点A和B.不失一般性，假设以C为中心的圆盘不小于以D为中心的圆盘.由A→C←B形成的内角小于180度，所以该三角形的有符号面积为负当且仅当 A→C 在 C 周围顺时针顺序在 B→C 之前，反过来当且仅当 B→D 在 D 周围顺时针顺序在 A→D 之前.

现在我们确定哪些边实际上是多边形边界.对于一个特定的磁盘，我们在它的中心周围有一堆角度间隔(每个间隔从第一个端点到第二个端点扫过顺时针扇区).我们需要的是计算段联合的常见面试问题的更复杂版本.通常的扫描线算法在扫描打开端点时增加覆盖计数并在扫描关闭端点时减少覆盖计数可以在这里工作，我们需要将计数初始化为不为 0 而是初始化为起始角度的适当覆盖计数.

有一种方法可以不用三角学，只需减法、行列式和比较即可完成所有这些工作.

This question is an extension on some computation details of this question.

Suppose one has a set of (potentially overlapping) circles, and one wishes to compute the area this set of circles covers. (For simplicity, one can assume some precomputation steps have been made, such as getting rid of circles included entirely in other circles, as well as that the circles induce one connected component.)

One way to do this is mentioned in Ants Aasma's and Timothy's Shields' answers, being that the area of overlapping circles is just a collection of circle slices and polygons, both of which the area is easy to compute.

The trouble I'm encountering however is the computation of these polygons. The nodes of the polygons (consisting of circle centers and "outer" intersection points) are easy enough to compute:

And at first I thought a simple algorithm of picking a random node and visiting neighbors in clockwise order would be sufficient, but this can result in the following "outer" polygon to be constructed, which is not part of the correct polygons.

So I thought of different approaches. A Breadth First Search to compute minimal cycles, but I think the previous counterexample can easily be modified so that this approach results in the "inner" polygon containing the hole (and which is thus not a correct polygon).

I was thinking of maybe running a Las Vegas style algorithm, taking random points and if said point is in an intersection of circles, try to compute the corresponding polygon. If such a polygon exists, remove circle centers and intersection points composing said polygon. Repeat until no circle centers or intersection points remain. This would avoid ending up computing the "outer" polygon or the "inner" polygon, but would introduce new problems (outside of the potentially high running time) e.g. more than 2 circles intersecting in a single intersection point could remove said intersection point when computing one polygon, but would be necessary still for the next.

Ultimately, my question is: How to compute such polygons?

PS: As a bonus question for after having computed the polygons, how to know which angle to consider when computing the area of some circle slice, between theta and 2PI - theta?

解决方案

Once we have the points of the polygons in the right order, computing the area is a not too difficult.

The way to achieve that is by exploiting planar duality. See the Wikipedia article on the doubly connected edge list representation for diagrams, but the gist is, given an oriented edge whose right face is inside a polygon, the next oriented edge in that polygon is the reverse direction of the previous oriented edge with the same head in clockwise order.

Hence we've reduced the problem to finding the oriented edges of the polygonal union and determining the correct order with respect to each head. We actually solve the latter problem first. Each intersection of disks gives rise to a quadrilateral. Let's call the centers C and D and the intersections A and B. Assume without loss of generality that the disk centered at C is not smaller than the disk centered at D. The interior angle formed by A→C←B is less than 180 degrees, so the signed area of that triangle is negative if and only if A→C precedes B→C in clockwise order around C, in turn if and only if B→D precedes A→D in clockwise order around D.

Now we determine which edges are actually polygon boundaries. For a particular disk, we have a bunch of angle intervals around its center from before (each sweeping out the clockwise sector from the first endpoint to the second). What we need amounts to a more complicated version of the common interview question of computing the union of segments. The usual sweep line algorithm that increases the cover count whenever it scans an opening endpoint and decreases the cover count whenever it scans a closing endpoint can be made to work here, with the adjustment that we need to initialize the count not to 0 but to the proper cover count of the starting angle.

There's a way to do all of this with no trigonometry, just subtraction and determinants and comparisons.

这篇关于如何从一组重叠的圆计算多边形组?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！