1

私は次の2つのクラスを持っています

public class PointClass
{
    double x, y, z;
}

と

public class PolyLineClass
{
    PointClass startPoint;
    PointClass endPoint;
}

および PolyLineClasses の配列

polyLineArray[];

polyLineArray 内のすべての線を何らかの順序で接続すると、自己交差しない閉じた曲線が得られると仮定します。

例えば

                  startPt  endPt
polyLineArray[0]: (0,0,0) (1,0,0)
polyLineArray[1]: (0,1,0) (0,0,0)
polyLineArray[2]: (1,1,0) (0,1,0)
polyLineArray[3]: (1,0,0) (1,1,0)

配列を 0->3->2->1 の順序でトラバースすると、閉じた曲線 (この単純なケースでは正方形) が作成されます。現在、私が持っているのは次のアルゴリズムです。

1) int i = 0; 
2) Get the endPt of polyLineArray[i];
3) search through the array for an element with index j such that 
   polyLineArray[i].endPoint == polyLineArray[j].startPoint.
4) i = j; Repeat from step2 until all elements in the array have been visited.

上記のアルゴリズムは O (怖い) です。ソートを行うためのより効率的な方法はありますか? 言語が重要な場合、私は c# でコーディングしています。

4

2 に答える 2

1

クラスを作成する

public class EndPoint {
    PointClass point ;
    int lineIndex ;
}

と配列

EndPoint endPoints[] ;

その長さは の 2 倍ですpolyLineArray。

e線の終点ごとにiEndPoint を作成し、それを配列{e,i}に追加します。endPoints次に、この配列をpoint要素順に並べ替えます。(ポイントはコンポーネントごとにソート/比較できます)。

並べ替えが完了したら、配列を走査して EndPoint を選択できます。これらは、ポイントが等しいペアになりますが、ライン インデックスはそのポイントで結合するラインを指します。並べ替えられた EndPoint 配列をたどって、リンクされた一連の PolyLines を拾うことができます。

于 2013-05-14T18:53:02.620 に答える