home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / graph_al / _triangu.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  4.5 KB  |  160 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _triangulation.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  TRIANGULATE_PLANAR_MAP  (triangulation)                                     *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24.  
  25. #include <LEDA/graph_alg.h>
  26.  
  27. /*
  28. #include <LEDA/d_array.h>
  29.  
  30. declare2(d_array,edge,edge)
  31. */
  32.  
  33.  
  34. #define NEXT_FACE_EDGE(e) G.cyclic_adj_pred(REV[e]) 
  35.  
  36. list(edge) TRIANGULATE_PLANAR_MAP(graph& G)
  37.  
  38. /*
  39.    G is a planar map. This procedure triangulates all faces of G
  40.    without introducing multiple edges. The algorithm was suggested by 
  41.    Christian Uhrig and Torben Hagerup. First implementation 9/5/88
  42.  
  43.    Description:
  44.  
  45.    Triangulating a planar graph G, i.e., adding edges
  46.    to G to obtain a chordal planar graph, in linear time:
  47.    
  48.    1) Compute a (combinatorial) embedding of G.
  49.    
  50.    2) Step through the vertices of G. For each vertex u,
  51.    triangulate those faces incident on u that have not
  52.    already been triangulated. For each vertex u, this
  53.    consists of the following:
  54.    
  55.      a) Mark the neighbours of u. During the processing
  56.    of u, a vertex will be marked exactly if it is a
  57.    neighbour of u.
  58.    
  59.      b) Process in any order those faces incident on u
  60.    that have not already been triangulated. For each such
  61.    face with boundary vertices u=x_1,...,x_n,
  62.         I)   If n=3, do nothing; otherwise
  63.         II)  If x_3 is not marked, add an edge {x_1,x_3},
  64.              mark x_3 and continue triangulating the face
  65.              with boundary vertices x_1,x_3,x_4,...,x_n.
  66.         III) If x_3 is marked, add an edge {x_2,x_4} and
  67.              continue triangulating the face with boundary
  68.              vertices x_1,x_2,x_4,x_5,...,x_n.
  69.    
  70.      c) Unmark the neighbours of x_1.
  71.    
  72.    Proof of correctness:
  73.    
  74.    A) All faces are triangulated.
  75.    This is rather obvious.
  76.    
  77.    B) There will be no multiple edges.
  78.    During the processing of a vertex u, the marks on
  79.    neighbours of u clearly prevent us from adding a multiple
  80.    edge with endpoint u. After the processing of u, such an
  81.    edge is not added because all faces incident on u have
  82.    been triangulated. This takes care of edges added in
  83.    step II).
  84.    Whenever an edge {x_2,x_4} is added in step III), the
  85.    presence of an edge {x_1,x_3} implies, by a topological
  86.    argument, that x_2 and x_4 are incident on exactly one
  87.    common face, namely the face currently being processed.
  88.    Hence we never add another edge {x_2,x_4}.
  89.    
  90. */
  91.    
  92. { 
  93.  
  94.   node v;
  95.   edge x;
  96.   list(edge) L;
  97.  
  98.   node_array(int)  marked(G,0);
  99.  
  100.   edge_array(edge) REV(G, 3*G.number_of_edges(), nil);
  101.  
  102.   compute_correspondence(G,REV);
  103.  
  104. /*
  105.   d_array(edge,edge) reversal;
  106.   forall_edges(x,G) reversal[x] = REV[x]; 
  107. */
  108.  
  109.   forall_nodes(v,G)
  110.   {
  111.     edgelist El = G.adj_edges(v);
  112.     edge e,e1,e2,e3;
  113.  
  114.     forall(e,El) marked[target(e)]=1;
  115.  
  116.     forall(e,El)
  117.     { 
  118.       e1 = e;
  119.       e2 = NEXT_FACE_EDGE(e1);
  120.       e3 = NEXT_FACE_EDGE(e2);
  121.  
  122.       while (target(e3) != v)
  123.       // e1,e2 and e3 are the first three edges in a clockwise 
  124.       // traversal of a face incident to v and t(e3) is not equal
  125.       // to v.
  126.        if ( !marked[target(e2)] )
  127.         { // we mark w and add the edge {v,w} inside F, i.e., after
  128.           // dart e1 at v and after dart e3 at w.
  129.  
  130.           marked[target(e2)] = 1;
  131.           L.append(x  = G.new_edge(e3,source(e1)));
  132.           L.append(e1 = G.new_edge(e1,source(e3)));
  133.           REV[x] = e1;
  134.           REV[e1] = x;
  135.           e2 = e3;
  136.           e3 = NEXT_FACE_EDGE(e2);
  137.         }
  138.         else
  139.         { // we add the edge {source(e2),target(e3)} inside F, i.e.,
  140.           // after dart e2 at source(e2) and before dart 
  141.           // reversal_of[e3] at target(e3).
  142.  
  143.           e3 = NEXT_FACE_EDGE(e3); 
  144.           L.append(x  = G.new_edge(e3,source(e2)));
  145.           L.append(e2 = G.new_edge(e2,source(e3)));
  146.           REV[x] = e2;
  147.           REV[e2] = x;
  148.         }
  149.      //end of while
  150.  
  151.     } //end of stepping through incident faces
  152.  
  153.    node w; forall_adj_nodes(w,v) marked[w] = 0;
  154.  
  155.   } // end of stepping through nodes
  156.  
  157. return L;
  158.  
  159. } //end of triangulation
  160.