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