ordering edges for sweeping algorithm

Question

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):

• by the x coordinate of their edge[0] coordinate (iff the x's of 2 edges are different)

• by the y coordinate of their edge[0] coordinate (iff the x's of 2 edges are equal)

• by their corresponding slopes (iff the x's of edges and the y's of edges are equal).

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):

• by the x coordinate of their edge[0] coordinate (iff the x's of 2 edges are different)

• by their corresponding slopes(iff the x's of 2 edges are equal)

• by the y coordinate of their edge[1] coordinate (iff the x's of edges and the slopes of edges are equal).

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

Answer 1

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...

Answer 2

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.