home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / prog / graphics / arrange1.c next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.4 KB  |  121 lines
  1. #include <LEDA/subdivision.h>
  2. #include <LEDA/plane.h>
  3. #include <LEDA/window.h>
  4.  
  5. declare(subdivision,int)
  6.  
  7. declare(edge_array,real)
  8.  
  9.  
  10. void  show_face(subdivision(int)& G, face f, window& W)
  11. { list(node) L = G.adj_nodes(f);
  12.   list(point) P;
  13.   node v;
  14.   forall(v,L) P.append(G[v]);
  15.   W.draw_filled_polygon(P,red);
  16. }
  17.  
  18.  
  19. main()
  20. {
  21.  
  22.   window W;
  23.  
  24.   W.init(0,1000,0);
  25.  
  26.   W.message("            Arrangement of line segments                ");
  27.   W.message("                                                        ");
  28.   W.message("This program computes an arrangement of straight lines. ");
  29.   W.message("Use the left button to insert a sequence of lines and ");
  30.   W.message("terminate the input by clicking the right button. Now");
  31.   W.message("you can input query points with the left button. For ");
  32.   W.message("each point p the face of the arrangment containing p ");
  33.   W.message("is computed and displayed. Terminate the program by  "); 
  34.   W.message("pressing the right mouse key.                        ");
  35.   W.message("                                                     ");
  36.   W.message("Click any button to start.                           ");
  37.   W.read_mouse();
  38.   W.clear();
  39.  
  40.  
  41.  
  42.   list(segment) seglist1,seglist2;
  43.  
  44.   // build up a frame
  45.  
  46.   real x0 = W.xmin();
  47.   real x1 = W.xmax();
  48.   real y0 = W.ymin();
  49.   real y1 = W.ymax();
  50.  
  51.   segment b(x0,y0,x1,y0);
  52.   segment t(x0,y1,x1,y1);
  53.   segment l(x0,y0,x0,y1);
  54.   segment r(x1,y0,x1,y1);
  55.  
  56.   seglist1.append(b);
  57.   seglist1.append(t);
  58.   seglist1.append(l);
  59.   seglist1.append(r);
  60.  
  61.   line L;
  62.  
  63.   while ( W >> L ) 
  64.   {  W << L;
  65.      if (L.vertical()) 
  66.         seglist1.append(segment(L.x_proj(y0),y0,L.x_proj(y1),y1));
  67.      else 
  68.         seglist1.append(segment(x0,L.y_proj(x0),x1,L.y_proj(x1)));
  69.    }
  70.  
  71.   W.message("Computing subdivision");
  72.   newline;
  73.  
  74.   GRAPH(point,int) G;
  75.  
  76.   SWEEP_SEGMENTS(seglist1,seglist2,G);
  77.  
  78.  
  79.   // insert reverse edges
  80.  
  81.   edge e;
  82.   list(edge) E = G.all_edges();
  83.   forall(e,E) G.new_edge(target(e),source(e),G[e]);
  84.  
  85.   // sort edges counter-clockwise
  86.  
  87.   edge_array(real) angle(G);
  88.  
  89.   forall_edges(e,G)
  90.   { segment s(G[source(e)],G[target(e)]);
  91.     angle[e] = s.angle();
  92.    }
  93.  
  94.   G.sort_edges(angle);
  95.  
  96.   subdivision(int) S(G);
  97.  
  98.   W.clear(); 
  99.   W.set_line_width(2);
  100.  
  101.   forall_edges(e,G)
  102.   W.draw_segment(G[source(e)], G[target(e)],blue);
  103.  
  104.  
  105.   // Locate points
  106.  
  107.   W.set_mode(xor_mode);
  108.  
  109.   point p;
  110.   face  f=nil;
  111.  
  112.   W.message("Give query points !");
  113.  
  114.   while (W >> p)
  115.   { if (f) show_face(S,f,W);
  116.     f = S.locate_point(p);
  117.     show_face(S,f,W);
  118.    }
  119.  
  120. }
  121.