は、私は私のクラスの次のデータ構造を有する掃引アルゴリズム

Question

用エッジを注文：

typedef vector< vector<int> > MxInt2d; 
typedef vector< vector<double> > MxDouble2d; 

class QSweep{ 
public: 
.... 
static MxDouble2d myPoints_; 
MxDouble2d myEdges_; 
} 

ここで：各点は3つのコンポーネント、従ってインデックスによって与えられ、XおよびY座標を有する 。 各エッジは、そのソースindex-edge [0]とその宛先index-edge [1]によって与えられます。ここで、edge [0]、edge [1]はmyPointsデータ構造体のインデックスです。 私は変数myEdges_にこの辺を持っています。

掃引アルゴリズムを適用して良好な結果と良い結果（エッジのすべての交点）を得るためには、このエッジをどのように配置する必要があるのですか。 これまでのところ、私はエッジを配置するための2つの異なる基準を持っていますが、どれも良い結果と良い結果しか得ていません（どちらも交差点を取得しないか、 ）。ここ

は私の基準である。

基準1（アイデア）：X、それらのエッジの座標によって

• [0]の座標（2つの縁のXは異なっているときに限り）

• （対応するスロープによって）（xのedのx座標が0であれば、

• ） gesとエッジのyは等しい）。

基準1（コード）：

class QSweep{ 
    public: 
    .... 
static MxDouble2d myPoints_; 
MxDouble2d myEdges_; 

class order{ 
public: 
    bool operator() (const vector<int>& edge1, const vector<int>& edge2){ 
      //std::cout<<"inside sort"<<endl; 
      //3 sort criteria 
      return (myPoints_[edge1[0]][0]<myPoints_[edge2[0]][0])|| 
         (myPoints_[edge1[0]][0]==myPoints_[edge2[0]][0]&& 
         myPoints_[edge1[0]][1]<myPoints_[edge2[0]][1]) 
        || 
        (myPoints_[edge1[0]][0]==myPoints_[edge2[0]][0]&& 
         myPoints_[edge1[0]][1]==myPoints_[edge2[0]][1]&& 
        getSlope(myPoints_[edge1[0]][0],myPoints_[edge1[0][1], 
            myPoints_[edge1[1]][0],myPoints_[edge1[1]][0]) 
        < 
         getSlope(myPoints_[edge2[0][0],myPoints_[edge2[0][1],  
            myPoints_[edge2[1]][0],myPoints_[edge2[1]][0])); 
        } 
}; 

static double getSlope(double a, double b, double c, double d); 
}; 

基準2（アイデア）：X、それらのエッジの座標によって

• [0]の座標（2のXはIFFエッジが異なる）

• 対応するスロープ（2つのエッジのxが等しい場合）

• のエッジ[1]座標のy座標（エッジのxとエッジの傾きが等しい場合）。

基準2（コード）：

class QSweep{ 
public: 
.... 
static MxDouble2d myPoints_; 
MxDouble2d myEdges_; 
class order{ 
public: 
    bool operator() (const vector<int>& edge1, const vector<int>& edge2){ 
    return ((myPoints_[edge1[0]][0]<myPoints_[edge2[0]][0])|| 
     ((myPoints_[edge1[0]][0]==myPoints_[edge2[0[0])&& 
      (getSlope(myPoints_[edge1[0]][0],myPoints_[edge1[0]][1], 
         myPoints_[edge1[1]][0],myPoints_[edge1[1]][1]) 
      <getSlope(myPoints_[edge2[0]][0],myPoints_[edge2[0]][1], 
         myPoints_[edge2[1]][0],myPoints_[edge2[1]][1])))|| 
    ((myPoints_[edge1[0]][0]==myPoints_[edge2[0]][0])&&( 
      getSlope(myPoints_[edge1[0]][0],myPoints_[edge1[0]][1], 
         myPoints_[edge1[1[0],myPoints_[edge1[1]][1])== 
      getSlope(myPoints_[edge2[0]][0],myPoints_[edge2[0]][1], 
        myPoints_[edge2[1]][0],myPoints_[edge2[1]][1])) 
      &&(myPoints_[edge1[1]][1]<myPoints_[edge2[1]][1])) 
       ); 
} 

}。

これは実際には複雑に見えますが、私のアルゴリズムでこれらの基準を試してみましたが、すべての交点を取得していません。だから私はいくつかの交差点を検出するので、スイープアルゴリズムのための私のエッジのための順序の基準は良くないと推測している。 は、私たちの質問を行うには直接 madalina

Answer 1

何も、事前にご提案（または小さな意見）ありがとうございませんが、私はあなたが簡単なポイントを使用した場合、あなたのコードが読みやすく、多くの1つの地獄であることを示唆していることができますXY座標を表す構造体？次のようなものがあります。

template <typename T> struct Point { 
    Point(const T & ax, const T & ay) : x(ax), y(ay) {} 
    T x, y; 
}; 

となります。次に、Pointの1次元ベクトルを作成し、配列インデックスではなくx &という名前を使用できます。

だけの提案 - あなたは通常、あなたのポイントに辞書式ソート使用sweeplineアルゴリズムについて...

Answer 2

を無視して自由に感じる：あなたは2点のX成分場合、Xによって

• ソート比較は等しい、代わりにYでソートします。 3Dでは、Z成分などに拡張することができます。

しかし、並べ替えが問題の根源（疑似交差点と欠落交差点）であるかどうかは疑問です。

スイープアルゴリズムは、丸め誤差の影響を受けやすい非常にです。あなたの計算が有効な結果を得るのに十分な精度を保持していることを絶対に確かめるまで、浮動小数点演算を行うことはできません。

は、この種の問題に詳細（およびソリューション）のために、このウェブページを見てみましょう：

http://www.cs.cmu.edu/~quake/robust.html

幸運を。

Btw - Bentley-Ottmann交差スキャンを書いていますか？交点を挿入すると、フロートの有限精度のために交差するエッジの傾きがわずかに変化するため、これらは他のスイープアルゴリズムよりもさらに敏感です。