-1

我正在构建一个与 Google Places API 交互的程序，以识别美国县内给定类型的所有机构。谷歌接受半径形式的搜索——所以为了覆盖整个区域，我正在按顺序构建我的搜索半径。但是，此算法会创建很多我想过滤掉的重叠圆圈。所以：

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

我已经可以判断一个圆圈是否被另一个圆圈包围 - 我的问题是其中很多被其他几个圆圈包围。

有人询问我现有的代码——我目前有测试一个圆圈是否与另一个圆圈完全重叠的代码——而不是它们的组合。但这就是我所拥有的。您可以看到，如果它与其他 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
4

2 回答 2

0

您可以将此作为磁盘联合问题来解决。这个问题与Alpha 形状理论有关，可以通过构建加权（加法）Voronoi 图来解决，该图可以O(n Log(n))针对n磁盘及时执行。

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

您将不得不使用 CGAL 等高级软件包，因为该算法远非简单。

如果您可以使用近似解决方案并且旨在简化编程，只需以合适的分辨率将磁盘绘制在空白图像中。然后检查绘制单个磁盘是否达到新像素。

这种方法成本很高，因为您需要处理的像素数量等于磁盘的总面积。

作为难度和效率之间的折衷，混合解决方案也是可能的。

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

于 2015-10-08T19:56:31.890 回答
-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")
于 2015-10-08T19:01:21.443 回答