home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graphics / sweep_se.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  20.2 KB  |  942 lines
  1. #include <LEDA/prio.h>
  2. #include <LEDA/sortseq.h>
  3. #include <LEDA/graph.h>
  4. #include <LEDA/plane.h>
  5. #include <LEDA/window.h>
  6.  
  7. #define EPS  0.00001
  8. #define EPS2 0.0000000001
  9.  
  10. declare2(GRAPH,point,int)
  11.  
  12. declare(list,seq_item)
  13.  
  14.  
  15. window* Wp;
  16.  
  17. static int trace = 0;
  18. static int intera = 0;
  19. static color seg_color = blue;
  20. static color node_color = red;
  21.  
  22.  
  23. class SWEEP_POINT;
  24. class SWEEP_SEGMENT;
  25. typedef SWEEP_POINT* SWEEP_point;
  26. typedef SWEEP_SEGMENT* SWEEP_segment;
  27.  
  28. enum SWEEP_point_type {Cross=0,Rightend=1,Leftend=2}; 
  29.  
  30.  
  31. class SWEEP_POINT
  32. {
  33.   friend class SWEEP_SEGMENT;
  34.  
  35.   SWEEP_segment seg;
  36.   int     kind;
  37.   real    x,y;
  38.  
  39.   public:
  40.  
  41.   SWEEP_POINT(real a,real b)   { x=a; y=b; seg=0; kind=Cross;}
  42.  
  43.   SWEEP_POINT(point p)         { x=p.xcoord();y=p.ycoord();seg=0;kind=Cross;}
  44.  
  45.   friend real    get_x(SWEEP_point p)      { return p->x; }
  46.   friend real    get_y(SWEEP_point p)      { return p->y; }
  47.   friend int     get_kind(SWEEP_point p)   { return p->kind; }
  48.   friend SWEEP_segment get_seg(SWEEP_point p)    { return p->seg; }   
  49.  
  50.   friend bool intersection(SWEEP_segment, SWEEP_segment, SWEEP_point&);
  51.  
  52.   OPERATOR_NEW(4);
  53.   OPERATOR_DEL(4);
  54.  
  55. };
  56.  
  57.  
  58. int compare(SWEEP_point& p1,SWEEP_point& p2)
  59. { if (p1==p2) return 0;
  60.  
  61.   real diffx = get_x(p1) - get_x(p2);
  62.   if (fabs(diffx) > EPS2 ) return (diffx > 0.0) ? 1 : -1;
  63.  
  64.   int  diffk = get_kind(p1)-get_kind(p2);
  65.   if (diffk != 0) return diffk;
  66.  
  67.   real diffy = get_y(p1) - get_y(p2);
  68.   if (fabs(diffy) > EPS2 ) return (diffy > 0.0) ? 1 : -1;
  69.  
  70.   return 0;
  71.  
  72. }
  73.  
  74. void Print(SWEEP_point& p) { cout << form("(%f,%f)",~get_x(p), ~get_y(p)); }
  75.  
  76. declare(list,SWEEP_point);
  77.  
  78.  
  79.  
  80. class SWEEP_SEGMENT
  81. {
  82.   SWEEP_point startpoint;
  83.   SWEEP_point endpoint;
  84.   real  slope;
  85.   real  yshift;
  86.   node  left_node;
  87.   int   orient;
  88.   int   color;
  89.   int   name;
  90.  
  91.   public:
  92.  
  93.   SWEEP_SEGMENT(SWEEP_point, SWEEP_point,int,int);     
  94.  ~SWEEP_SEGMENT() { delete startpoint; delete endpoint; }     
  95.  
  96.   friend SWEEP_point get_startpoint(SWEEP_segment seg)       { return seg->startpoint; }
  97.   friend SWEEP_point get_endpoint(SWEEP_segment seg)         { return seg->endpoint; }
  98.   friend real get_slope(SWEEP_segment seg)             { return seg->slope; }
  99.   friend real get_yshift(SWEEP_segment seg)            { return seg->yshift; }
  100.   friend int  get_orient(SWEEP_segment seg)            { return seg->orient; }
  101.   friend int  get_color(SWEEP_segment seg)             { return seg->color; }
  102.   friend int  get_name(SWEEP_segment seg)              { return seg->name; }
  103.   friend node get_left_node(SWEEP_segment seg)         { return seg->left_node; }
  104.   friend void set_left_node(SWEEP_segment seg, node v) { seg->left_node = v; }
  105.  
  106.   friend bool intersection(SWEEP_segment, SWEEP_segment, SWEEP_point&);
  107.  
  108.   OPERATOR_NEW(8);
  109.   OPERATOR_DEL(8);
  110.  
  111. };
  112.  
  113.  
  114.   SWEEP_SEGMENT::SWEEP_SEGMENT(SWEEP_point p1,SWEEP_point p2,int c, int n)    
  115.   {
  116.     left_node  = nil;
  117.     color      = c;
  118.     name       = n;
  119.  
  120.     if (compare(p1,p2) < 0)
  121.      { startpoint = p1; 
  122.        endpoint = p2; 
  123.        orient = 0;
  124.       }
  125.     else
  126.      { startpoint = p2; 
  127.        endpoint = p1; 
  128.        orient = 1;
  129.       }
  130.  
  131.     startpoint->kind = Leftend; 
  132.     endpoint->kind = Rightend; 
  133.     startpoint->seg = this; 
  134.     endpoint->seg = this;
  135.  
  136.     if (endpoint->x != startpoint->x)
  137.     {
  138.       slope = (endpoint->y - startpoint->y)/(endpoint->x - startpoint->x);
  139.       yshift = startpoint->y - slope * startpoint->x;
  140.  
  141.       startpoint->x -= EPS;
  142.       startpoint->y -= EPS * slope;
  143.       endpoint->x += EPS;
  144.       endpoint->y += EPS * slope;
  145.     }
  146.     else //vertical segment
  147.     { startpoint->y -= EPS;
  148.       endpoint->y   += EPS;
  149.      }
  150.   }
  151.  
  152. void Print(SWEEP_segment& s) { cout << form("S%d",get_name(s)); }
  153.  
  154. static real x_sweep;
  155. static real y_sweep;
  156.  
  157.  
  158. int compare(SWEEP_segment& s1,SWEEP_segment& s2)
  159. {
  160.   real sl1 = get_slope(s1);
  161.   real sl2 = get_slope(s2);
  162.   real ys1 = get_yshift(s1);
  163.   real ys2 = get_yshift(s2);
  164.  
  165.   real y1 = sl1*x_sweep+ys1;
  166.   real y2 = sl2*x_sweep+ys2;
  167.  
  168.   real diff = y1-y2;
  169.  
  170.   if (fabs(diff) > EPS2) return (diff > 0.0) ? 1 : -1;
  171.  
  172.   if (sl1 == sl2) 
  173.         return compare(get_x(get_startpoint(s1)), get_x(get_startpoint(s2)));
  174.  
  175.     if (y1 <= y_sweep+EPS2)
  176.         return compare(sl1,sl2);
  177.     else
  178.         return compare(sl2,sl1);
  179.  
  180. }
  181.  
  182.  
  183.  
  184.  
  185. declare2(priority_queue,seq_item,SWEEP_point);
  186. static priority_queue(seq_item,SWEEP_point) X_structure;
  187.  
  188. declare2(sortseq,SWEEP_segment,pq_item);
  189. static sortseq(SWEEP_segment,pq_item) Y_structure;
  190.  
  191.  
  192. bool intersection(SWEEP_segment seg1,SWEEP_segment seg2, SWEEP_point& inter)
  193. {
  194.   if (seg1->slope == seg2->slope)
  195.     return false;
  196.   else
  197.   {
  198.     //x-coordinate  of the intersection
  199.     real Cross_x = (seg2->yshift - seg1->yshift) / (seg1->slope - seg2->slope);
  200.  
  201.     if (Cross_x <= x_sweep) return false;
  202.  
  203.     real s1 = seg1->startpoint->x;
  204.     real s2 = seg2->startpoint->x;
  205.     real e1 = seg1->endpoint->x;
  206.     real e2 = seg2->endpoint->x;
  207.  
  208.     if (s2>Cross_x || s1>Cross_x || Cross_x>e1 || Cross_x>e2) return false;
  209.  
  210.     //y-coordinate of the intersection
  211.     real Cross_y = (seg1->slope * Cross_x + seg1->yshift);
  212.     inter =  new SWEEP_POINT(Cross_x,Cross_y);
  213.  
  214.     return true;
  215.   }
  216. }
  217.  
  218. void message(string s, int line=1)
  219. { s += "                                                            ";
  220.   double d = 20/Wp->scale();
  221.   if (s.length() > 150) s = s.head(150);
  222.   Wp->draw_text(Wp->xmin()+d, Wp->ymax()-d*(0.5+line),s);
  223.  }
  224.  
  225.  
  226. void draw_segment(SWEEP_segment seg)
  227. { real x1 = get_x(get_startpoint(seg));
  228.   real y1 = get_y(get_startpoint(seg));
  229.   real x2 = get_x(get_endpoint(seg));
  230.   real y2 = get_y(get_endpoint(seg));
  231.  
  232.   real d = 10/Wp->scale();
  233.  
  234.   Wp->draw_text(x1-d,y1,form("%d",get_name(seg)));
  235.  
  236.   Wp->draw_segment(x1,y1,x2,y2,seg_color);
  237. }
  238.  
  239.  
  240. declare(list,SWEEP_segment);
  241.  
  242. void draw_sweep_line(real xpos) 
  243. {
  244.  
  245.   Wp->set_mode(xor_mode);
  246.  
  247.  if (trace) 
  248.     Wp->draw_segment(xpos,-1150,xpos,Wp->ymax()-5*20/Wp->scale());
  249.  else 
  250.     Wp->draw_segment(xpos,-1150,xpos,Wp->ymax()-2*20/Wp->scale());
  251.  
  252.   Wp->set_mode(src_mode);
  253. }
  254.  
  255. void move_sweep_line(real x, real xpos) 
  256. { 
  257.   if (x == xpos) return;
  258.   
  259.   real delta = 1/Wp->scale(); 
  260.  
  261.   Wp->set_mode(xor_mode);
  262.  
  263.   while (x < xpos)
  264.   { draw_sweep_line(x+delta);
  265.     draw_sweep_line(x);
  266.     x += delta;
  267.    }
  268.   
  269.   draw_sweep_line(x);
  270.  
  271.   draw_sweep_line(xpos);
  272.  
  273.   Wp->set_mode(src_mode);
  274. }
  275.  
  276. void draw_Ystructure()
  277. {
  278.   seq_item sit;
  279.   string s = "Y_structure: ";
  280.  
  281.   forall_seq_items(sit,Y_structure) 
  282.     s+=form("%d ",get_name(Y_structure.key(sit)));
  283.  
  284.   message(s,3);
  285.  
  286. }
  287.  
  288. void draw_Xstructure()
  289. {
  290.   string s = "X_structure: ";
  291.  
  292.   priority_queue(seq_item,SWEEP_point) Q = X_structure;
  293.  
  294.   while (!Q.empty())
  295.   { pq_item it = Q.find_min(); 
  296.  
  297.     SWEEP_point p = X_structure.inf(it);
  298.     seq_item sit  = X_structure.key(it);
  299.  
  300.     Q.del_min();
  301.  
  302.      SWEEP_segment seg = get_seg(p);
  303.  
  304.      switch (get_kind(p)) {
  305.  
  306.      case Leftend:  s += form("L(%d) ",get_name(seg));
  307.                     break;
  308.  
  309.      case Rightend: s += form("R(%d) ",get_name(seg)) ;
  310.                     break;
  311.  
  312.      default:       s += form("X(%d) ",get_name(Y_structure.key(sit))); 
  313.                     break;
  314.  
  315.      }
  316.  
  317.   }
  318.  
  319.   message(s,2);
  320.  
  321. }
  322.  
  323. pq_item Xinsert(seq_item i, SWEEP_point p) 
  324. { 
  325.  
  326.  if (trace)
  327.  {
  328.   SWEEP_segment s ;
  329.   if (i!=nil) s = Y_structure.key(i);
  330.  
  331.   else s = get_seg(p);
  332.     
  333.      switch (get_kind(p)) {
  334.  
  335.      case Leftend:  message(form("Xinsert: L(%d) ",get_name(s)),4);
  336.                     break;
  337.  
  338.      case Rightend: message(form("Xinsert: R(%d) ",get_name(s)),4) ;
  339.                     break;
  340.  
  341.      default:       message(form("Xinsert: X(%d) ",get_name(s)),4); 
  342.                     break;
  343.       }
  344.  
  345.   Wp->set_mode(xor_mode);
  346.   Wp->draw_filled_node(get_x(p),get_y(p),green);
  347.   Wp->set_mode(src_mode);
  348.  }
  349.   return X_structure.insert(i,p);
  350. }
  351.  
  352. SWEEP_point Xdelete(pq_item i) 
  353. {
  354.  if (trace)
  355.  {SWEEP_point p = X_structure.inf(i);
  356.  
  357.   seq_item sit = X_structure.key(i);
  358.  
  359.   SWEEP_segment s ;
  360.  
  361.   if (sit!=nil) s = Y_structure.key(sit);
  362.   else s = get_seg(p);
  363.     
  364.      switch (get_kind(p)) {
  365.  
  366.      case Leftend:  message(form("Xdelete: L(%d) ",get_name(s)),4);
  367.                     break;
  368.  
  369.      case Rightend: message(form("Xdelete: R(%d) ",get_name(s)),4) ;
  370.                     break;
  371.  
  372.      default:       message(form("Xdelete: X(%d) ",get_name(s)),4); 
  373.                     break;
  374.       }
  375.  
  376.   Wp->set_mode(xor_mode);
  377.   Wp->draw_filled_node(get_x(p),get_y(p),green);
  378.   Wp->set_mode(src_mode);
  379.  }
  380.  
  381.   SWEEP_point p = X_structure.inf(i);
  382.  
  383.   X_structure.del_item(i);
  384.  
  385.   return p;
  386. }
  387.  
  388.  
  389. node New_Node(GRAPH(point,int)& G,real x, real y )
  390. { return G.new_node(point(x,y)); }
  391.  
  392. void New_Edge(GRAPH(point,int)& G,node v, node w, SWEEP_segment l )
  393. { if (get_orient(l)==0)
  394.        G.new_edge(v,w,get_color(l));
  395.   else G.new_edge(w,v,get_color(l));
  396. }
  397.  
  398.  
  399. void process_vertical_segment(GRAPH(point,int)& SUB, SWEEP_segment l)
  400. { 
  401.   SWEEP_point p = 
  402.               new SWEEP_POINT(get_x(get_startpoint(l)),get_y(get_startpoint(l)));
  403.   SWEEP_point q = 
  404.               new SWEEP_POINT(get_x(get_endpoint(l)),get_y(get_endpoint(l)));
  405.  
  406.   SWEEP_point r = new SWEEP_POINT(get_x(p)+1,get_y(p));
  407.   SWEEP_point s = new SWEEP_POINT(get_x(q)+1,get_y(q));
  408.  
  409.   SWEEP_segment bot = new SWEEP_SEGMENT(p,r,0,0);
  410.   SWEEP_segment top = new SWEEP_SEGMENT(q,s,0,0);
  411.  
  412.   seq_item bot_it = Y_structure.insert(bot,nil);
  413.   seq_item top_it = Y_structure.insert(top,nil);
  414.   seq_item sit;
  415.  
  416.   node u,v,w;
  417.   SWEEP_segment seg;
  418.   
  419.  
  420.   for(sit=Y_structure.succ(bot_it); sit != top_it; sit=Y_structure.succ(sit))
  421.   { seg = Y_structure.key(sit);
  422.  
  423.     real cross_y = (get_slope(seg) * get_x(p) + get_yshift(seg));
  424.  
  425.     Wp->draw_filled_node(get_x(p),cross_y,node_color);
  426.  
  427.     v = get_left_node(seg);
  428.     if (v==nil)
  429.     { w = New_Node(SUB,get_x(p),cross_y);
  430.       set_left_node(seg,w);
  431.      }
  432.     else
  433.     { real vx = SUB[v].xcoord();
  434.       if ( vx < get_x(p)-EPS2) 
  435.       { w = New_Node(SUB,get_x(p),cross_y);
  436.         New_Edge(SUB,v,w,seg);
  437.         set_left_node(seg,w);
  438.        }
  439.       else w = v;
  440.      }
  441.  
  442.     u = get_left_node(l);
  443.     if (u!=nil && u!=w) New_Edge(SUB,u,w,l);
  444.     set_left_node(l,w);
  445.  
  446.    }
  447.     
  448.   delete l;
  449.   delete bot;
  450.   delete top;
  451.   Y_structure.del_item(bot_it);
  452.   Y_structure.del_item(top_it);
  453.  
  454.  }
  455.  
  456.  
  457. void plane_sweep(list(segment)& L1, list(segment)& L2, GRAPH(point,int)& SUB)
  458. {
  459.   SWEEP_point    p,inter;
  460.   SWEEP_segment  seg, l,lsit,lpred,lsucc,lpredpred;
  461.  
  462.   pq_item  pqit,pxmin;
  463.   seq_item sitmin,sit,sitpred,sitsucc,sitpredpred;
  464.  
  465.  
  466.   int count=1;
  467.  
  468.   Wp->clear();
  469.  
  470.   //initialization of the X-structure
  471.  
  472.   segment s;
  473.  
  474.   forall(s,L1) 
  475.    { SWEEP_point p = new SWEEP_POINT(s.start());
  476.      SWEEP_point q = new SWEEP_POINT(s.end());
  477.      seg = new SWEEP_SEGMENT(p,q,0,count++);
  478.      draw_segment(seg);
  479.      Xinsert(nil,get_startpoint(seg));
  480.    }
  481.  
  482.   count = -1;
  483.  
  484.   forall(s,L2) 
  485.    { SWEEP_point p = new SWEEP_POINT(s.start());
  486.      SWEEP_point q = new SWEEP_POINT(s.end());
  487.      seg = new SWEEP_SEGMENT(p,q,1,count--);
  488.      draw_segment(seg);
  489.      Xinsert(nil,get_startpoint(seg));
  490.    }
  491.  
  492.  
  493.   count = 0;
  494.  
  495.   x_sweep = Wp->xmin();
  496.   y_sweep = Wp->ymin();
  497.  
  498.   if (trace)
  499.   { draw_Xstructure();
  500.     draw_Ystructure();
  501.    }
  502.  
  503.   draw_sweep_line(x_sweep);
  504.  
  505.   while(!X_structure.empty())
  506.   {
  507.     if (trace==1)  trace = Wp->read_mouse();
  508.  
  509.     pxmin = X_structure.find_min();
  510.     p = X_structure.inf(pxmin);
  511.  
  512.     move_sweep_line(x_sweep,get_x(p));
  513.  
  514.     sitmin = X_structure.key(pxmin);
  515.  
  516.     Xdelete(pxmin);
  517.  
  518.  
  519.  
  520.     if (get_kind(p) == Leftend)
  521.  
  522.     //left endpoint
  523.     { 
  524.  
  525.       l = get_seg(p); 
  526.  
  527.       x_sweep = get_x(p);
  528.       y_sweep = get_y(p);
  529.  
  530.       if (trace)
  531.       message(form("LEFT  point   x = %4f seg = %4d",
  532.               ~get_x(p),get_name(l)),1);
  533.  
  534.  
  535.       if (get_x(p) == get_x(get_endpoint(l)))
  536.         process_vertical_segment(SUB,l);
  537.       else
  538.       {
  539.  
  540.       sit = Y_structure.lookup(l);
  541.  
  542.       if (sit!=nil)  error_handler(0,"plane sweep: sorry, overlapping segments");
  543.  
  544.       sit = Y_structure.insert(l,nil);
  545.  
  546.       Xinsert(sit,get_endpoint(l));
  547.  
  548.       sitpred = Y_structure.pred(sit);
  549.       sitsucc = Y_structure.succ(sit);
  550.  
  551.       if (sitpred != nil) 
  552.       { if ((pqit = Y_structure.inf(sitpred)) != nil)
  553.           delete Xdelete(pqit);
  554.  
  555.         lpred = Y_structure.key(sitpred);
  556.  
  557.         Y_structure.change_inf(sitpred,nil);
  558.  
  559.         if (intersection(lpred,l,inter))
  560.             Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  561.       }
  562.  
  563.  
  564.       if (sitsucc != nil)
  565.       { lsucc = Y_structure.key(sitsucc);
  566.         if (intersection(lsucc,l,inter))
  567.            Y_structure.change_inf(sit,Xinsert(sit,inter));
  568.       }
  569.      } /* else if vertical */
  570.  
  571.     }
  572.     else if (get_kind(p) == Rightend)
  573.          //right endpoint
  574.          { 
  575.            x_sweep = get_x(p);
  576.            y_sweep = get_y(p);
  577.  
  578.            if (trace)
  579.            message(form("RIGHT point   x = %4f seg = %4d",
  580.                    ~get_x(p),get_name(get_seg(p))),1);
  581.  
  582.            sit = sitmin;
  583.  
  584.            sitpred = Y_structure.pred(sit);
  585.            sitsucc = Y_structure.succ(sit);
  586.  
  587.            SWEEP_segment SEG =Y_structure.key(sit);
  588.  
  589.            Y_structure.del_item(sit);
  590.  
  591.            delete SEG;
  592.  
  593.            if((sitpred != nil)&&(sitsucc != nil))
  594.            {
  595.              lpred = Y_structure.key(sitpred);
  596.              lsucc = Y_structure.key(sitsucc);
  597.              if (intersection(lsucc,lpred,inter))
  598.                 Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  599.            }
  600.          }
  601.          else /*point of intersection*/
  602.          { 
  603.            node w = New_Node(SUB,get_x(p),get_y(p));
  604.  
  605.            count++;
  606.  
  607.            /* Let L = list of all lines intersecting in p 
  608.  
  609.               we compute sit     = L.head();
  610.               and        sitpred = L.tail();
  611.  
  612.               by scanning the Y_structure in both directions 
  613.               starting at sitmin;
  614.  
  615.            */
  616.  
  617.            /* search for sitpred upwards from sitmin: */
  618.  
  619.            Y_structure.change_inf(sitmin,nil);
  620.  
  621.            sitpred = Y_structure.succ(sitmin);
  622.  
  623.  
  624.            while ((pqit=Y_structure.inf(sitpred)) != nil)
  625.            { SWEEP_point q = X_structure.inf(pqit);
  626.              if (compare(p,q) != 0) break; 
  627.              X_structure.del_item(pqit);
  628.              Y_structure.change_inf(sitpred,nil);
  629.              sitpred = Y_structure.succ(sitpred);
  630.             }
  631.  
  632.  
  633.            /* search for sit downwards from sitmin: */
  634.  
  635.            sit = sitmin;
  636.  
  637.            seq_item sit1;
  638.            
  639.            while ((sit1=Y_structure.pred(sit)) != nil)
  640.            { pqit = Y_structure.inf(sit1);
  641.              if (pqit == nil) break;
  642.              SWEEP_point q = X_structure.inf(pqit);
  643.              if (compare(p,q) != 0) break; 
  644.              X_structure.del_item(pqit);
  645.              Y_structure.change_inf(sit1,nil);
  646.              sit = sit1;
  647.             }
  648.  
  649.  
  650. /*
  651.            if (trace)
  652.            { string line;
  653.              line += form("sit = %d  ", get_name(Y_structure.key(sit)));
  654.              line += form("sitpred = %d",get_name(Y_structure.key(sitpred)));
  655.              message(line,5);
  656.             }
  657. */
  658.  
  659.  
  660.            // insert edges to p for all segments in sit, ..., sitpred into SUB
  661.            // and set left node to w 
  662.  
  663.            lsit = Y_structure.key(sitpred);
  664.  
  665.            node v = get_left_node(lsit);
  666.            if (v!=nil) New_Edge(SUB,v,w,lsit);
  667.            set_left_node(lsit,w);
  668.  
  669.            for(sit1=sit; sit1!=sitpred; sit1 = Y_structure.succ(sit1))
  670.            { lsit = Y_structure.key(sit1);
  671.  
  672.              v = get_left_node(lsit);
  673.              if (v!=nil) New_Edge(SUB,v,w,lsit);
  674.              set_left_node(lsit,w);
  675.             }
  676.  
  677.            lsit = Y_structure.key(sit);
  678.            lpred=Y_structure.key(sitpred);
  679.            sitpredpred = Y_structure.pred(sit);
  680.            sitsucc=Y_structure.succ(sitpred);
  681.  
  682.            message(form("INTERSECTION  # = %4d  x = %5f  seg = %4d ",
  683.                         count, ~get_x(p),get_name(lsit)),1);
  684.  
  685.            Wp->draw_filled_node(get_x(p),get_y(p),node_color);
  686.  
  687.  
  688.            if (sitpredpred != nil)
  689.             { 
  690.               lpredpred=Y_structure.key(sitpredpred);
  691.  
  692.               if ((pqit = Y_structure.inf(sitpredpred)) != nil)
  693.                delete Xdelete(pqit);
  694.      
  695.  
  696.               Y_structure.change_inf(sitpredpred,nil);
  697.  
  698.  
  699.               if (intersection(lpred,lpredpred,inter))
  700.                 Y_structure.change_inf(sitpredpred,
  701.                                        Xinsert(sitpredpred,inter));
  702.              }
  703.  
  704.  
  705.            if (sitsucc != nil)
  706.             {
  707.               lsucc=Y_structure.key(sitsucc);
  708.  
  709.               if ((pqit = Y_structure.inf(sitpred)) != nil)
  710.                 delete Xdelete(pqit);
  711.                  
  712.               Y_structure.change_inf(sitpred,nil);
  713.  
  714.               if (intersection(lsucc,lsit,inter))
  715.                   Y_structure.change_inf(sit,Xinsert(sit,inter));
  716.              }
  717.  
  718.  
  719. // reverse the subsequence sit, ... ,sitpred  in the Y_structure
  720.  
  721.            x_sweep = get_x(p);
  722.            y_sweep = get_y(p);
  723.  
  724.            Y_structure.reverse_items(sit,sitpred);
  725.  
  726.            delete p;
  727.  
  728.          } // intersection
  729.  
  730.    if (trace) 
  731.     { draw_Xstructure();
  732.       draw_Ystructure();
  733.      }
  734.  
  735.   }
  736.  
  737.   message("END OF SWEEP",1);
  738.  
  739.   if (intera) Wp->read_mouse();             //wait for mouse click
  740.  
  741.     draw_sweep_line(x_sweep);
  742.  
  743.     X_structure.clear();
  744.  
  745. } // plane_sweep
  746.  
  747.  
  748.  
  749. void interactive(window& W)
  750. {
  751.   bool random_input;
  752.   int grid_width = 0;
  753.   int line_width = 1;
  754.   int node_width = 4;
  755.   int N = 50;
  756.  
  757.   intera= 1;
  758.  
  759.   panel P("PLANE SWEEP");
  760.  
  761.   P.text_item("This program performs a plane sweep to compute the  "); 
  762.   P.text_item("intersections of a set of straight line segments.   ");
  763.   P.text_item("You can define a sequence of segments with the left ");
  764.   P.text_item("mouse button terminated by pressing the right button");
  765.   P.text_item("or create a random set of segments. In TRACE mode,  ");
  766.   P.text_item("the current states of the event queue (X-structure) ");
  767.   P.text_item("and the sweep line (Y-structure) are displayed, and ");
  768.   P.text_item("the sweep line stops at each event point waiting for");
  769.   P.text_item("a mouse click.                                      ");
  770.   P.text_item("                                                    ");
  771.  
  772.   P.bool_item("TRACE",trace);
  773.   P.choice_item("INPUT", random_input,"mouse","random");
  774.   P.int_item("GRID",grid_width,0,40,10);
  775.   P.int_item("SEGMENTS", N);
  776.   P.text_item("");
  777.   P.int_item("line width",line_width,1,5);
  778.   P.int_item("node width",node_width,1,10);
  779.  
  780.  
  781. for(;;)
  782. {
  783.   P.open();
  784.  
  785.   W.init(-1200,1200,-1200, grid_width);
  786.  
  787.   W.set_text_mode(opaque);
  788.   W.set_node_width(node_width);
  789.   W.set_line_width(line_width);
  790.  
  791.   list(segment) seglist1,seglist2;
  792.  
  793.   if (random_input) 
  794.    { 
  795.      init_random();
  796.  
  797.      double ymax = W.ymax()-4*20/W.scale()-100;
  798.  
  799.      int xmin = int(W.xmin())+100;
  800.      int xmax = int(W.xmax())-100;
  801.  
  802.      while (N--) 
  803.      { real x1 = random(xmin,-100);
  804.        real y1 = random(-1000,int(ymax));
  805.        real x2 = random(100,xmax);
  806.        real y2 = random(-1000,int(ymax));
  807.        segment s(x1,y1,x2,y2);
  808.        W << s;
  809.        seglist1.append(s);
  810.       }
  811.     }
  812.   else // mouse input
  813.     { segment s;
  814.  
  815.       while (W >> s)
  816.       { W << s;
  817.         seglist1.append(s);
  818.        }
  819.  
  820.      }
  821.  
  822.  
  823.   GRAPH(point,int) SUB;
  824.  
  825.   plane_sweep(seglist1,seglist2,SUB);
  826.  
  827. } // for(;;)
  828.  
  829. }
  830.  
  831.  
  832.  
  833. void demo(window& W, int N)
  834. {
  835.   trace = false;
  836.  
  837.   W.init(-1200,1200,-1200);
  838.  
  839.   for(;;)
  840.   {
  841.  
  842.   W.clear();
  843.  
  844.  
  845.   W.set_text_mode(opaque);
  846.   W.set_node_width(3);
  847.  
  848.  
  849.   list(segment) seglist1,seglist2;
  850.  
  851.      init_random();
  852.  
  853.      double ymax = W.ymax()-4*20/W.scale()-100;
  854.  
  855.      for(int i=0; i<N; i++)
  856.      { real x1 = random(-1100,-100);
  857.        real y1 = random(-1000,int(ymax));
  858.        real x2 = random(100,1100);
  859.        real y2 = random(-1000,int(ymax));
  860.        segment s(x1,y1,x2,y2);
  861.        W << s;
  862.        seglist1.append(s);
  863.       }
  864.  
  865.  
  866.   GRAPH(point,int) SUB;
  867.   edge e;
  868.  
  869.   plane_sweep(seglist1,seglist2,SUB);
  870.  
  871.   W.clear();
  872.   forall_edges(e,SUB) W <<  segment(SUB[source(e)],SUB[target(e)]);
  873.  
  874.   sleep(2);
  875.  
  876.   }
  877.  
  878. }
  879.  
  880.  
  881.  
  882. main(int argc, char** argv)
  883. {
  884.   int   position=0, 
  885.         N=0;
  886.  
  887.   float f1=0, 
  888.         f2=0;
  889.  
  890.   float w,h,xpos,ypos;
  891.  
  892.   string_istream arguments(argc-1,argv+1);
  893.  
  894.   arguments >> f1;
  895.   arguments >> f2;
  896.  
  897.   if (f1 == 0 && f2 == 0) 
  898.    { f1 = 0.75;
  899.      f2 = 0.95;
  900.     }
  901.   else 
  902.    if (f2 == 0) 
  903.      f2 = f1;
  904.    else
  905.      { arguments >> position;
  906.        arguments >> N;
  907.       }
  908.  
  909.   w = SCREEN_WIDTH*f1;
  910.   h = SCREEN_HEIGHT*f2;
  911.  
  912.   switch(position) {
  913.  
  914.   case 0: xpos = SCREEN_WIDTH - w;
  915.           ypos = 0;
  916.           break; 
  917.  
  918.   case 1: xpos = 0;
  919.           ypos = 0;
  920.           break; 
  921.  
  922.   case 2: xpos = 0;
  923.           ypos = SCREEN_HEIGHT - h;
  924.           break; 
  925.  
  926.   case 3: xpos = SCREEN_WIDTH - w;
  927.           ypos = SCREEN_HEIGHT - h;
  928.           break; 
  929. }
  930.  
  931.  
  932.   window W(w,h,xpos,ypos);
  933.  
  934.   Wp = &W;
  935.  
  936.   if (N==0) 
  937.      interactive(W);
  938.   else
  939.      demo(W,N);
  940.  
  941. }
  942.