arêtes de commande pour l'algorithme de balayage

Question

I ont les structures de données suivantes dans ma classe:

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

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

où: Chaque point a 3 composants, étant ainsi donnée par un index, x, et une coordonnée y; Chaque arête est donnée par son arête-index source [0] et son arête-index de destination [1], où arête [0], arête [1] sont des index de la structure de données myPoints). J'ai ces bords dans ma variable myEdges_.

La question est la suivante: Comment on doit arranger ces arêtes pour appliquer l'algorithme de balayage et obtenir les bons résultats et les bons résultats seulement (c'est-à-dire toutes les intersections des arêtes). Jusqu'à présent j'ai deux critères différents pour arranger les arêtes, mais aucun ne me donne les bons résultats et seulement les bons résultats (soit je n'obtiens pas toutes les intersections, soit je reçois les intersections plus quelques autres points qui ne sont pas des intersections).

Voici mes critères:

critères 1 (idée):

• par la coordonnée x de leur bord [0] coordonner (IFF les x de 2 bords sont différents)

• par la coordonnée y de leur coordonnée de bord [0] (si les x de 2 arêtes sont égaux)

• par leurs pentes correspondantes (si les x de ed ges et les y de bords sont égaux).

critères 1 (code):

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); 
}; 

critères 2 (idée):

• par la coordonnée x de leur arête [0] de coordonnées (ssi les x de 2 les arêtes sont différentes)

• par leurs pentes correspondantes (si les x de 2 arêtes sont égaux)

• par la coordonnée y de leur coordonnée de bord [1] (si les x des arêtes et les pentes des arêtes sont égaux).

critères 2 (code):

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])) 
       ); 
} 

};

Oui, cela semble vraiment compliqué, j'ai essayé ces critères sur mon algorithme et je n'obtiens pas toutes les intersections. Donc je devine que les critères d'ordre de mes arêtes pour l'algorithme de balayage ne sont pas bons, parce que je détecte certaines intersections mais pas d'autres. Merci pour vos suggestions (ou petits opinions) à l'avance, madalina

Answer 1

rien à faire directement avec notre question, mais puis-je suggérer que votre code serait un enfer de beaucoup plus lisible si vous avez utilisé un simple point structure pour représenter les coordonnées XY?quelque chose comme:

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

serait un début. Vous pouvez ensuite créer des vecteurs 1-demensioned de Point, et utiliser des noms x & y plutôt que des indices de tableau.

Juste une suggestion - vous pouvez ignorer ...

Answer 2

Pour les algorithmes sweepline que vous utilisez habituellement une sorte lexicographique sur vos points:

• Trier par X, si le composant X de deux points que vous compare est égal à, Trier par Y à la place. En 3D vous pouvez étendre à la composante Z et ainsi de suite ..

Cependant, je doute que le tri soit la racine de vos problèmes (intersections fausses et manquantes).

Les algorithmes de lignes de balayage sont très sensibles aux erreurs d'arrondi. Travailler avec l'arithmétique à virgule flottante ne peut pas être fait à moins que vous soyez absolument sûr que vos calculs conservent suffisamment de précision pour vous donner des résultats valides.

Jetez un oeil à cette page web pour plus de détails (et solutions) à ce genre de problèmes:

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

Bonne chance. Btw - vous écrivez un scan d'intersection Bentley-Ottmann, n'est-ce pas? Ceux-ci sont encore plus sensibles que les autres algorithmes de sweepline car l'insertion d'un point d'intersection modifie légèrement la pente des arêtes d'intersection en raison de la précision finie des flotteurs.