-1

私は、Google Places API とやり取りして、米国郡内の特定のタイプの施設をすべて識別するプログラムを構築しています。Google は半径の形で検索を受け入れます。そのため、エリア全体をカバーするために、検索半径を順次構築しています。ただし、このアルゴリズムは、フィルターで除外したい重複する円を多数作成します。そう：

それぞれの中心と半径を含む円のリストが与えられた場合、単一の円が他の円の組み合わせによって完全に覆われているかどうかをどのように判断できますか?

円が別の単一の円に囲まれているかどうかは、すでにわかります。私の問題は、それらの多くが他のいくつかの円の組み合わせによって囲まれていることです。

誰かが私の既存のコードを求めました - 私が現在持っているコードは、円が別の円と完全に重なっているかどうかをテストします - それらの組み合わせではありません。しかし、ここに私が持っているものがあります。他の 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

これは、ディスク ユニオンの問題として対処できます。この問題は、アルファ形状の理論に関連しており、ディスクに間に合うように実行できる加重 (加算) ボロノイ図の構築によって解決できます。O(n Log(n))n

この構造は次のように使用できます。リストからディスクの結合を計算します。次に、単一のディスクをこのユニオンに追加します。変更がない場合は、1 つのディスクが含まれます。

アルゴリズムは単純ではないため、CGAL などの高度なパッケージを使用する必要があります。

おおよその解決策があり、プログラミングの容易さを目指している場合は、ディスクを適切な解像度で空白のイメージにペイントするだけです。次に、単一の円盤が新しいピクセルに達するかどうかを確認します。

このアプローチは、ディスクの総面積に等しい数のピクセルを処理する必要があるため、コストがかかる可能性があります。

難易度と効率の妥協点として、混合ソリューションも可能です。

垂直方向の解像度を選択し、等距離の水平線で平面をクロスハッチングします。それらは、線分に沿ってすべてのディスクと交差します。水平ごとにセグメントのリストを保持し、新しいディスクを追加するときにセグメントの結合を実行するのは簡単なことです。(nセグメントの結合は、オーバーラップを並べ替えてカウントすることで簡単に実行できます。)

于 2015-10-08T19:56:31.890 に答える
-1

テスト対象の円 A を考えてみましょう。

あなたの計算がどれほど正確である必要があるかはわかりませんが、A の円周を 100 ポイントで表すことで十分であると仮定しましょう。

インポート数学

#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 に答える