Geometry

 

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