home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / prog / plane / voro_test.c < prev   
C/C++ Source or Header  |  1996-09-03  |  2KB  |  95 lines
  1. #include <LEDA/plane_alg.h>
  2.  
  3.  
  4. random_source& operator>>(random_source& R, point& p)
  5. { double x,y;
  6.   R >> x >>y;
  7.   p = point(x,y);
  8.   return R;
  9. }
  10.  
  11.  
  12. main()
  13. {
  14.    int N = read_int("N = ");
  15.  
  16.    list<point>     L;
  17.    list<rat_point> L1;
  18.    random_source ran(0,100000);
  19.  
  20.    ran.set_seed(12345*N);
  21.  
  22.    for(int i=0; i<N; i++) 
  23.    { int x,y;
  24.      ran >> x >> y;
  25.      L.append(point(x,y));
  26.      L1.append(rat_point(x,y));
  27.     }
  28.  
  29.  
  30.   // flipping with floating point points
  31.  
  32.   GRAPH<point,edge>  D1;
  33.   GRAPH<circle,point> V1;
  34.  
  35.   list<edge> d_list;
  36.  
  37.   float T, t1, t2, t3;
  38.  
  39. /*
  40.   cout << "DELAUNAY FLIP0(float) " << flush;
  41.   T = used_time();
  42.   TRIANGULATE_POINTS(L,D1);
  43.   t1 = used_time(T);
  44.   DELAUNAY_FLIPPING(D1);
  45.   t2 = used_time(T);
  46.   DELAUNAY_TO_VORONOI_OLD(D1,V1);
  47.   t3 = used_time(T);
  48.   cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
  49.           V1.number_of_nodes(), V1.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;
  50. */
  51.  
  52.  
  53.   cout << "DELAUNAY FLIP(float)  " << flush;
  54.   T = used_time();
  55.   TRIANGULATE_POINTS(L,D1);
  56.   t1 = used_time(T);
  57.   DELAUNAY_FLIPPING(D1,d_list);
  58.   t2 = used_time(T);
  59.   DELAUNAY_TO_VORONOI(D1,V1);
  60.   t3 = used_time(T);
  61.   cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
  62.           V1.number_of_nodes(), V1.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;
  63.  
  64.   // flipping with rational points
  65.  
  66.   GRAPH<rat_point,edge> D2;
  67.   GRAPH<rat_circle,rat_point> V2;
  68.  
  69. /*
  70.   cout << "DELAUNAY FLIP0(exact) " << flush;
  71.   T = used_time();
  72.   TRIANGULATE_POINTS(L1,D2);
  73.   t1 = used_time(T);
  74.   DELAUNAY_FLIPPING(D2);
  75.   t2 = used_time(T);
  76.   DELAUNAY_TO_VORONOI_OLD(D2,V2);
  77.   t3 = used_time(T);
  78.   cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
  79.           V2.number_of_nodes(), V2.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;
  80. */
  81.  
  82.  
  83.   cout << "DELAUNAY FLIP(exact)  " << flush;
  84.   T = used_time();
  85.   TRIANGULATE_POINTS(L1,D2);
  86.   t1 = used_time(T);
  87.   DELAUNAY_FLIPPING(D2,d_list);
  88.   t2 = used_time(T);
  89.   DELAUNAY_TO_VORONOI(D2,V2);
  90.   t3 = used_time(T);
  91.   cout << string("|V| = %d  |E| = %d  time = %.2f (%.2f + %.2f + %.2f)",
  92.           V2.number_of_nodes(), V2.number_of_edges()/2,t1+t2+t3,t1,t2,t3) << endl;
  93.  return 0;
  94. }
  95.