开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
triang_demo.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：4k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

triang_demo.c：源码内容
  1. #include <LEDA/window.h>
  2. #include <LEDA/plane_alg.h>
  3. #include <LEDA/point.h>
  4. #include <LEDA/map.h>
  6. window W;
  8. void draw_circle(window& W, point a, point b, point c)
  9. { line L1 = p_bisector(a,b);
  10.   line L2 = p_bisector(a,c);
  11.   point m;
  12.   L1.intersection(L2,m);
  13.   W.draw_disc(m,m.distance(a),violet);
  14. }
  16. static int  flip_count = 0;
  17. static int  visited_edges = 0;
  18. static int  speed = 40;
  19. static bool animate = false;
  21. void animate_flip(point a, point b, point c, point d, int n)
  22. {
  23.   W.del_messages();
  24.   W.message(string(" %2d flips",flip_count++));
  25.   
  26.   segment s1(a,b);
  27.   segment s2(c,d);
  28.   double l1 = s1.length()/n;
  29.   double l2 = s2.length()/n;
  30.   double a1 = s1.angle(); 
  31.   double a2 = s2.angle(); 
  33.   while (n--)
  34.   { point a_new = a.translate(a1,l1);
  35.     point c_new = c.translate(a2,l2);
  36.     W.draw_edge(a_new,c_new,red);
  37.     W.draw_edge(a,c,red);
  38.     a = a_new;
  39.     c = c_new;
  40.    }
  41.   W.draw_edge(a,c,red);
  42.   W.draw_edge(a,c,blue);
  44. }
  45.    
  47.   
  49. void flipping(GRAPH<point,edge> &G)
  50. {
  51.   edge_map<bool> marked(G,false);
  52.   list<edge> L;
  53.   edge e;
  55.   forall_edges(e,G)  marked[e] = false;
  57.   forall_edges(e,G) 
  58.     if ( !marked[e] )
  59.     { L.append(e);
  60.       marked[e] = true;
  61.       marked[G[e]] = true;
  62.       if (animate) W.draw_edge(G[source(e)],G[target(e)],red);
  63.      }
  66.   while ( !L.empty() )
  67.   { visited_edges++;
  68.     edge e = L.pop();
  69.     marked[e] = false;
  70.     marked[G[e]] = false;
  72.     edge e1 =  G.cyclic_adj_pred(e); 
  73.     edge e2 =  G.cyclic_adj_pred(G[e1]); 
  74.     edge e3 =  G.cyclic_adj_pred(G[e]); 
  75.     edge e4 =  G.cyclic_adj_pred(G[e3]); 
  77.     point a = G[source(e1)];
  78.     point b = G[source(e2)];
  79.     point c = G[source(e3)];
  80.     point d = G[source(e4)];
  82.     if ( orientation(b,a,d) > 0 && orientation(b,d,c) > 0
  83.          && incircle(a,b,c,d) > 0)
  84.     { 
  85.       if (animate) animate_flip(a,b,c,d,8000/speed);
  87.       G.del_edge(G[e]);
  88.       G.del_edge(e);
  89.       e = G.new_edge(e2,source(e4),nil);
  90.       G[e] = G.new_edge(e4,source(e2),e);
  91.       marked[e] = false;
  92.       marked[G[e]] = false;
  94.       if ( !marked[e1]) 
  95.       { L.append(e1); 
  96.         marked[e1] = marked[G[e1]] = true; 
  97.         if (animate)
  98.         { W.draw_edge(a,b,blue);
  99.           W.draw_edge(a,b,red);
  100.          }
  101.        }
  103.       if ( !marked[e2]) 
  104.       { L.append(e2); 
  105.         marked[e2] = marked[G[e2]] = true; 
  106.         if (animate)
  107.         { W.draw_edge(b,c,blue);
  108.           W.draw_edge(b,c,red);
  109.          }
  110.        }
  112.       if ( !marked[e3]) 
  113.       { L.append(e3); 
  114.         marked[e3] = marked[G[e3]] = true; 
  115.         if (animate)
  116.         { W.draw_edge(c,d,blue);
  117.           W.draw_edge(c,d,red);
  118.          }
  119.        }
  121.       if ( !marked[e4]) 
  122.       { L.append(e4); 
  123.         marked[e4] = marked[G[e4]] = true; 
  124.         if (animate)
  125.         { W.draw_edge(d,a,blue);
  126.           W.draw_edge(d,a,red);
  127.          }
  128.        }
  129.      }
  130.      else
  131.      if (animate)
  132.      { W.draw_edge(a,c,red);
  133.        W.draw_edge(a,c,blue);
  134.       }
  135.    }
  137. }
  141. random_source& operator>>(random_source& R, point& p)
  142. { double x,y;
  143.   R >> x >>y;
  144.   p = point(100*x,100*y);
  145.   return R;
  146. }
  148. main()
  149. {
  150.    int N = 100;
  151.    bool grid = false;
  153.    panel P;
  155.    P.int_item("speed",speed,1,100);
  156.    P.bool_item("animate",animate);
  157.    P.bool_item("grid",grid);
  158.    P.int_item("#points",N,0,500);
  159.    P.open();
  162.    list<point> L;
  163.    random_source ran(0,1000);
  165. //window W;
  166. W.init(-5,105,-5);
  167. if (grid) W.set_grid_mode(2);
  168. W.set_node_width(2);
  170. L.append(point(0,0));
  171. L.append(point(100,0));
  172. L.append(point(50,100));
  174. point p;
  175. for(int i=0; i<N; i++) 
  176. { ran >> p;
  177.   L.append(p);
  178.  }
  180. forall(p,L) W.draw_filled_node(p);
  182. GRAPH<point,edge> G;
  184. TRIANGULATE_POINTS(L,G);
  186. W.set_mode(xor_mode);
  187. flipping(G);
  188. W.set_mode(src_mode);
  190. W.set_flush(false);
  191. edge e;
  192. forall_edges(e,G) W.draw_edge(G[source(e)],G[target(e)],blue);
  193. W.flush();
  195. W.set_mode(xor_mode);
  197. while (W >> p)
  198. {
  199.   forall_edges(e,G)
  200.   { edge e1 = e;
  201.     edge e2 = G.cyclic_adj_pred(G[e1]);
  202.     edge e3 = G.cyclic_adj_pred(G[e2]);
  204.     point a = G[source(e1)];
  205.     point b = G[source(e2)];
  206.     point c = G[source(e3)];
  208.     if ( left_turn(a,b,p) && left_turn(b,c,p) && left_turn(c,a,p) )
  209.     {
  210.       W.draw_filled_node(p);
  211.       //W.draw_edge(p,a,red);
  212.       //W.draw_edge(p,b,red);
  213.       //W.draw_edge(p,c,red);
  215.       node v = G.new_node(p);
  217.       edge x = G.new_edge(e1,v,nil);
  218.       G[x] = G.new_edge(v,source(e1),x);
  219.       x = G.new_edge(e2,v,nil);
  220.       G[x] = G.new_edge(v,source(e2),x);
  221.       x = G.new_edge(e3,v,nil);
  222.       G[x] = G.new_edge(v,source(e3),x);
  223.       break;
  224.     }
  225.   }
  227.   W.clear();
  228.   node v;
  229.   forall_nodes(v,G) W.draw_filled_node(G[v]);
  231.   animate = true;
  232.   flipping(G);
  233. }
  235. return 0;
  236. }