CODEWITHSUNDEEP
c++geometry
madalina
madalina

Reputation: 377

ordering edges for sweeping algorithm

I have the following data structures in my class:

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

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

where: Each point has 3 components,thus being given by an index, an x, and a y coordinate; Each edge is given by its source index-edge[0] and its destination index-edge[1],where edge[0],edge[1] are indexes of the myPoints data structure). I have this edges in my variable myEdges_.

The question is the following: How one has to arrange this edges for applying the sweep algorithm and obtaining the good results and the good results only (that is all the intersections of the edges). So far I have two different criteria for arranging the edges, but none of them give me the good results and only the good results (either I do not obtain all the intersections or either I get the intersections plus some other points which are not intersections).

Here are my criteria:

criteria 1 (idea):

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

Criteria 2(idea):

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

};

yep this looks really complicated, I tried these criteria on my algorithm and I do not obtain all the intersections. So I am guessing the ordering criteria for my edges for the sweeping algorithm is not good, because I detect some intersections but not others. Thank you for your suggestions (or small opinions) in advance, madalina

Upvotes: 0

Views: 663

Answers (2)

Nils Pipenbrinck
Nils Pipenbrinck

Reputation: 86333

For sweepline algorithms you usually use a lexicographic sort on your points:

  • Sort by X, if the X component of two points you compare is equal, Sort by Y instead. In 3D you can extend to the Z-component and so on..

However, I doubt that the sorting is the root of your problems (false and missed intersections).

Sweepline algorithms are very sensitive to rounding errors. Working with floating point arithmetic can't be done unless you make absolutely sure that your math preserves enough precision to give you valid results.

Take a look at this web-page for more details (and solutions) to these kinds of problems:

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

Good luck.

Btw - you're writing a Bentley-Ottmann intersection scan, aren't you? These are even more sensitive than other sweepline-algorithms because inserting an intersection point will slightly changes the slope of the intersecting edges due to the finite precision of floats.

Upvotes: 0

anon
anon

Reputation:

Nothing directly to do with our question, but can I suggest that your code would be one hell of a lot more readable if you used a simple Point structure to represent XY coordinates? something like:

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

would be a start. You could then create 1-demensioned vectors of Point, and use names x & y rather than array indices.

Just a suggestion - feel free to ignore...

Upvotes: 2

Related Questions