0

2D空間のエッジと頂点のこの大きなグラフがあります。大きなグラフは、C++ライブラリで計算された関数によって返されます。私はこのグラフを読み、それを使用してそのエッジのすべての交点（線のセグメント）を計算しています。スイープアルゴリズムを使用します。2つのエッジの交差を検出するために、いくつかの問題があります。2つのエッジが交差するかどうかをテストし、肯定的な場合はそれらの交差を計算して保持する4つの異なる方法があります。

  1. 2つのエッジがポリゴンの対角線であるかどうかをテストするもの。つまり、もう一方の線の方程式に挿入された一方の線のエッジの座標は、異なる符号を持っています。

  2. 毎回交差点を計算し、見つかった交差点が両方のセグメントの端点の間にあるかどうかを確認するもの。

  3. ただし、C++で実装されたこのリンクのコードです。

  4. この質問でJasonCohenによって提案された最初の方法を実装するもの 。

「問題はこの質問に帰着します：AからBとCからDの2本の線が交差しますか？それからあなたはそれを4回尋ねることができます（線と長方形の4つの辺のそれぞれの間）。

これを行うためのベクトル数学です。AからBへの線が問題の線であり、CからDへの線が長方形の線の1つであると仮定します。私の表記では、Axは「Aのx座標」であり、Cyは「Cのy座標」です。また、「*」は内積を意味します。たとえば、次のようになります。

A*B = Ax*Bx + Ay*By.
E = B-A = ( Bx-Ax, By-Ay )
F = D-C = ( Dx-Cx, Dy-Cy ) 
P = ( -Ey, Ex )
h = ( (A-C) * P ) / ( F * P )

このh番号が鍵です。hが0と1の間にある場合、線は交差します。そうでない場合、線は交差しません。F Pがゼロの場合、もちろん計算はできませんが、この場合、線は平行であるため、明らかな場合にのみ交差します。正確な交点はC+ Fhです。hが正確に0または1の場合、線は終点で接触します。これは「交差点」と見なすことができますが、適切と思われる場合はそうではありません。」

私が作成したデータ（2倍の値を持つ小さなデータ）については、実装された4つのメソッドすべてで良好な結果が得られました。大きなグラフのデータに対してC++で実装されたこれらのメソッドのいずれかを使用すると、毎回異なる結果が得られますが、良い結果は得られません。

  1. メソッドは、必要な交差点をはるかに多く返します（すべてのポイントがグラフ上にあります）が、取得するポイントが多すぎます。

  2. 何があっても常に0の交差点を取得します。

  3. 1よりもはるかに多くの交差点があります。

  4. いくつかの例では、グラフ上にない（交差点でさえない）ポイントを取得します。しかし、いくつかの例では、交点と他のいくつかの点を取得します。

問題がどこにあるのかわかりません。交差点を計算してテストする方法に関する提案やその他のアイデアは、歓迎される以上のものです。ありがとう、マダリーナ

4

6 に答える 6

2

必要なのは、4 つのメソッドの単体テストと、それらを徹底的にテストすることです。特に線分の交差点では、通常のすべての公差の問題に加えて、平行な勾配、端点の一致、完全または部分的なオーバーラップなど、多くのエンド ケースがあります (たとえば、「等しい勾配」とは正確には何を意味するのでしょうか?)。

物事をより小さく、よりテストしやすい単位に分割しないと、それを絞り込むのに苦労することになります。

于 2009-04-01T20:11:52.277 に答える
0

交点を計算するときに単調なエッジにスイープ ラインを使用しています (コンストラクター内でエッジを並べ替える並べ替え関数があり、それらをテストして、それらを適切に並べ替えます)、交点として頂点であるいくつかのポイントを取得しますが、このケースを排除するために多くのテストを行っていますが、いくつかのエッジがあります。

これは 4 番目の方法のコードです (これにより、これまでのところ最良の結果が得られますが、すべての交差点ではなく、他の交差点と比較して少なくともいくつかの良い交差点が得られます)。

//4 method
double* QSweep::findIntersection(edge_t edge1,edge_t edge2) {  
    point_t p1=myPoints_[edge1[0]];
    point_t p2=myPoints_[edge1[1]];
    point_t p3=myPoints_[edge2[0]];
    point_t p4=myPoints_[edge2[1]];

    double xD1,yD1,xD2,yD2,xD3,yD3,xP,yP,h,denom;
    double* pt=new double[3];

    // calculate differences  
    xD1=p2[0]-p1[0];  
    xD2=p4[0]-p3[0];  
    yD1=p2[1]-p1[1];  
    yD2=p4[1]-p3[1];  
    xD3=p1[0]-p3[0];  
    yD3=p1[1]-p3[1];    

    xP=-yD1;
    yP=xD1;
    denom=xD2*(-yD1)+yD2*xD1;
    if (denom==0) {
        return NULL;
    }
    else{
    h=(xD3*(-yD1)+yD3*xD1)/denom;
    }
    std::cout<<"h is"<<h<<endl;
    if ((h>0)&&(h<1)){
        pt[0]=p3[0]+xD2*h;  
        pt[1]=p3[1]+yD2*h;
        pt[2]=0.00;
    }
    else{
        return NULL;
    }

    // return the valid intersection  
    return pt;  
}

void QSweep:: intersection(){
    nbIntersections=0;
    double* vector;
    for (int i=2;i<myEdges_.size()-1;i++){
        vector=findIntersection(myEdges_[i-1],myEdges_[i]);
        if (vector!=NULL){
                nbIntersections++;
                myIntersections.push_back(vector);
                swap(myEdges_[i-1], myEdges_[i]);
        }
    }
}

交差関数は常に同じなので、findIntersection関数を見つけるだけです。

1 と 2 の方法では、次のバージョンのfindIntersection関数を使用しています。

double* QSweep::computeIntersection(double m1, double b1, double m2, double b2){
    double* v=new double[3];

    v[0]= (b2-b1)/(m1-m2);
    v[1]= (m1*b2-m2*b1)/(m1-m2);
    v[2]=0.00;
    return v;
    }

    double* QSweep::findIntersection(edge_t edge1, edge_t edge2){


    //equation for the support line of the first edge

    double a=myPoints_[edge1[0]][0];
    double b=myPoints_[edge1[0]][1];
    double c=myPoints_[edge1[1]][0];
    double d=myPoints_[edge1[1]][1];
    double m1=getSlope(a,b,c,d);
    double b1=getYIntercept(a,b,c,d);

    double x=myPoints_[edge2[0]][0];
    double y=myPoints_[edge2[0]][1];
    double s=myPoints_[edge2[1]][0];
    double t=myPoints_[edge2[1]][1];
    double m2=getSlope(x,y,s,t);
    double b2=getYIntercept(x,y,s,t);
    double* vector;

    double line2InLine1=evalEqnLineD(myPoints_[edge2[0]],edge1);
    double line2InLine1New=evalEqnLineD(myPoints_[edge2[1]],edge1);
    double line1InLine2=evalEqnLineD(myPoints_[edge1[0]],edge2);
    double line1InLine2New=evalEqnLineD(myPoints_[edge1[1]],edge2);

    if (m1==m2){
        return NULL;
    }
    else{

            if ((line1InLine2*line1InLine2New)<0 &&   (line2InLine1*line2InLine1New)<0){
            vector=computeIntersection(m1,b1,m2,b2);

            if ((vector[0]>a && vector[0]<c)&&(vector[0]>x && vector[0]<s)){
                return vector;
            }
            else{
                return NULL;
            }
        }
        else{
            return NULL;
        }
    }
    return vector;
}

最初からやり直して、自分が求める交点の共通点を見ていきます。いくつかのテストでも厳しいですが、良い交点さえ得られませんが、グラフ上の他の点は得られないので、本当に混乱しています.

于 2009-04-02T08:53:59.340 に答える
0

コードを見ることができずに言うのは難しいですが、浮動小数点値で堅牢性の問題が発生しているのではないかと思います。整数ポイントを使用したり、浮動小数点値の共通ビットを削除するなど、ある種の堅牢性を強化したりすることを検討しましたか?

GEOS ( http://trac.osgeo.org/geos/ )と呼ばれるオープン ソースのジオメトリ ライブラリがあり、データ セットをテストするのに役立ちます。GEOS には、整数グリッドへのスナップ丸めを実行し、共通ビットを削除して、堅牢性の問題が発生しているかどうかを判断するのに役立つアルゴリズムもあります。さらに注目すべきは、GEOS が同次空間で点と線の双対性を使用して交点を計算する方法です (これは、あなたが説明する内積投影法が数学的に同等であるかどうかはわかりません)。

余談ですが、エッジのグラフの交点を計算するための私のお気に入りのソリューションは、単調なエッジのチェーンと組み合わせてスイープラインを使用することです。モノトーン チェーンを使用すると、チェーンが交差しないため、多くのエッジ交差テストを省略できます。これが GEOS の機能です。

于 2009-04-01T20:48:56.010 に答える
0

なぜ車輪を再発明するのですか？

Boostに依存して処理できる場合は、サンドボックスの GTL ライブラリをチェックアウトします。これをダウンロードする方法については、wikiを参照してください (手順はフロント ページにあります)。

GTL ライブラリは、データ構造のあらゆる実装に役立ちます (つまり、データ構造とアルゴリズムが直交する STL の精神に基づいて設計されています)。コードは高速かつ正確です。できればチェックしてください。

于 2009-04-02T15:37:03.547 に答える
0

Boost.Geometry (別名 Generic Geometry Library)を試してみてください。

于 2010-01-25T23:23:54.883 に答える