Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_triang.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 2k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_triang.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _triang.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>
  15. typedef point  POINT;
  18. void TRIANGULATE_POINTS(list<POINT> L, GRAPH<POINT,edge>& G)
  19. { 
  20.   L.sort();  // sort pointss lexicographically
  22.   // eliminate multiple points
  24.   list_item it;
  25.   forall_items(it,L)
  26.   { list_item it1 = L.succ(it);
  27.     while (it1 != nil && L[it1] == L[it])
  28.     { L.del(it1);
  29.       it1 = L.succ(it);
  30.      }
  31.    }
  33.   // initialize convex hull with first three points
  35.   node u = G.new_node(L.pop());
  36.   node v = G.new_node(L.pop());
  37.   node w = G.new_node(L.pop());
  39.   edge e1 = G.new_edge(u,v,nil);
  40.   G[e1] = G.new_edge(v,u,e1);
  41.   edge e2 = G.new_edge(v,w,nil);
  42.   G[e2] = G.new_edge(w,v,e2);
  43.   edge e3 = G.new_edge(w,u,nil);
  44.   G[e3] = G.new_edge(u,w,e3);
  46.   edge last =  ( orientation(G[w],G[v],G[u]) < 0 ) ? G[e2] : e3;
  48.   // scan remaining points
  50.   POINT p;
  51.   forall(p,L) 
  52.   {
  53.     node  v = G.new_node(p);
  55.     // compute upper tangent (p,up)
  56.     edge up = last;
  57.     while (right_turn(p,G[source(up)],G[target(up)]))
  58.          up = G.cyclic_adj_succ(G[up]);
  60.     // compute lower tangent (p,low)
  61.     edge low = G[G.cyclic_adj_pred(last)];
  62.     while (left_turn(p,G[target(low)],G[source(low)]))
  63.          low = G[G.cyclic_adj_pred(low)];
  65.     // triangulate 
  66.     edge e = up; 
  67.     do { edge next = G[G.cyclic_adj_pred(e)];
  68.          edge x = G.new_edge(v,source(e),nil);
  69.          G[x] = G.new_edge(e,v,x,before);
  70.          e = next;
  71.         } while (e != low);
  72.     last = G.first_adj_edge(v);
  73.    }
  75. // if (!PLANAR(G)) error_handler(1,"graph not planar");
  76. }