开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
sweep_segments.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：21k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

sweep_segments.c：源码内容
  1. #include <LEDA/prio.h>
  2. #include <LEDA/sortseq.h>
  3. #include <LEDA/segment.h>
  4. #include <LEDA/window.h>
  6. #include <math.h>
  10. /*
  11. #include <LEDA/graph.h>
  12. */
  16. #define EPS  0.00001
  17. #define EPS2 0.0000000001
  20. window* Wp;
  22. static bool trace = false;
  23. static bool intera = false;
  24. static color seg_color = blue;
  25. static color node_color = red;
  28. class SWEEP_POINT;
  29. class SWEEP_SEGMENT;
  30. typedef SWEEP_POINT* SWEEP_point;
  31. typedef SWEEP_SEGMENT* SWEEP_segment;
  33. enum SWEEP_point_type {Cross=0,Rightend=1,Leftend=2}; 
  36. class SWEEP_POINT
  37. {
  38.   friend class SWEEP_SEGMENT;
  40.   SWEEP_segment seg;
  41.   int     kind;
  42.   double    x,y;
  44.   public:
  46.   SWEEP_POINT(double a,double b)   { x=a; y=b; seg=0; kind=Cross;}
  48.   SWEEP_POINT(point p)         { x=p.xcoord();y=p.ycoord();seg=0;kind=Cross;}
  50.   friend double    get_x(SWEEP_point p);
  51.   friend double    get_y(SWEEP_point p);
  52.   friend int       get_kind(SWEEP_point p);
  53.   friend SWEEP_segment get_seg(SWEEP_point p);
  55.   friend bool intersection(SWEEP_segment, SWEEP_segment, SWEEP_point&);
  57.   LEDA_MEMORY(SWEEP_POINT);
  59. };
  61.   inline double    get_x(SWEEP_point p)       { return p->x; }
  62.   inline double    get_y(SWEEP_point p)       { return p->y; }
  63.   inline int       get_kind(SWEEP_point p)    { return p->kind; }
  64.   inline SWEEP_segment get_seg(SWEEP_point p) { return p->seg; }   
  67. #if defined(__GNUC__)
  68. // if I declare compare static g++ does not use it but instantiates 
  69. // the default error compare template
  70. inline
  71. #else
  72. static
  73. #endif
  74. int compare(const SWEEP_point& p1, const SWEEP_point& p2)
  75. { if (p1==p2) return 0;
  77.   double diffx = get_x(p1) - get_x(p2);
  78.   if (fabs(diffx) > EPS2 ) return (diffx > 0.0) ? 1 : -1;
  80.   int  diffk = get_kind(p1)-get_kind(p2);
  81.   if (diffk != 0) return diffk;
  83.   double diffy = get_y(p1) - get_y(p2);
  84.   if (fabs(diffy) > EPS2 ) return (diffy > 0.0) ? 1 : -1;
  86.   return 0;
  88. }
  90. void Print(SWEEP_point& p) { cout << string("(%f,%f)",get_x(p), get_y(p)); }
  95. class SWEEP_SEGMENT
  96. {
  97.   SWEEP_point startpoint;
  98.   SWEEP_point endpoint;
  99.   double  slope;
  100.   double  yshift;
  101.   //node  left_node;
  102.   int   orient;
  103.   int   color;
  104.   int   name;
  106.   public:
  108.   SWEEP_SEGMENT(SWEEP_point, SWEEP_point,int,int);     
  109.  ~SWEEP_SEGMENT() { delete startpoint; delete endpoint; }     
  111.   friend SWEEP_point get_startpoint(SWEEP_segment seg);
  112.   friend SWEEP_point get_endpoint(SWEEP_segment seg);
  113.   friend double get_slope(SWEEP_segment seg);
  114.   friend double get_yshift(SWEEP_segment seg);
  115.   friend int  get_orient(SWEEP_segment seg);
  116.   friend int  get_color(SWEEP_segment seg);
  117.   friend int  get_name(SWEEP_segment seg);
  119. /*
  120.   friend node get_left_node(SWEEP_segment seg)         { return seg->left_node;}
  121.   friend void set_left_node(SWEEP_segment seg, node v) { seg->left_node = v; }
  122. */
  124.   friend bool intersection(SWEEP_segment, SWEEP_segment, SWEEP_point&);
  126.   LEDA_MEMORY(SWEEP_SEGMENT);
  129. };
  132. inline SWEEP_point get_startpoint(SWEEP_segment seg) { return seg->startpoint; }
  133. inline SWEEP_point get_endpoint(SWEEP_segment seg)   { return seg->endpoint; }
  134. inline double get_slope(SWEEP_segment seg)           { return seg->slope; }
  135. inline double get_yshift(SWEEP_segment seg)          { return seg->yshift; }
  136. inline int  get_orient(SWEEP_segment seg)            { return seg->orient; }
  137. inline int  get_color(SWEEP_segment seg)             { return seg->color; }
  138. inline int  get_name(SWEEP_segment seg)              { return seg->name; }
  141.   SWEEP_SEGMENT::SWEEP_SEGMENT(SWEEP_point p1,SWEEP_point p2,int c, int n)    
  142.   {
  143.     //left_node  = nil;
  144.     color      = c;
  145.     name       = n;
  147.     if (compare(p1,p2) < 0)
  148.      { startpoint = p1; 
  149.        endpoint = p2; 
  150.        orient = 0;
  151.       }
  152.     else
  153.      { startpoint = p2; 
  154.        endpoint = p1; 
  155.        orient = 1;
  156.       }
  158.     startpoint->kind = Leftend; 
  159.     endpoint->kind = Rightend; 
  160.     startpoint->seg = this; 
  161.     endpoint->seg = this;
  163.     if (endpoint->x != startpoint->x)
  164.     {
  165.       slope = (endpoint->y - startpoint->y)/(endpoint->x - startpoint->x);
  166.       yshift = startpoint->y - slope * startpoint->x;
  168.       startpoint->x -= EPS;
  169.       startpoint->y -= EPS * slope;
  170.       endpoint->x += EPS;
  171.       endpoint->y += EPS * slope;
  172.     }
  173.     else //vertical segment
  174.     { startpoint->y -= EPS;
  175.       endpoint->y   += EPS;
  176.      }
  177.   }
  179. void Print(SWEEP_segment& s) { cout << string("S%d",get_name(s)); }
  181. static double x_sweep;
  182. static double y_sweep;
  185. int compare(const SWEEP_segment& s1,const SWEEP_segment& s2)
  186. {
  187.   double sl1 = get_slope(s1);
  188.   double sl2 = get_slope(s2);
  189.   double ys1 = get_yshift(s1);
  190.   double ys2 = get_yshift(s2);
  192.   double y1 = sl1*x_sweep+ys1;
  193.   double y2 = sl2*x_sweep+ys2;
  195.   double diff = y1-y2;
  197.   if (fabs(diff) > EPS2) return (diff > 0.0) ? 1 : -1;
  199.   if (sl1 == sl2) 
  200.         return compare(get_x(get_startpoint(s1)), get_x(get_startpoint(s2)));
  202.     if (y1 <= y_sweep+EPS2)
  203.         return compare(sl1,sl2);
  204.     else
  205.         return compare(sl2,sl1);
  207. }
  212. static priority_queue<seq_item,SWEEP_point> X_structure;
  214. static sortseq<SWEEP_segment,pq_item> Y_structure;
  217. bool intersection(SWEEP_segment seg1,SWEEP_segment seg2, SWEEP_point& inter)
  218. {
  219.   if (seg1->slope == seg2->slope)
  220.     return false;
  221.   else
  222.   {
  223.     //x-coordinate  of the intersection
  224.     double Cross_x = (seg2->yshift - seg1->yshift) / (seg1->slope - seg2->slope);
  225.  
  226.     if (Cross_x <= x_sweep) return false;
  228.     double s1 = seg1->startpoint->x;
  229.     double s2 = seg2->startpoint->x;
  230.     double e1 = seg1->endpoint->x;
  231.     double e2 = seg2->endpoint->x;
  233.     if (s2>Cross_x || s1>Cross_x || Cross_x>e1 || Cross_x>e2) return false;
  235.     //y-coordinate of the intersection
  236.     double Cross_y = (seg1->slope * Cross_x + seg1->yshift);
  237.     inter =  new SWEEP_POINT(Cross_x,Cross_y);
  239.     return true;
  240.   }
  241. }
  243. void message(string s, int line=1)
  244. { s += "                                                            ";
  245.   double d = 20/Wp->scale();
  246.   if (s.length() > 150) s = s.head(150);
  247.   Wp->draw_text(Wp->xmin()+d, Wp->ymax()-d*(0.5+line),s);
  248.  }
  250.  
  251. void draw_segment(SWEEP_segment seg)
  252. { double x1 = get_x(get_startpoint(seg));
  253.   double y1 = get_y(get_startpoint(seg));
  254.   double x2 = get_x(get_endpoint(seg));
  255.   double y2 = get_y(get_endpoint(seg));
  257.   double d = 10/Wp->scale();
  259.   Wp->draw_text(x1-d,y1,string("%d",get_name(seg)));
  261.   Wp->draw_segment(x1,y1,x2,y2,seg_color);
  262. }
  263.  
  267. void draw_sweep_line(double xpos) 
  268. {
  269.   Wp->set_mode(xor_mode);
  270.   Wp->draw_segment(xpos,-1150,xpos,Wp->ymax()-5*20/Wp->scale());
  271.   Wp->set_mode(src_mode);
  272. }
  275. void move_sweep_line(double x, double xpos) 
  276. { 
  277.   if (x == xpos) return;
  279.   double delta = 1/Wp->scale(); 
  280.   double y = Wp->ymax()-100*delta;
  282.   Wp->set_mode(xor_mode);
  284.   while (x < xpos)
  285.   { Wp->draw_segment(x+delta,-1150,x+delta,y);
  286.     Wp->draw_segment(x,-1150,x,y);
  287.     x += delta;
  288.    }
  289.   
  290.   Wp->draw_segment(x,-1150,x,y);
  291.   Wp->draw_segment(xpos,-1150,xpos,y);
  293.   Wp->set_mode(src_mode);
  294. }
  298. void draw_Ystructure()
  299. {
  300.   seq_item sit;
  301.   string s = "Y_structure: ";
  303.   forall_items(sit,Y_structure) 
  304.     s+=string("%d ",get_name(Y_structure.key(sit)));
  306.   message(s,3);
  308. }
  310. void draw_Xstructure()
  311. {
  312.   string s = "X_structure: ";
  314.   priority_queue<seq_item,SWEEP_point> Q = X_structure;
  316.   while (!Q.empty())
  317.   { pq_item it = Q.find_min(); 
  319.     SWEEP_point p = X_structure.inf(it);
  320.     seq_item sit  = X_structure.key(it);
  322.     Q.del_min();
  324.      SWEEP_segment seg = get_seg(p);
  326.      switch (get_kind(p)) {
  328.      case Leftend:  s += string("L(%d) ",get_name(seg));
  329.                     break;
  331.      case Rightend: s += string("R(%d) ",get_name(seg)) ;
  332.                     break;
  334.      default:       s += string("X(%d) ",get_name(Y_structure.key(sit))); 
  335.                     break;
  337.      }
  339.   }
  341.   message(s,2);
  343. }
  345. pq_item Xinsert(seq_item i, SWEEP_point p) 
  346. { 
  348.  if (trace)
  349.  {
  350.   SWEEP_segment s ;
  351.   if (i!=nil) s = Y_structure.key(i);
  353.   else s = get_seg(p);
  354.     
  355.      switch (get_kind(p)) {
  357.      case Leftend:  message(string("Xinsert: L(%d) ",get_name(s)),4);
  358.                     break;
  360.      case Rightend: message(string("Xinsert: R(%d) ",get_name(s)),4) ;
  361.                     break;
  363.      default:       message(string("Xinsert: X(%d) ",get_name(s)),4); 
  364.                     break;
  365.       }
  367.   Wp->set_mode(xor_mode);
  368.   Wp->draw_filled_node(get_x(p),get_y(p),green);
  369.   Wp->set_mode(src_mode);
  370.  }
  371.   return X_structure.insert(i,p);
  372. }
  374. SWEEP_point Xdelete(pq_item i) 
  375. {
  376.  if (trace)
  377.  {SWEEP_point p = X_structure.inf(i);
  379.   seq_item sit = X_structure.key(i);
  381.   SWEEP_segment s ;
  383.   if (sit!=nil) s = Y_structure.key(sit);
  384.   else s = get_seg(p);
  385.     
  386.      switch (get_kind(p)) {
  388.      case Leftend:  message(string("Xdelete: L(%d) ",get_name(s)),4);
  389.                     break;
  391.      case Rightend: message(string("Xdelete: R(%d) ",get_name(s)),4) ;
  392.                     break;
  394.      default:       message(string("Xdelete: X(%d) ",get_name(s)),4); 
  395.                     break;
  396.       }
  398.   Wp->set_mode(xor_mode);
  399.   Wp->draw_filled_node(get_x(p),get_y(p),green);
  400.   Wp->set_mode(src_mode);
  401.  }
  403.   SWEEP_point p = X_structure.inf(i);
  405.   X_structure.del_item(i);
  407.   return p;
  408. }
  412. /*
  413. node New_Node(GRAPH<point,int>& G,double x, double y )
  414. { return G.new_node(point(x,y)); }
  416. void New_Edge(GRAPH<point,int>& G,node v, node w, SWEEP_segment l )
  417. { if (get_orient(l)==0)
  418.        G.new_edge(v,w,get_color(l));
  419.   else G.new_edge(w,v,get_color(l));
  420. }
  421. */
  424. void process_vertical_segment(/*GRAPH<point,int>& SUB, */ SWEEP_segment l)
  425. { 
  426.   SWEEP_point p = 
  427.               new SWEEP_POINT(get_x(get_startpoint(l)),get_y(get_startpoint(l)));
  428.   SWEEP_point q = 
  429.               new SWEEP_POINT(get_x(get_endpoint(l)),get_y(get_endpoint(l)));
  431.   SWEEP_point r = new SWEEP_POINT(get_x(p)+1,get_y(p));
  432.   SWEEP_point s = new SWEEP_POINT(get_x(q)+1,get_y(q));
  434.   SWEEP_segment bot = new SWEEP_SEGMENT(p,r,0,0);
  435.   SWEEP_segment top = new SWEEP_SEGMENT(q,s,0,0);
  437.   seq_item bot_it = Y_structure.insert(bot,nil);
  438.   seq_item top_it = Y_structure.insert(top,nil);
  439.   seq_item sit;
  441.   //node u,v,w;
  443.   SWEEP_segment seg;
  444.   
  446.   for(sit=Y_structure.succ(bot_it); sit != top_it; sit=Y_structure.succ(sit))
  447.   { seg = Y_structure.key(sit);
  449.     double cross_y = (get_slope(seg) * get_x(p) + get_yshift(seg));
  451.     Wp->draw_filled_node(get_x(p),cross_y,node_color);
  453. /*
  454.     v = get_left_node(seg);
  455.     if (v==nil)
  456.     { w = New_Node(SUB,get_x(p),cross_y);
  457.       set_left_node(seg,w);
  458.      }
  459.     else
  460.     { double vx = SUB[v].xcoord();
  461.       if ( vx < get_x(p)-EPS2) 
  462.       { w = New_Node(SUB,get_x(p),cross_y);
  463.         New_Edge(SUB,v,w,seg);
  464.         set_left_node(seg,w);
  465.        }
  466.       else w = v;
  467.      }
  469.     u = get_left_node(l);
  470.     if (u!=nil && u!=w) New_Edge(SUB,u,w,l);
  471.     set_left_node(l,w);
  472. */
  474.    }
  475.     
  476.   delete l;
  477.   delete bot;
  478.   delete top;
  479.   Y_structure.del_item(bot_it);
  480.   Y_structure.del_item(top_it);
  482.  }
  485. void plane_sweep(list<segment>& L1, list<segment>& L2 
  486.                  /*, GRAPH<point,int>& SUB */)
  487. {
  488.   SWEEP_point    p,inter;
  489.   SWEEP_segment  seg, l,lsit,lpred,lsucc,lpredpred;
  491.   pq_item  pqit,pxmin;
  492.   seq_item sitmin,sit,sitpred,sitsucc,sitpredpred;
  495.   int count=1;
  497.   Wp->clear();
  498.  
  499.   //initialization of the X-structure
  501.   segment s;
  503.   forall(s,L1) 
  504.    { SWEEP_point p = new SWEEP_POINT(s.start());
  505.      SWEEP_point q = new SWEEP_POINT(s.end());
  506.      seg = new SWEEP_SEGMENT(p,q,0,count++);
  507.      draw_segment(seg);
  508.      Xinsert(nil,get_startpoint(seg));
  509. /*
  510. Print(seg);
  511. Print(get_startpoint(seg));
  512. newline;
  513. */
  514.    }
  516.   count = -1;
  518.   forall(s,L2) 
  519.    { SWEEP_point p = new SWEEP_POINT(s.start());
  520.      SWEEP_point q = new SWEEP_POINT(s.end());
  521.      seg = new SWEEP_SEGMENT(p,q,1,count--);
  522.      draw_segment(seg);
  523.      Xinsert(nil,get_startpoint(seg));
  524. /*
  525. Print(seg);
  526. Print(get_startpoint(seg));
  527. newline;
  528. */
  529.    }
  532.   count = 0;
  534.   x_sweep = Wp->xmin();
  535.   y_sweep = Wp->ymin();
  537.   if (trace)
  538.   { draw_Xstructure();
  539.     draw_Ystructure();
  540.    }
  542.   draw_sweep_line(x_sweep);
  544.   while(!X_structure.empty())
  545.   {
  546.     if (trace)  
  547.        trace = (Wp->read_mouse() != 3);
  548.     else
  549.        trace = Wp->get_button();
  552.     pxmin = X_structure.find_min();
  553.     p = X_structure.inf(pxmin);
  555.     move_sweep_line(x_sweep,get_x(p));
  557.     sitmin = X_structure.key(pxmin);
  559.     Xdelete(pxmin);
  563.     if (get_kind(p) == Leftend)
  565.     //left endpoint
  566.     { 
  568.       l = get_seg(p); 
  570.       x_sweep = get_x(p);
  571.       y_sweep = get_y(p);
  573.       if (trace)
  574.       message(string("LEFT  point   x = %4f seg = %4d",
  575.               get_x(p),get_name(l)),1);
  578.       if (get_x(p) == get_x(get_endpoint(l)))
  579.         process_vertical_segment(/*SUB,*/ l);
  580.       else
  581.       {
  583.       sit = Y_structure.lookup(l);
  585.       if (sit!=nil)  error_handler(0,"plane sweep: sorry, overlapping segments");
  587.       sit = Y_structure.insert(l,nil);
  589.       Xinsert(sit,get_endpoint(l));
  591.       sitpred = Y_structure.pred(sit);
  592.       sitsucc = Y_structure.succ(sit);
  594.       if (sitpred != nil) 
  595.       { if ((pqit = Y_structure.inf(sitpred)) != nil)
  596.           delete Xdelete(pqit);
  598.         lpred = Y_structure.key(sitpred);
  600.         Y_structure.change_inf(sitpred,nil);
  602.         if (intersection(lpred,l,inter))
  603.             Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  604.       }
  607.       if (sitsucc != nil)
  608.       { lsucc = Y_structure.key(sitsucc);
  609.         if (intersection(lsucc,l,inter))
  610.            Y_structure.change_inf(sit,Xinsert(sit,inter));
  611.       }
  612.      } /* else if vertical */
  614.     }
  615.     else if (get_kind(p) == Rightend)
  616.          //right endpoint
  617.          { 
  618.            x_sweep = get_x(p);
  619.            y_sweep = get_y(p);
  621.            if (trace)
  622.            message(string("RIGHT point   x = %4f seg = %4d",
  623.                    get_x(p),get_name(get_seg(p))),1);
  625.            sit = sitmin;
  626.  
  627.            sitpred = Y_structure.pred(sit);
  628.            sitsucc = Y_structure.succ(sit);
  630.            SWEEP_segment SEG =Y_structure.key(sit);
  632.            Y_structure.del_item(sit);
  634.            delete SEG;
  636.            if((sitpred != nil)&&(sitsucc != nil))
  637.            {
  638.              lpred = Y_structure.key(sitpred);
  639.              lsucc = Y_structure.key(sitsucc);
  640.              if (intersection(lsucc,lpred,inter))
  641.                 Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  642.            }
  643.          }
  644.          else /*point of intersection*/
  645.          { 
  646.            //node w = New_Node(SUB,get_x(p),get_y(p));
  648.            count++;
  650.            /* Let L = list of all lines intersecting in p 
  651.  
  652.               we compute sit     = L.head();
  653.               and        sitpred = L.tail();
  655.               by scanning the Y_structure in both directions 
  656.               starting at sitmin;
  658.            */
  660.            /* search for sitpred upwards from sitmin: */
  662.            Y_structure.change_inf(sitmin,nil);
  664.            sitpred = Y_structure.succ(sitmin);
  667.            while ((pqit=Y_structure.inf(sitpred)) != nil)
  668.            { SWEEP_point q = X_structure.inf(pqit);
  669.              if (compare(p,q) != 0) break; 
  670.              X_structure.del_item(pqit);
  671.              Y_structure.change_inf(sitpred,nil);
  672.              sitpred = Y_structure.succ(sitpred);
  673.             }
  676.            /* search for sit downwards from sitmin: */
  678.            sit = sitmin;
  680.            seq_item sit1;
  681.            
  682.            while ((sit1=Y_structure.pred(sit)) != nil)
  683.            { pqit = Y_structure.inf(sit1);
  684.              if (pqit == nil) break;
  685.              SWEEP_point q = X_structure.inf(pqit);
  686.              if (compare(p,q) != 0) break; 
  687.              X_structure.del_item(pqit);
  688.              Y_structure.change_inf(sit1,nil);
  689.              sit = sit1;
  690.             }
  693. /*
  694.            if (trace)
  695.            { string line;
  696.              line += string("sit = %d  ", get_name(Y_structure.key(sit)));
  697.              line += string("sitpred = %d",get_name(Y_structure.key(sitpred)));
  698.              message(line,5);
  699.             }
  700. */
  702. /*
  704.            // insert edges to p for all segments in sit, ..., sitpred into SUB
  705.            // and set left node to w 
  707.            lsit = Y_structure.key(sitpred);
  709.            node v = get_left_node(lsit);
  710.            if (v!=nil) New_Edge(SUB,v,w,lsit);
  711.            set_left_node(lsit,w);
  713.            for(sit1=sit; sit1!=sitpred; sit1 = Y_structure.succ(sit1))
  714.            { lsit = Y_structure.key(sit1);
  716.              v = get_left_node(lsit);
  717.              if (v!=nil) New_Edge(SUB,v,w,lsit);
  718.              set_left_node(lsit,w);
  719.             }
  720. */
  722.            lsit = Y_structure.key(sit);
  723.            lpred=Y_structure.key(sitpred);
  724.            sitpredpred = Y_structure.pred(sit);
  725.            sitsucc=Y_structure.succ(sitpred);
  727.            message(string("INTERSECTION  # = %4d  x = %5f  seg = %4d ",
  728.                         count, float(get_x(p)),get_name(lsit)),1);
  730.            draw_sweep_line(get_x(p));
  731.            Wp->draw_filled_node(get_x(p),get_y(p),node_color);
  732.            draw_sweep_line(get_x(p));
  735.            if (sitpredpred != nil)
  736.             { 
  737.               lpredpred=Y_structure.key(sitpredpred);
  739.               if ((pqit = Y_structure.inf(sitpredpred)) != nil)
  740.                delete Xdelete(pqit);
  741.      
  743.               Y_structure.change_inf(sitpredpred,nil);
  746.               if (intersection(lpred,lpredpred,inter))
  747.                 Y_structure.change_inf(sitpredpred,
  748.                                        Xinsert(sitpredpred,inter));
  749.              }
  752.            if (sitsucc != nil)
  753.             {
  754.               lsucc=Y_structure.key(sitsucc);
  756.               if ((pqit = Y_structure.inf(sitpred)) != nil)
  757.                 delete Xdelete(pqit);
  758.                  
  759.               Y_structure.change_inf(sitpred,nil);
  761.               if (intersection(lsucc,lsit,inter))
  762.                   Y_structure.change_inf(sit,Xinsert(sit,inter));
  763.              }
  766. // reverse the subsequence sit, ... ,sitpred  in the Y_structure
  768.            x_sweep = get_x(p);
  769.            y_sweep = get_y(p);
  771.            Y_structure.reverse_items(sit,sitpred);
  773.            delete p;
  775.          } // intersection
  777.    if (trace) 
  778.     { draw_Xstructure();
  779.       draw_Ystructure();
  780.      }
  782.   }
  784.   message("END OF SWEEP",1);
  786.   if (intera) Wp->read_mouse();             //wait for mouse click
  788.     draw_sweep_line(x_sweep);
  790.     X_structure.clear();
  792. } // plane_sweep
  796. void interactive(window& W)
  797. {
  798.   intera= true;
  800.   int grid_width = 0;
  801.   int line_width = 1;
  802.   int node_width = 4;
  803.   int N = 80;
  805.   panel P("PLANE SWEEP DEMO");
  807.   P.bool_item("TRACE",trace);
  808.   P.int_item("GRID",grid_width,0,80,20);
  809.   P.int_item("SEGMENTS", N);
  810.   P.int_item("line width",line_width,1,5);
  811.   P.int_item("node width",node_width,1,10);
  812.   P.button("MOUSE");
  813.   P.button("RANDOM");
  814.   P.button("QUIT");
  816.   for(;;)
  817.   { int input = P.open(W);
  818.   
  819.     if (input == 2) break;
  820.   
  821.     W.init(-1200,1200,-1200, grid_width);
  822.     W.set_text_mode(opaque);
  823.     W.set_node_width(node_width);
  824.     W.set_line_width(line_width);
  825.   
  826.     list<segment> seglist1,seglist2;
  827.   
  828.     if (input==1)  // random 
  829.      { double ymax = W.ymax()-4*20/W.scale()-100;
  830.        int xmin = int(W.xmin())+100;
  831.        int xmax = int(W.xmax())-100;
  832.        for(int i=0; i<N; i++)
  833.        { double x1 = rand_int(xmin,-100);
  834.          double y1 = rand_int(-1000,int(ymax));
  835.          double x2 = rand_int(100,xmax);
  836.          double y2 = rand_int(-1000,int(ymax));
  837.          segment s(x1,y1,x2,y2);
  838.          W << s;
  839.          seglist1.append(s);
  840.         }
  841.       }
  842.     else // input == 0 (mouse)
  843.       { segment s;
  844.         while (W >> s)
  845.         { W << s;
  846.           seglist1.append(s);
  847.          }
  848.        }
  849.   
  850.   
  851.     plane_sweep(seglist1,seglist2);
  852.   
  853.   //GRAPH<point,int> SUB;
  854.   //plane_sweep(seglist1,seglist2,SUB);
  855.   
  856.  } // for(;;)
  858. }
  862. void demo(window& W, int N)
  863. {
  864.   trace = false;
  866.   W.init(-1200,1200,-1200);
  868.   for(;;)
  869.   {
  871.   W.clear();
  874.   W.set_text_mode(opaque);
  875.   W.set_node_width(3);
  878.   list<segment> seglist1,seglist2;
  880.      double ymax = W.ymax()-4*20/W.scale()-100;
  882.      for(int i=0; i<N; i++)
  883.      { double x1 = rand_int(-1100,-100);
  884.        double y1 = rand_int(-1000,int(ymax));
  885.        double x2 = rand_int(100,1100);
  886.        double y2 = rand_int(-1000,int(ymax));
  887.        segment s(x1,y1,x2,y2);
  888.        W << s;
  889.        seglist1.append(s);
  890.       }
  892.   plane_sweep(seglist1,seglist2);
  894. /*
  895.   GRAPH<point,int> SUB;
  896.   edge e;
  898.   plane_sweep(seglist1,seglist2,SUB);
  899.  
  900.   W.clear();
  901.   forall_edges(e,SUB) W <<  segment(SUB[source(e)],SUB[target(e)]);
  902. */
  904.   wait(2);
  906.   }
  908. }
  911. /*
  912. #include <LEDA/stream.h>
  913. */
  916. main(int argc, char** argv)
  917. {
  918.   int N = 0;
  920.   panel P0("PLANE SWEEP DEMO");
  921.   P0.text_item("This program computes the intersections in a set of");
  922.   P0.text_item("straight line segments using a plane sweep algorithm.");
  923.   P0.text_item("You can define the set of line segments interactively");
  924.   P0.text_item("using the left mouse button (input is terminated with");
  925.   P0.text_item("the right button) or create a random set of segments.");
  926.   P0.text_item("In TRACE mode the current contents of the event queue");
  927.   P0.text_item("(X-structure) and of the sweep line (Y-structure) are");
  928.   P0.text_item("displayed and the sweep line stops at each event point.");
  929.   P0.button("continue");
  930.    
  931.   if (argc == 1)
  932.     P0.open();
  933.   else
  934.     N = atoi(argv[1]);
  936.   window W;
  938.   Wp = &W;
  940.   if (N==0) 
  941.       interactive(W);
  942.   else
  943.      demo(W,N);
  946.   return 0;
  947. }