Using a persistent dictionary (cf. section 6.10) 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); }