home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graphics / delaunay.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  7.4 KB  |  378 lines
  1. #include <LEDA/window.h>
  2. #include <LEDA/delaunay_tree.h>
  3.  
  4.  
  5. window* Wp;
  6.  
  7. const double R = 1000;  // "length of inifinite rays"
  8.  
  9. int ymax;
  10.  
  11. int segment_to_points(segment s, list(point)& out, double dist)
  12. { 
  13.   int n = int(s.length()/dist) + 2;
  14.  
  15.   double dx = (s.xcoord2() - s.xcoord1())/n;
  16.   double dy = (s.ycoord2() - s.ycoord1())/n;
  17.   double x  = s.xcoord1();
  18.   double y  = s.ycoord1();
  19.  
  20.   out.append(s.start());
  21.  
  22.   for(int i = 0; i<n; i++)
  23.   { x += dx + 0.001 * rrandom();
  24.     y += dy + 0.001 * rrandom();
  25.     out.append(point(x,y));
  26.    }
  27.  
  28.   out.permute();
  29.  
  30.   return n;
  31.  
  32. }
  33.  
  34. int circle_to_points(circle C, list(point)& out, double dist)
  35. { 
  36.   point c = C.center();
  37.   double r = C.radius();
  38.   int n = int(6.283 * r/dist);
  39.  
  40.   double alpha = 0;
  41.   double d = 6.283/n;
  42.  
  43.   for(int i = 0; i<n; i++)
  44.   { out.append(c.translate(alpha,r + 0.0001 * rrandom()));
  45.     alpha += d;
  46.    }
  47.  
  48.   out.permute();
  49.  
  50.  return n;
  51.  
  52. }
  53.  
  54.  
  55.  
  56.  
  57. void draw_vor_site(double x, double y)
  58. { Wp->draw_point(x,y); }
  59.  
  60. void draw_vor_seg(double x1, double y1, double x2, double y2,double,double)
  61. { Wp->draw_segment(x1,y1,x2,y2,blue); }
  62.  
  63.  
  64. void draw_triang_seg(double x1, double y1, double x2, double y2)
  65. { Wp->draw_segment(x1,y1,x2,y2,red); 
  66.  }
  67.  
  68. void infi_pt(double x1, double y1, double x2, double y2, double *x, double* y)
  69. /* retourne le point a l'infini dans la direction x2 y2 depuis x1 y1*/
  70. {
  71.   vector v(x2,y2);
  72.  
  73.   v = v.norm();
  74.  
  75.   *x = x1 + R * v[0];
  76.   *y = y1 + R * v[1];
  77.   
  78. }
  79.  
  80.  
  81. declare(DELAUNAY_TREE,int)
  82.  
  83. DELAUNAY_TREE(int) DT;
  84.  
  85. DT_item it = nil;
  86. bool vor = false;
  87. bool triang = false;
  88. list(segment) CH;
  89.  
  90. void redraw()
  91. { list(DT_item) L;
  92.   DT.all_items(L);
  93.   Wp->clear();
  94.   forall(it,L) *Wp << DT.key(it);
  95.   it = nil; 
  96.   vor = false;
  97.   triang = false;
  98.   CH.clear();
  99. }
  100.  
  101.  
  102. void interactive(window& W)
  103. {
  104.  
  105.   W.set_mode(xor_mode);
  106.  
  107.   panel P("DYNAMIC VORONOI DIAGRAMS");
  108.  
  109.   P.text_item("            based on Delaunay Trees           ");
  110.   P.text_item("             by Olivier Devillers             ");
  111.   P.text_item("             INRIA Sofia-Antipolis            ");
  112.   P.text_item("                                              ");
  113.   P.text_item("BUTTON    |  left      middle       right     ");
  114.   P.text_item("----------+-----------------------------------");
  115.   P.text_item("unshifted |  insert    voronoi      menu      ");
  116.   P.text_item("shifted   |  segment   delaunay     delete    ");
  117.   P.text_item("ctrl      |  circle    convex hull  locate    ");
  118.   P.text_item("                                              ");
  119.  
  120.   int key = 0;
  121.  
  122.   int input = 0;          // 0:mouse, 1: random
  123.   int grid_width = 0;
  124.   int line_width = 1;
  125.   int node_width = 4;
  126.   int N = 100;
  127.  
  128.   P.choice_item("input",input,"mouse","random");
  129.  
  130.   P.int_item("grid width  ",grid_width,0,40,10);
  131.   P.int_item("#sites ",N);
  132.   P.int_item("line width", line_width,1,5);
  133.   P.int_item("node width", node_width,1,10);
  134.  
  135.  
  136. for(;;)
  137. {
  138.   P.open();
  139.  
  140.   W.set_line_width(line_width);
  141.   W.set_node_width(node_width);
  142.   W.set_grid_mode(grid_width);
  143.  
  144.   real x, y;
  145.  
  146.   it = nil;
  147.   vor = false;
  148.   triang = false;
  149.   CH.clear();
  150.  
  151.  
  152.   if (input == 1)
  153.   { init_random();
  154.     DT.clear();
  155.     W.clear();
  156.     while (N--)
  157.     { point p(random(10,500),random(10,ymax));
  158.       DT.insert(p,N);
  159.       W << p;
  160.      }
  161.  
  162.     DT.trace_voronoi_edges( draw_vor_seg,infi_pt);
  163.     W.flush();
  164.     vor = true;
  165.    }
  166.  
  167.  
  168.    while ( (key = W.read_mouse(x,y)) != 3 ) 
  169.     {
  170.       segment s;
  171.  
  172.       // undo previous drawings
  173.  
  174.         if (vor)         DT.trace_voronoi_edges(draw_vor_seg,infi_pt);
  175.         if (triang)      DT.trace_triang_edges(draw_triang_seg);
  176.         if (!CH.empty()) forall(s,CH) W.draw_arrow(s,green);
  177.         if (it != nil)   W.draw_filled_node(DT.key(it));
  178.  
  179.  
  180.         vor = false;
  181.         triang = false;
  182.         CH.clear();
  183.         it = nil;
  184.  
  185.         point p(x,y);
  186.  
  187.     switch (key) {
  188.  
  189.     case  1 : { W << p;
  190.                     DT.insert(p,0);
  191.                     break;
  192.                    }
  193.  
  194.     case -1 :  { list(point) pl;
  195.                      real x1,y1;
  196.                      W.read_mouse_seg(x,y,x1,y1);
  197.                      segment s(x,y,x1,y1);
  198.                      segment_to_points(s,pl,10/W.scale());
  199.                      point p;
  200.                      forall(p,pl)
  201.                      { W << p;
  202.                        DT.insert(p,0);
  203.                       }
  204.                      break;
  205.                     }
  206.  
  207.     case  4 :  { list(point) pl;
  208.                      real x1,y1;
  209.                      W.read_mouse_circle(x,y,x1,y1);
  210.                      point p(x,y);
  211.                      real r = p.distance(point(x1,y1));
  212.                      circle_to_points(circle(p,r),pl,10/W.scale());
  213.                      forall(p,pl)
  214.                      { W << p;
  215.                        DT.insert(p,0);
  216.                       }
  217.                      break;
  218.                     }
  219.  
  220.  
  221.  
  222.     case  2 : DT.trace_voronoi_edges( draw_vor_seg,infi_pt);
  223.                   vor = true;
  224.                   break;
  225.  
  226.     case -2 : DT.trace_triang_edges( draw_triang_seg);
  227.                   triang = true;
  228.                   break;
  229.  
  230.         case  5: { // convex hull
  231.                    list(DT_item) L;
  232.                    list_item it;
  233.                    DT.convex_hull(L);
  234.                    cout << "Convex Hull =\n";
  235.                    forall_items(it,L) 
  236.                    { point p = DT.key(L[it]);
  237.                      point q = DT.key(L[L.cyclic_succ(it)]);
  238.                      cout << p;
  239.                      newline;
  240.                      CH.append(segment(p,q));
  241.                      W.draw_arrow(p,q,green);
  242.                     }
  243.                    newline;
  244.                    break;
  245.                   }
  246.  
  247.         case  3 : // panel
  248.                   break;
  249.  
  250.  
  251.     case -3 : it = DT.neighbor(p); 
  252.                   if (it) 
  253.           { W << DT.key(it);
  254.                     DT.del_item(it); 
  255.                    }
  256.                   it = nil;
  257.                   break;
  258.  
  259.     case  6 : it = DT.neighbor(p); 
  260.                   if (it)
  261.           { W.draw_filled_node(DT.key(it));
  262.             cout << DT.inf(it) << "\n";
  263.                    }
  264.                   break;
  265.  
  266.  
  267.  
  268.     }  // switch
  269.  
  270.       W.flush();
  271.  
  272.      }  // while
  273.  
  274.  } // for(;;)
  275.  
  276. }
  277.  
  278.  
  279.  
  280. void demo(int N, int wait)
  281. { int i;
  282.  
  283.   for(;;)
  284.   {
  285.     DT.clear();
  286.     Wp->clear();
  287.     Wp->message(form("%d sites",N));
  288.     Wp->flush();
  289.  
  290.     for (i=0; i<N ; i++)
  291.     { point p(random(10,500),random(10,ymax));
  292.       DT.insert(p,i);
  293.       *Wp << p;
  294.      }
  295.  
  296.  
  297.     //DT.trace_voronoi_sites( draw_vor_site);
  298.  
  299.     DT.trace_voronoi_edges( draw_vor_seg,infi_pt);
  300.     Wp->flush();
  301.     sleep(wait);
  302.  
  303.     Wp->clear();
  304.  
  305.     DT.trace_triang_edges( draw_triang_seg);
  306.     Wp->flush();
  307.     sleep(wait);
  308.   }
  309.  
  310. }
  311.  
  312.  
  313. main(int argc, char** argv)
  314. {
  315.   int   position=0, N=0;
  316.   float f1=0, f2=0;
  317.  
  318.   float w,h,xpos,ypos;
  319.  
  320.   string_istream arguments(argc-1,argv+1);
  321.  
  322.   arguments >> f1;
  323.   arguments >> f2;
  324.  
  325.  
  326.   if (f1 == 0 && f2 == 0) 
  327.    { f1 = 0.75;
  328.      f2 = 0.95;
  329.     }
  330.   else 
  331.    if (f2 == 0) 
  332.      f2 = f1;
  333.    else
  334.      { arguments >> position;
  335.        arguments >> N;
  336.       }
  337.  
  338.   w = SCREEN_WIDTH*f1;
  339.   h = SCREEN_HEIGHT*f2;
  340.  
  341.   switch(position) {
  342.  
  343.   case 0: xpos = SCREEN_WIDTH - w;    // upper right corner
  344.           ypos = 0;
  345.           break; 
  346.  
  347.   case 1: xpos = 0;                   // upper left corner
  348.           ypos = 0;
  349.           break; 
  350.  
  351.   case 2: xpos = 0;
  352.           ypos = SCREEN_HEIGHT - h;   // lower left corner
  353.           break; 
  354.  
  355.   case 3: xpos = SCREEN_WIDTH - w;    // lower right corner
  356.           ypos = SCREEN_HEIGHT - h;
  357.           break; 
  358. }
  359.  
  360.  
  361.   window W(w,h,xpos,ypos);
  362.  
  363.   W.set_flush(false);
  364.   W.set_node_width(5);
  365.  
  366.   W.init(0,512,0);
  367.  
  368.   Wp = &W;
  369.  
  370.   ymax = int(W.ymax()-10);
  371.  
  372.   if (N==0) 
  373.      interactive(W);
  374.   else
  375.      demo(N,1);
  376.  
  377. }
  378.