Using a persistent dictionary (cf. section 4.7) for planar point location (sweep line algorithm).
`=̀
#include <LEDA/plane.h> #include <LEDA/prio.h> #include <LEDA/sortseq.h> #include <LEDA/p_dictionary.h>
double X_POS; // current position of sweep line
int compare(segment s1,segment s2) line l1(s1); line l2(s2);
double y1 = l1.y_proj(X_POS); double y2 = l2.y_proj(X_POS);
return compare(y1,y2);
typedef priority_queue<segment,point> X_structure; typedef p_dictionary<segment,int> Y_structure;
sortseq<double,Y_structure> HISTORY;
void SWEEP(list<segment>& L) // Precondition: L is a list of non-intersecting // from left to right directed line segments
X_structure X; Y_structure Y; segment s;
forall(s,L) // initialize the X_structure X.insert(s,s.start()); X.insert(s,s.end());
HISTORY.insert(-MAXDOUBLE,Y); // insert empty Y_structure at -infinity
while( ! X.empty() ) point p; segment s;
X.del_min(s,p); // next event: endpoint p of segment s
X_POS = p.xcoord();
if (s.start()==p) Y = Y.insert(s,0); // p is left end of s else Y = Y.del(s); // p is right end of s
HISTORY.insert(X_POS,Y); // insert Y into history sequence
HISTORY.insert(MAXDOUBLE,Y); // insert empty Y_structure at +infinity
segment LOCATE(point p) X_POS = p.xcoord();
Y_structure Y = HISTORY.inf(HISTORY.pred(X_POS));
p_dic_item pit = Y.succ(segment(p,0,1));
if (pit != nil) return Y.key(pit); else return segment(0);