home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graphics / p_sweep.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.0 KB  |  181 lines
  1. #include <LEDA/plane.h>
  2. #include <LEDA/window.h>
  3. #include <LEDA/prio.h>
  4. #include <LEDA/sortseq.h>
  5. #include <LEDA/p_dictionary.h>
  6.  
  7.  
  8. real X_POS;
  9.  
  10. int compare(segment& s1,segment& s2)
  11. {
  12.   line l1(s1);
  13.   line l2(s2);
  14.  
  15.   double diff = l1.y_proj(X_POS) - l2.y_proj(X_POS);
  16.  
  17.   if (fabs(diff) < 1e-10)
  18.      return compare(l1.slope(),l2.slope());
  19.   else 
  20.      return compare(diff,0.0);
  21. }
  22.  
  23. segment hor_seg(point p) { return segment(p,0,1); }
  24.  
  25.  
  26.  
  27. declare2(priority_queue,segment,point);
  28. typedef priority_queue(segment,point) X_structure;
  29.  
  30.  
  31. declare2(p_dictionary,segment,int);
  32. typedef p_dictionary(segment,int) Y_structure; 
  33.  
  34.  
  35. declare2(sortseq,real,Y_structure);
  36. typedef sortseq(real,Y_structure)  HISTORY;
  37.  
  38.  
  39. HISTORY H;
  40.  
  41.  
  42. void sweep(list(segment)& L)
  43. {
  44.   X_structure    X;
  45.   Y_structure    Y;           
  46.   segment s;
  47.  
  48.   forall(s,L)                     // initialize the X_structure
  49.   { X.insert(s,s.start());
  50.     X.insert(s,s.end());
  51.    }
  52.  
  53.  
  54.   // start sweep
  55.  
  56.   X_POS = -MAXDOUBLE;         
  57.  
  58.   H.insert(X_POS,Y);              // insert empty Y_structure at -infinity
  59.  
  60.   while( !X.empty() )
  61.   {
  62.     point   p; 
  63.     segment l;
  64.  
  65.     X.del_min(l,p);               // p is the next transitition point
  66.                                   // s is a segment starting or ending in p
  67.  
  68.     X_POS = p.xcoord();           // move the sweep line to p
  69.  
  70.     if (l.start()==p)             // update Y_structure Y
  71.         Y = Y.insert(l,0);        // left point
  72.     else
  73.         Y = Y.del(l);             // rigth point
  74.  
  75.     H.insert(X_POS,Y);            // insert Y into history sequence 
  76.  
  77.   }
  78.  
  79.   H.insert(MAXDOUBLE,Y);          // insert empty Y_structure at +infinity
  80.   
  81. }
  82.  
  83.  
  84.  
  85.  
  86. segment locate(point p)
  87. {
  88.   X_POS = p.xcoord();
  89.  
  90.   Y_structure Y = H.inf(H.pred(X_POS));
  91.  
  92.   p_dic_item pit = Y.succ(hor_seg(p));
  93.  
  94.   if (pit != nil) 
  95.      return Y.key(pit);
  96.   else
  97.      return segment(0);
  98.   
  99. }
  100.  
  101.  
  102.  
  103. window W;
  104.  
  105. void draw_sweep_line()
  106. { int save = W.set_line_width(1);
  107.   W.draw_vline(X_POS,green);
  108.   W.set_line_width(save);
  109.  }
  110.  
  111. void draw_segment(segment s)
  112. { W.draw_segment(s,blue);
  113.  }
  114.  
  115. void show_segment(segment s)
  116. { draw_segment(s);
  117.   int save = W.set_line_width(5);
  118.   W.draw_segment(s,red);
  119.   W.set_line_width(save);
  120.  }
  121.  
  122. void hide_segment(segment s)
  123. { int save = W.set_line_width(5);
  124.   W.draw_segment(s,red);
  125.   W.set_line_width(save);
  126.   draw_segment(s);
  127.  }
  128.  
  129.  
  130. main()
  131. { 
  132.   segment s;
  133.   point p;
  134.  
  135.   list(segment) L;
  136.  
  137.   W.set_mode(xor_mode);
  138.   W.set_line_width(1);
  139.  
  140.   while (W >> s) 
  141.   { draw_segment(s);
  142.     L.append(s);
  143.    }
  144.  
  145.  sweep(L);
  146.  
  147.  
  148.  int key;
  149.  real x0,x,y;
  150.  
  151.  X_POS = W.xmin();
  152.  L.clear();
  153.  
  154.  while ((key = W.read_mouse(x,y))!= 3 )  
  155.  {
  156.    forall(s,L) hide_segment(s);           
  157.    draw_sweep_line();
  158.    L.clear();
  159.  
  160.    switch(key) {
  161.  
  162.    case 1: L.append(locate(point(x,y)));
  163.            X_POS = W.xmin();
  164.            break;
  165.  
  166.    case 2: { X_POS = x;
  167.              draw_sweep_line();
  168.              seq_item sit = H.pred(x);
  169.              Y_structure Y = H.inf(sit);
  170.              p_dic_item it;
  171.              forall_items(it,Y) L.append(Y.key(it));
  172.              break;
  173.             }
  174.    }
  175.  
  176.    forall(s,L) show_segment(s);           
  177.  
  178.   }
  179.   
  180. }
  181.