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

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

数值算法/人工智能

开发平台：

MultiPlatform

_voronoi.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _voronoi.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/plane_alg.h>
  14. #include <LEDA/impl/delaunay_tree.h>
  15. #include <LEDA/d_array.h>
  18. static d_array<point,node>* VP;
  20. static GRAPH<point,point>*  G;
  22. static double infi_length;
  24. static point* XP;
  27. static void trace_segment(double x1, double y1, double x2, double y2, 
  28.                    double sx0, double sy0)
  29. {
  30.   point p(x1,y1);
  31.   point q(x2,y2);
  32.   point s(sx0,sy0);
  34.   node v,w;
  36.   if ((v = (*VP)[p]) == nil) (*VP)[p] = v = G->new_node(p);
  37.     
  38.   if ((w = (*VP)[q]) == nil) (*VP)[q] = w = G->new_node(q);
  40.   G->new_edge(v,w,s);
  43. }
  46. static void infi_point(double x1, double y1, double x2, double y2, double* x, double* y)
  47. {
  48.   vector v(x2,y2);
  50.   v = v.norm();
  52.   *x = x1 + infi_length * v[0];
  53.   *y = y1 + infi_length * v[1];
  55. }
  58. static int cmp_infi_pts(const point& p, const point& q)
  59. { // used to sort infi points clockwise around XP
  60.   segment  s1(*XP,p);
  61.   segment  s2(*XP,q);
  62.   return compare(s2.angle(),s1.angle());
  63. }
  66. void VORONOI(list<point>& site_list, double R, GRAPH<point,point>& VD)
  67. { 
  68.    if (site_list.empty()) return;
  70.    d_array<point,node> V(nil);
  72.    point X = site_list.head();
  74.    VP = &V;
  75.    XP = &X;
  77.    delaunay_tree DT;
  79.    point p,q;
  80.    node v;
  82.    list<point> infi_list;
  84.    forall(p,site_list) DT.insert(p,0);
  86.    infi_length = R;
  88.    G = &VD;
  90.    DT.trace_voronoi_edges(trace_segment, infi_point, 1);
  93.    // sort & link infinite points
  95.    forall_nodes(v,VD) 
  96.      if (VD.outdeg(v) == 1) infi_list.append(VD[v]);
  98.    infi_list.sort(cmp_infi_pts);
  100.    point INFI(MAXDOUBLE,MAXDOUBLE);  
  102.    list_item it;
  104.    forall_items(it,infi_list)
  105.    {  node p = V[infi_list[it]];
  106.       node q = V[infi_list[infi_list.cyclic_succ(it)]];
  107.       point s = VD[VD.first_adj_edge(q)];
  108.       VD.new_edge(p,q,s); 
  109.     }
  111.    forall_items(it,infi_list)
  112.    {  node p = V[infi_list[it]];
  113.       node q = V[infi_list[infi_list.cyclic_pred(it)]];
  114.       VD.new_edge(p,q,INFI);  
  115.     }
  117.    V.clear();
  119. }