如何判断一个圆是否被其他几个圆包围

Question

我正在构建一个与googleplacesapi交互的程序，以识别美国郡内所有给定类型的机构。谷歌接受半径形式的搜索，所以为了覆盖整个区域，我把搜索半径从一个半径到另一个半径依次建立起来。但是，这个算法创建了很多重叠的圆，我想过滤掉。所以：

给定一个圆的列表，每个圆的中心和半径，我如何判断一个圆是否完全被其他圆的组合所覆盖？你知道吗

我已经知道一个圆是否被另一个圆包围了——我的问题是，很多圆都被其他几个圆的组合包围了。你知道吗

有人问我现有的代码-代码我目前有测试，如果一个圈是完全重叠的另一个圈-不是他们的组合。但这就是我所拥有的。你可以看到，我正在通过排除它是否与其他20个圆重叠来近似当前的问题，在这一点上，它可能包含：

def radiusIsInsidePreviousQuery(self, testQuery):
    newSearchCoordinates = (testQuery['center']['lat'], testQuery['center']['lng'])
    alreadyBeenSearched = False

    numberOfIntersectingCircles = 0

    for queryNumber in self.results.keys():
        previousQuery = self.results[queryNumber]
        previousSearchCoordinates = (previousQuery['center']['lat'], 
                                     previousQuery['center']['lng'])

        centroidDistance = VincentyDistance(newSearchCoordinates, 
                                            previousSearchCoordinates)

        centroidDistanceMeters = centroidDistance.meters
        newQueryRadius = testQuery['radius']
        fullSearchDistance = centroidDistanceMeters + newQueryRadius

        #If the full search distance (the sum of the distance between
        #the two searches' centroids and the new search's radius) is less
        #than the previous search's radius, then the new search is encompassed
        #entirely by the old search.
        previousQueryRadius = previousQuery['radius']
        if fullSearchDistance <= previousQueryRadius:
            print "Search area encompassed"
            alreadyBeenSearched = True
        elif centroidDistanceMeters < newQueryRadius + previousQueryRadius:
            numberOfIntersectingCircles += 1
        elif self.queriesAreEqual(testQuery, previousQuery):
            print "found duplicate"
            alreadyBeenSearched = True   

    #If it intersects with 20 other circles, it's not doing any more good.
    if numberOfIntersectingCircles > 20:
        alreadyBeenSearched = True    

    return alreadyBeenSearched 

Answer 1

让我们考虑要测试的圆A

我不知道你的计算需要多精确，但假设用100点表示A的周长就足够了。你知道吗

导入数学

#Circle to be tested

Circle_A = (3,2,1)
resolution = 100

circumference_A = []
for t in xrange(resolution):
    step = (2*math.pi)/resolution 
    x = Circle_A[0]
    y = Circle_A[1]
    r = Circle_A[2]
    circumference_A.append((x+(r*math.cos(t*step)),y+(r*math.sin(t*step))))

# Given list of circles (we need to know center and radius of each).
# Put them in a list of tuples like this (x,y,r)

ListOfCircles=[(5,2,2),(2,4,2),(2,2,1),(3,1,1)]

# Test:Check if all the points of circumference A are not < r from each one of the circles in the list.

overlap_count = 0
for p in circumference_A:
    print('testing p:',p)
    for c in ListOfCircles:
        distance = math.sqrt(math.pow(p[0]-c[0],2) + math.pow(p[1]-c[1],2))
        if distance < c[2]:
            overlap_count += 1
            print('overlap found with circle',c)
            break
        else:
            print('distance:',str(distance))
            print('origin:',c)



if overlap_count == resolution:
    print("Circle A is completely overlapped by the ListOfCircles")
else:
    print(str(overlap_count)+" points out of "+ str(resolution) + " overlapped with the composed area")

Answer 2

您可以将此作为磁盘联合问题来解决。这个问题与Alpha shapes理论有关，可以通过构造一个weighted (additive) Voronoi diagram来解决，这个O(n Log(n))可以在n磁盘的O(n Log(n))时间内执行。你知道吗

可以按如下方式使用此构造：从列表中计算磁盘的并集。然后将单个磁盘添加到此联合。如果没有变化，则包含单个磁盘。你知道吗

您将不得不使用一个高级软件包，比如CGAL，因为算法远不简单。你知道吗

---

如果你可以用一个近似的解决方案，并着眼于易于编程，只需在一个空白的图像中画一个合适的分辨率磁盘。然后检查单个磁盘的绘制是否达到新像素。你知道吗

这种方法成本高昂，因为您需要处理的像素数等于磁盘的总面积。你知道吗

---

混合解决方案也可以作为难度和效率之间的折衷方案。你知道吗

选择垂直分辨率并用等距水平线交叉填充平面。它们将沿着一条线段与每个圆盘相交。为每个水平磁盘保留一个段列表，并在添加新磁盘时执行段的并集是一件容易的事情。（通过对重叠进行排序和计数，n段的并集很容易实现。）