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

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

数值算法/人工智能

开发平台：

MultiPlatform

triang.c：源码内容
  1. #include <LEDA/plane.h>
  2. #include <LEDA/d_array.h>
  3. #include <LEDA/graph.h>
  4. #include <LEDA/window.h>
  6. window W;
  8. void TRIANG(list<point> L, GRAPH<point,int>& G)
  9. { 
  10.   if (L.length() < 3) return;
  12.   list<point> CH;
  13.   list_item last;
  15.   L.sort();  // sort points lexicographically
  17.   d_array<point,node> V(nil);
  21.   // initialize convex hull with first two points
  23.   point p = L.pop();
  24.   V[p] = G.new_node(p);
  25.   CH.append(p);
  27.   while (L.head() == p) L.pop();
  28.   point q = L.pop();
  29.   last = CH.append(q);
  30.   V[q] = G.new_node(q);
  32.   G.new_edge(V[p],V[q]);
  35.   // scan remaining points
  37.   forall(p,L)
  38.   {
  39.     if (p == CH[last]) continue;  // multiple point
  41.     node v = G.new_node(p);
  43.     V[p] = v;
  45.     G.new_edge(v,V[CH[last]]);
  47.     // compute upper tangent (p,up)
  49.     list_item up = last;
  50.     list_item it = CH.cyclic_succ(up);
  52.     while (left_turn(CH[it],CH[up],p))
  53.     { up = it;
  54.       it = CH.cyclic_succ(up);
  55.       G.new_edge(v,V[CH[up]]);
  56.      }
  59.     // compute lower tangent (p,low)
  61.     list_item low = last;
  62.     it = CH.cyclic_pred(low);
  64.     while (right_turn(CH[it],CH[low],p))
  65.     { low = it;
  66.       it = CH.cyclic_pred(low);
  67.       G.new_edge(v,V[CH[low]]);
  68.      }
  71.     // remove all points between up and low
  73.     if (up != low)
  74.     { it = CH.cyclic_succ(low);
  76.       while (it != up)
  77.       { CH.del(it);
  78.         it = CH.cyclic_succ(low);
  79.        }
  80.      }
  82.     // insert new point
  84.     last = CH.insert(p,low);
  86.    }
  88. }
  89.      
  92. main()
  93. {
  94.   //window W;
  95.   W.init(-100,100,-100);
  96.   W.set_node_width(5);
  98.   int N = 500;
  100.   panel P("triangulation");
  102.   P.int_item("# points",N,1,2000);
  103.   int b1 = P.button("mouse");
  104.   int b2 = P.button("random");
  105.   int b3 = P.button("quit");
  107.   for(;;)
  108.   { 
  109.     list<point> L;
  110.     point p,q;
  112.     int but = P.open();
  114.     W.clear();
  116.     if (but == b1)
  117.       while (W >> p)
  118.       { W.draw_point(p,blue);
  119.         L.append(p);
  120.        }
  122.     if (but == b2)
  123.       for(int i = 0; i<N; i++) 
  124.       { point p(rand_int(-90,90),rand_int(-90,90));
  125.         W.draw_point(p,blue);
  126.         L.append(p);
  127.        }
  129.     if (but == b3) break;
  130.   
  131.     GRAPH<point,int> G;
  132.     TRIANG(L,G);
  133.   
  134.     edge e;
  135.     forall_edges(e,G)
  136.        W.draw_segment(G[source(e)],G[target(e)],violet);
  137.   }
  138.    
  139.  return 0;
  140. }