7

n頂点によって定義された穴と自己交差のないポリゴン（つまり、単純なポリゴン）があるとします。vこのポリゴンの反射頂点を選択します。

u頂点から「見える」同じポリゴンの他の頂点を見つけたいのですがv。v目に見えるとは、ポリゴンとポリゴンの間の線分がu完全にポリゴンの内側にあることを意味します。

時間内にそれを行うためのアルゴリズムはありO(N)ますか？O(N)目に見えるすべての頂点を時間内に見つけることができるアルゴリズムはありますか？

簡単な調査によると、特定のポリゴンとこのポリゴン内の任意のポイントについて、可視性ポリゴンをで構築できますO(N)。単一の可視頂点を見つけるのはさらに簡単なはずだと思います。

4

5 に答える 5

7

この問題は30年前に解決されました。

ElGindy and Avis、「ポイントから可視性ポリゴンを計算するための線形アルゴリズム」、J。Algorithms 2、1981 、 p。186--197。

Joe＆Simpsonによる1985年の非常に優れた論文、「ある点からの単純なポリゴンの可視性」があり、慎重に検証された擬似コードを提供しています:( PDFダウンロードリンク）。それ以来、これは確かに多くの言語で何度も実装されてきました。たとえば、このトピックに関するウィキペディアの記事にリンクがあります。

于 2012-11-21T02:08:59.497 に答える
2

アルゴリズムが正しくなかったため、アルゴリズムを変更しました。今回はすべてのケースをカバーすることを願っています！。

反射aから始めて、次の頂点をa'とし、辺a 'でa --a'と交差するエッジが見つかるまでポリゴンをたどり、bをこのエッジと線a--aとの交点とします。 'およびcエッジの終点（a--cの右側の終点）。

次に、ポリゴンのエッジを通過し続けます。エッジがセグメントa--bと左から右に交差する場合は、 bを新しい交点に設定し、 cを終了頂点に設定します。終了すると、三角形a--b--cができます。ここで、 cからやり直して、すべての頂点を調べて、三角形a--b--cの内側にあるかどうかを確認します。その場合は、cを新しい頂点に設定します。最後に、a--cはポリゴンの対角線です。

これは、反射点aが次の場所にあることを前提としたCでの実装ですP[0]。

struct pt {
    double x,y;
    friend pt operator+(pt a, pt b){a.x+=b.x; a.y+=b.y; return a;}
    friend pt operator-(pt a, pt b){a.x-=b.x; a.y-=b.y; return a;}
    friend pt operator*(pt a, double k){a.x*=k; a.y*=k; return a;}
    bool leftof(pt a, pt b) const{
        // returns true if the *this point is left of the segment a--b.
        return (b.x-a.x)*(y-a.y) - (x-a.x)*(b.y-a.y) > 0;
    }
};
pt intersect(pt a, pt b, pt c, pt d){// (see O'rourke p.222)
    double s,t, denom;
    denom = (a.x-b.x)*(d.y-c.y)+ (d.x-c.x)*(b.y-a.y);
    s = ( a.x*(d.y-c.y)+c.x*(a.y-d.y)+d.x*(c.y-a.y) )/denom;
    return a + (b-a)*s;
}
/**
    P is a polygon, P[0] is a reflex (the inside angle at P[0] is > pi).
    finds a vertex t such that P[0]--P[t] is a diagonal of the polygon.
**/
int diagonal( vector<pt> P ){
    pt a = P[0], b = P[1]; //alias
    int j=2;
    if( !b.leftof(a,P[j]) ){
        // find first edge cutting a--b to the right of b
        for(int k = j+1; k+1 < int(P.size()); ++k)
            if( P[k].leftof(a,b) && P[k+1].leftof(b,a) && b.leftof(P[k+1],P[k]) )
                j = k,
                b = intersect( a,b,P[k],P[k+1] );
        // find nearest edge cutting the segment a--b 
        for(int k = j+1; k+1 < int(P.size()); ++k)
            if( P[k].leftof(a,b) && P[k+1].leftof(b,a) &&
                a.leftof(P[k+1],P[k]) && b.leftof(P[k],P[k+1]) ){
                b = intersect( a,b,P[k],P[k+1] );
                j = k+1;
            }
    }
    for(int k = j+1; k+1 < int(P.size()); ++k)
        if( P[k].leftof(a,b) && P[k].leftof(b,P[j]) && P[k].leftof(P[j],a) )
            j = k;
    return j;
}
于 2012-11-20T00:15:04.403 に答える
0

Vで始まる頂点を通過し続け、表示されている頂点のリストを更新します。私が何も見逃していなければ、それはO（n）になります。

簡単にするために、Vをvisibleと呼びましょう。

私はそれを言葉で表現しようと1日試みましたが、失敗して擬似コードを使用しました:)

visible_vertices = {V}
for each next segment in counter-clockwise polygon traversal
  if segment is counter-clockwise (looking from V)
    if (visible_vertices.last -> segment.end) is counter-clockwise
      visible_vertices.add(segment.end)
  else
    while segment hides visible_vertices.last or segment.start=visible_vertices.last
      visible_vertices.remove_last
于 2012-11-18T07:01:41.613 に答える
0

O（n）時間で個々の頂点をテストできるため、 O（n ^ 2）ですべての頂点をテストできます。個々の頂点UがVから見えるかどうかをテストするには、 VとUの間に線を作成します。この線をLと呼びましょう。次に、 Lをテストして、ポリゴンのエッジのいずれかと交差するかどうかを確認します。そうでない場合、UはVから隠されません。含まれている場合、Uは隠されています。

さらに、次のようにLがポリゴン内にあるかどうかをテストできます。Vの入射エッジがE1とE2であると仮定します。E1とE2の間（これをa1と呼びます）およびE1とLの間（これをa2と呼びます）の符号付き角度を計算します。a2の符号はa1と同じである必要があり（つまり、LはE1の「同じ」側にあり、E2と同じ）、a2はa1よりも小さい必要があります（つまり、L 'は「E2 」の前にあります）。）。

LはVに入射するポリゴンのエッジと自明に交差するため、交差テストには注意してください。これらの交差点は無視してかまいません。

また、UがVに入射するエッジのいずれかを共有している場合、UはVから自明に見えます。

于 2012-11-17T11:02:22.823 に答える
0

ポリゴンの三角形分割を使用できます。

三角形分割があると仮定すると、三角形分割の関連する内部エッジを調べることで、頂点Tの可視頂点のセットを見つけることができます。具体的には、にアタッチされた三角形のセットがトラバースされ、内部エッジが識別された場合（2回表示されるもの！）、セットはを除くすべてのエッジ頂点になります。UVVUV

これは必ずしもからのすべての可視頂点ではなく、 （Vからの少なくとも1つの内部エッジである必要があります）Vのセットであることに注意してください。ただし、効率的です。訪問した三角形/エッジの数は、基本的に妥当な入力用です。|U| >= 0 O(m)mO(1)

もちろん、最初に三角形分割を作成する必要があります。制約付きドロネー三角形分割を組み込むことができる効率的なアルゴリズムがありますがO(n*log(n))、それは完全ではありませんO(n)。優れた制約付きDelaunay実装は、TriangleおよびCGALにあります。

于 2012-11-17T11:33:51.393 に答える