home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / plane / _convex_.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.0 KB  |  184 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _convex_hull.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. #include <LEDA/plane.h>
  17. #include <LEDA/graph.h>
  18.  
  19.  
  20. struct p_edge {
  21.  
  22. segment   s;
  23. list_item it;
  24.  
  25. OPERATOR_NEW(2)
  26. OPERATOR_DEL(2)
  27.  
  28.  
  29. };
  30.  
  31. typedef p_edge* p_edge_ptr;
  32.  
  33. void Clear(p_edge_ptr& p) { delete p; }
  34.  
  35.  
  36.  
  37. declare2(GRAPH,p_edge_ptr,int)
  38. GRAPH(p_edge_ptr,int) DAG;
  39. list(node) POL;
  40.  
  41.  
  42.  
  43. node NEW_NODE(segment s)
  44. { p_edge_ptr p = new p_edge;
  45.   p->s =s;
  46.   return DAG.new_node(p);
  47.  }
  48.  
  49.  
  50.  
  51.  
  52. node next_segment(segment s, node v )
  53. { node u = nil;
  54.   node w;
  55.   point Q;
  56.   forall_adj_nodes(w,v)
  57.     if (s.intersection(DAG[w]->s,Q)) 
  58.     { u = w;
  59.       break;
  60.      }
  61.   DAG.init_adj_iterator(v);
  62.   return u;
  63. }
  64.  
  65.  
  66.  
  67. polygon CONVEX_HULL(list(point) L)
  68. { 
  69.  
  70.  
  71.   point A,B,C;
  72.  
  73.   A = L.pop();
  74.   B = L.pop();
  75.   C = L.pop();
  76.  
  77.   segment sa(A,B);
  78.   segment sb(B,C);
  79.   segment sc(C,A);
  80.  
  81.   if (sa.angle(sb) < 0) 
  82.   { sa = segment(A,C);
  83.     sb = segment(C,B);
  84.     sc = segment(B,A);
  85.    }
  86.  
  87.   node root = NEW_NODE(segment(A,A));
  88.   node    a = NEW_NODE(sa);
  89.   node    b = NEW_NODE(sb);
  90.   node    c = NEW_NODE(sc);
  91.  
  92.   //DAG edges
  93.  
  94.   DAG.new_edge(root,a,0);
  95.   DAG.new_edge(root,b,0);
  96.   DAG.new_edge(root,c,0);
  97.  
  98.   //POL is initialized to triangle (A,B,C);
  99.  
  100.   DAG[a]->it = POL.append(a);
  101.   DAG[b]->it = POL.append(b);
  102.   DAG[c]->it = POL.append(c);
  103.  
  104.   double x = (A.xcoord() + B.xcoord() + C.xcoord())/3;
  105.   double y = (A.ycoord() + B.ycoord() + C.ycoord())/3;
  106.  
  107.   point I(x,y);
  108.  
  109.   point P;
  110.  
  111.   while (!L.empty())
  112.   { 
  113.     P = L.pop();
  114.  
  115.     point   Q;
  116.  
  117.     segment S(P,I);
  118.  
  119.     node v = root;
  120.  
  121.     while (v!=nil && DAG.outdeg(v)!=0) v = next_segment(S,v);
  122.  
  123.     if (v==nil) continue;
  124.  
  125.      list_item it;
  126.  
  127.  
  128.      point   rtouch  = DAG[v]->s.start();
  129.      segment rtangent(P,rtouch);
  130.      node    w = v;
  131.  
  132.      it = DAG[w]->it;
  133.      while (rtangent.angle(DAG[w]->s) <= 0) 
  134.      { 
  135.        it = POL.cyclic_succ(it);
  136.        w = POL[it];
  137.        rtouch   = DAG[w]->s.start();
  138.        rtangent = segment(P,rtouch);
  139.       }
  140.  
  141.      point   ltouch   = DAG[v]->s.end();
  142.      segment ltangent(ltouch,P);
  143.      node    u = v;
  144.  
  145.      it = DAG[u]->it;
  146.      while (ltangent.angle(DAG[u]->s) >= 0) 
  147.      { it = POL.cyclic_pred(it);
  148.        u = POL[it];
  149.        ltouch   = DAG[u]->s.end();
  150.        ltangent = segment(ltouch,P);
  151.       }
  152.  
  153.  
  154.      node x = NEW_NODE(ltangent);
  155.      node y = NEW_NODE(rtangent);
  156.  
  157.      it = POL.cyclic_succ(DAG[u]->it);
  158.      
  159.      while (it != DAG[w]->it)
  160.      { list_item i = it;
  161.        it = POL.cyclic_succ(it);
  162.        DAG.new_edge(POL[i],x);
  163.        DAG.new_edge(POL[i],y);
  164.        POL.del(i);
  165.       }
  166.      
  167.      DAG[x]->it = POL.insert(x,it,before);
  168.      DAG[y]->it = POL.insert(y,it,before);
  169.  
  170.  
  171.    }
  172.  
  173.  
  174.  
  175.  
  176.   node v;
  177.  
  178.   forall(v,POL) L.append(DAG[v]->s.start());
  179.  
  180.   return polygon(L);
  181.  
  182. }
  183.  
  184.