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

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

数值算法/人工智能

开发平台：

MultiPlatform

dtriang.c：源码内容
  2. #include <LEDA/plane_alg.h>
  3. #include <LEDA/point.h>
  4. #include <LEDA/matrix.h>
  7. bool incircle(const point& a, const point& b, const point& c, const point& d)
  8. {
  9.    double ax = a.xcoord();
  10.    double ay = a.ycoord();
  12.    double bx = b.xcoord() - ax;
  13.    double by = b.ycoord() - ay;
  14.    double bw = bx*bx + by*by;
  16.    double cx = c.xcoord() - ax;
  17.    double cy = c.ycoord() - ay;
  18.    double cw = cx*cx + cy*cy;
  20.    double dx = d.xcoord() - ax;
  21.    double dy = d.ycoord() - ay;
  22.    double dw = dx*dx + dy*dy;
  24.    //return (by*cw-cy*bw) * (bx*dw-dx*bw) > (bx*cw-cx*bw) * (by*dw-dy*bw);
  26.    return ((by*cx-bx*cy)*dw + (cy*bw-by*cw)*dx  + (bx*cw-cx*bw)*dy)  > 0;
  27.  }
  31. static int flip_count = 0;
  33. inline bool flip_test(const GRAPH<point,edge>& G, edge e)
  34. { point a = G[source(e)];
  35.   point b = G[target(G.cyclic_adj_pred(e))];
  36.   point c = G[target(e)];
  37.   point d = G[target(G.cyclic_adj_succ(e))];
  38.   return right_turn(b,a,d) && right_turn(b,d,c) && incircle(a,b,c,d);
  39.  }
  43. void DELAUNAY_FLIPPING(GRAPH<point,edge>& G)
  44. {
  45.   edge_map<list_item> It(G,nil);
  46.   list<edge> L;
  47.   edge E[4];
  49. #define next_face_edge(x)  G.cyclic_adj_pred(G[x])
  51.   edge e;
  52.   forall_edges(e,G) 
  53.     if (It[e] == nil && flip_test(G,e)) It[G[e]] = It[e] = L.append(e);
  55.   while ( !L.empty() )
  56.   { flip_count++;
  58.     edge e = L.pop();
  59.     edge x = G.cyclic_adj_pred(e); 
  61.     // delete diagonal
  62.     G.del_edge(G[e]);
  63.     G.del_edge(e);
  65.     // collect face edges of quadriliteral
  66.     for(int i = 0; i < 4; i++) 
  67.     { E[i] = x; 
  68.       x = next_face_edge(x); 
  69.      }
  71.     // insert new diagonal
  72.     e = G.new_edge(E[1],source(E[3]),nil);
  73.     G[e] = G.new_edge(E[3],source(E[1]),e);
  76.     // test collected edges 
  77.     for(int j=0; j<4; j++)
  78.     { edge e = E[j];
  79.       if (flip_test(G,e))
  80.         { if (It[e] == nil) 
  81.           It[G[e]] = It[e] = L.push(e); 
  82.          }
  83.       else
  84.           if (It[e] != nil)
  85.           { L.del_item(It[e]);
  86.             It[G[e]] = It[e] = nil;
  87.            }
  88.      }
  90.    }
  91.  }
  94. random_source& operator>>(random_source& R, point& p)
  95. { double x,y;
  96.   R >> x >>y;
  97.   p = point(x,y);
  98.   return R;
  99. }
  101. main()
  102. {
  103.    int N = read_int("N = ");
  105.    list<point> L;
  106.    random_source ran(0,1000);
  108.    ran.set_seed(12345*N);
  110.    for(int i=0; i<N; i++) 
  111.    { point p;
  112.      ran >> p;
  113.      L.append(p);
  114.     }
  116.    GRAPH<point,edge> G;
  118.    float T = used_time();
  120.    flip_count = 0;
  121.    TRIANGULATE_POINTS(L,G);
  122.    DELAUNAY_FLIPPING(G);
  123.    cout << string("flips = %d   time = %.2f", flip_count,used_time(T)) << endl;
  125.    return 0;
  126. }