14

互いに交差しない単純なポリゴンがいくつかありますが、一部のポリゴンは他のポリゴンに埋め込まれている可能性があります。

例えば：

+--------------------------------------------+
|                                            |
|   +----------------+          +--------+   |
|   |                |         /         |   |
|   |   +--------+   |        /          |   |
|   |   |        |   |       /  +----(2)-+   |
|   |   |        |   |      /   |            |
|   |   +----(3)-+   |     /    |   +---+    |
|   |                |    +-----+   |   |    |
|   +------------(2)-+              +(2)+    |
|                                            |
+----------------------------------------(1)-+

すべてのポリゴンの「深さ」を調べる方法は? つまり、ポリゴンがいくつのポリゴンに囲まれているかを調べる方法は? 「深さ」は括弧内の数字です。

ポリゴンのポイントが他のすべてのポリゴンの内側にある回数を数えることはできますが、これには二次的な複雑さがあります。これらの深さをより速く計算するにはどうすればよいですか?

4

5 に答える 5

2

ポリゴンをある種の空間ルックアップ構造(たとえば、ポリゴンの最小境界四角形に基づくR ツリー) に配置します。次に、O( n log n )で求めている包含​​関係を計算できるはずです。（ポリゴンの最小外接長方形の多くが重なっている病理学的なケースでない限り、これはあなたの説明に基づいている可能性は低いと思われます。）

編集して追加: もちろん、R ツリーに依存して、あるポリゴンが別のポリゴンの内側にあるかどうかを判断する必要はありません (これは、最小境界四角形に基づいているため、概算しか得られません)。R ツリーを使用して包含候補を低コストで特定し、それを高価な方法で検証します (1 つのポリゴン内のポイントが別のポリゴン内にあることを確認します)。

于 2013-01-18T00:46:35.900 に答える
0

(このアプローチは、@GarethRees のものと同様の考え方に従います。最初に、包含をチェックする必要のないポリゴンのペアを安価に見つけます。チェックする必要があるペアの数が受け入れられるようになったら、正確な (高価な) ジオメトリを実行します。小切手。）

ポリゴンごとに外接する四角形、つまり左、右、上、下を計算するのは簡単なので、最初に計算してみましょう。左の例:p.L = min { x : (x,y) is a vertex of p }時間はポイント数に比例します。

各ポリゴンを互いに比較する必要がないように、エリアを 2x2 グリッドに分割できます。領域の幅と高さがそれぞれ と で与えられると仮定すると、Dx9つのDyセットtop,bottom,left,right,topright,topleft,bottomright,bottomleft,restを作成して次の操作を実行できます。

for p in polygons:
    in_top    = p.B > Dy/2
    in_bottom = p.T < Dy/2
    in_left   = p.R < Dx/2
    in_right  = p.L > Dx/2 
    if in_top:
        if in_left:
            add p to topleft
        elsif in_right:
            add p to topright
        else:
            add p to top
    elsif in_bottom:
        if in_left:
            add p to bottomleft
        elsif in_right:
            add p to bottomright
        else:
            add p to bottom

    if in_right and not (in_top or in_bottom):
        add p to right
    elsif in_left and not (in_top or in_bottom):
        add p to left

    if not (in_top or in_bottom or in_left or in_right):
        add p to rest

これも線形時間です。各ポリゴンは、最も「密に」含まれるセクターにビニングされています。これによってあなたは何を得ましたか？たとえば、ポリゴンpのleft場合、 set との包含関係はあり得ないことがわかっているrightので、それらを比較する必要はありません。同様に と の間bottomleft、rightとbottomleftなどtopleft。あなたの例では次のようになります。

                      Dx/2
+----------------------|---------------------+
|                      |                     |
|   +----------------+ |        +--------+   |
|   |                | |       /         |   |
|   |   +--------+   | |      /          |   |
|___|___|________|___|_|____ /__+===d(2)=+___|_ Dy/2
|   |   |        |   | |    /   |            |
|   |   +---b(3)-+   | |   /    |   +---+    |
|   |                | |  +-----+   |   |    |
|   +-----------c(2)-+ |            e(2)+    |
|                      |                     |
+----------------------|----------------a(1)-+

そうrest = {a}, top = {}, bottom = {}, left = {b,c}, right = {d}

topleft = {}, topright = {}, bottomleft = {}, bottomright = {e}

したがって、基本的には、(高価な正確なチェックを使用して) 、b、cおよび他のすべてと比較する必要があります。包含は推移的であるため、 includes 、およびincludesに気付いた場合、 includesかどうかを確認する必要はありません。deaacbacab

もう 1 つのポイントは、上記の推論を再帰的に適用できることです。たとえば、セットtoprightが大きすぎて好みに合わないとします。次に、そのサブリージョンをさらに分割することで、同じ手法を適用できます (簿記を正しく行う必要があるだけです)。

于 2013-01-29T14:17:02.220 に答える
0

ステップ 1: ポリゴンを同じ方向、たとえば反時計回りに向けます。

ステップ 2: 総巻き数を計算するために「深さ」を計算する必要がある任意の点 (x, y) について。これにはさまざまな方法があります。実際に最も速いのは、(x, y) を起点とする水平 (または垂直) 光線間の交差の SIGNED 数を計算することです。

特に、各ポリゴンの深さは、その頂点の深さになります。

于 2013-08-27T21:00:41.923 に答える
0

比較演算子として別のポリゴンの内側にあるかどうかのテストを使用して、ポリゴンをソートすることでうまくいくようです。

ステップ1

多角形間の関係 '<' を次のように定義するとします。A が B の内側にある場合、A < B。A < B かつ B < C の場合、A < C となります (つまり、多角形 A が B の内側にあり、B が B の内側にある場合)。 C の内側にある場合、A は C の内側にある必要があります)。これで、任意のポリゴン間に厳密な弱い順序付けができました。

[編集: ある種の非凸多角形内点テストを使用する必要がありますが、おそらく既にそれを行っています。]

ステップ2

お気に入りの比較ベースの並べ替えアルゴリズムを使用して、この比較に従ってポリゴンを並べ替えます。たとえば、マージ ソートには、O(nlogn) 比較の最悪の場合の時間の複雑さがあり、n はポリゴンの数です。

[編集: これは二次的な複雑さを取り除くため、重要なステップです。]

ステップ 3

「最大の」(つまり、最も外側の) 要素が、ポリゴンの並べ替えられた配列の最初にあることを確認してください。(これを達成するために必要に応じてリストを逆にします - ポリゴンの数に比例します)。

ステップ 4

これで、「最大」(つまり最も外側) のポリゴンが最初の要素になるはずです。

[編集: 実際、ポリゴンは深さに従ってソートされています。ただし、並べ替えが安定しているかどうかによっては、深度が同じ 2 つのポリゴンが異なる順序で表示される場合があります。これは私たちには関係ありません。私たちが興味を持っているのは、深さの変化です。]

次のように、各ポリゴンに深さを割り当てます。まず、それぞれの深さを 0 に初期化します ([編集: 例に従って 1 に初期化])。次に、ソートされたリストを繰り返し処理しますが、今回は各要素 p を次の要素 p+1 とのみ比較します。(p+1 < p) が true の場合、p+1 の深さをインクリメントします。そうでない場合は、p+1 の深さを p の深さと同じに設定します。

于 2013-03-29T21:44:47.467 に答える