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

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

数值算法/人工智能

开发平台：

MultiPlatform

_delaunay.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _delaunay.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. #include <LEDA/plane_alg.h>
  15. #include <LEDA/planar_map.h>
  17. typedef point   POINT;
  19. // in the current version we use GRAPH<POINT,edge> for representing
  20. // planar maps ( G[e] = rev(e) )
  23. static int flip_count = 0;
  25. inline bool flip_test(const GRAPH<POINT,edge>& G, edge e)
  26. { POINT a = G[source(e)];
  27.   POINT b = G[target(G.cyclic_adj_pred(e))];
  28.   POINT c = G[target(e)];
  29.   POINT d = G[target(G.cyclic_adj_succ(e))];
  30.   return right_turn(b,a,d) && right_turn(b,d,c) && incircle(a,b,c,d);
  31.  }
  34. static void DELAUNAY_FLIPPING(GRAPH<POINT,edge>& G)
  35. {
  36.   edge_map<list_item> It(G,nil);
  37.   list<edge> L;
  38.   edge E[4];
  41.   edge e;
  42.   forall_edges(e,G) 
  43.     if (It[e] == nil && flip_test(G,e)) It[G[e]] = It[e] = L.append(e);
  45.   while ( !L.empty() )
  46.   { flip_count++;
  48.     edge e = L.pop();
  49.     edge x = G.cyclic_adj_pred(e); 
  51.     // delete diagonal
  52.     G.del_edge(G[e]);
  53.     G.del_edge(e);
  55.     // collect face edges of quadriliteral
  56.     for(int i = 0; i < 4; i++) 
  57.     { E[i] = x; 
  58.       x = G.cyclic_adj_pred(G[x]);
  59.      }
  61.     // insert new diagonal
  62.     e = G.new_edge(E[1],source(E[3]),nil);
  63.     G[e] = G.new_edge(E[3],source(E[1]),e);
  66.     // test collected edges 
  67.     for(int j=0; j<4; j++)
  68.     { edge e = E[j];
  69.       if (flip_test(G,e))
  70.         { if (It[e] == nil) 
  71.           It[G[e]] = It[e] = L.push(e); 
  72.          }
  73.       else
  74.           if (It[e] != nil)
  75.           { L.del_item(It[e]);
  76.             It[G[e]] = It[e] = nil;
  77.            }
  78.      }
  80.    }
  81.  }
  85. void DELAUNAY_TRIANG(const list<POINT>& L, GRAPH<POINT,edge>& T)
  86. {
  87.   TRIANGULATE_POINTS(L,T);
  88.   DELAUNAY_FLIPPING(T);
  89. }
  92. void DELAUNAY_TRIANG(const list<POINT>& L, graph& T, 
  93.                                            node_array<POINT>& pos,
  94.                                            edge_array<edge>&  rev)
  95. { GRAPH<POINT,edge> G;
  96.   DELAUNAY_TRIANG(L,G);
  98.   T = G;
  100.   node v;
  101.   pos.init(T);
  102.   forall_nodes(v,G) pos[v] = G[v];
  104.   edge e;
  105.   rev.init(T);
  106.   forall_edges(e,G) rev[e] = G[e];
  107. }
  110. void DELAUNAY_TRIANG(const list<POINT>& L, planar_map& T, 
  111.                                            node_array<POINT>& pos)
  112. { GRAPH<POINT,edge> G;
  113.   DELAUNAY_TRIANG(L,G);
  115.   T = G;
  117.   node v;
  118.   pos.init(T);
  119.   forall_nodes(v,G) pos[v] = G[v];
  120. }