home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / plane / _subdivi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.8 KB  |  152 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _subdivision.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/subdivision.h>
  17.  
  18. #include <LEDA/prio.h>
  19.  
  20.  
  21. declare2(priority_queue,edge,point)
  22. typedef priority_queue(edge,point) X_structure;
  23.  
  24.  
  25. static real x_sweep;
  26.  
  27. int compare(segment& s1,segment& s2)
  28. {
  29.   if (s1 == s2) return 0;
  30.  
  31.   real sl1 = s1.slope();
  32.   real sl2 = s2.slope();
  33.  
  34.   if (s1.start() == s2.start()) return compare(sl1,sl2);
  35.  
  36.   if (s1.end() == s2.end()) return compare(sl2,sl1);
  37.  
  38.   double y1 = sl1*x_sweep+s1.y_abs();
  39.   double y2 = sl2*x_sweep+s2.y_abs();
  40.  
  41.   return (y1 > y2) ? 1 : -1;
  42.  
  43. }
  44.  
  45. SubDivision::SubDivision(const graph& G) : planar_map(G)
  46. { 
  47.   edge e;
  48.   segment s;
  49.   point p;
  50.   strip sp;
  51.   int count = 0;
  52.  
  53.   // compute strips
  54.  
  55.   X_structure X;
  56.  
  57.   // initialize X-structure
  58.  
  59.   forall_edges(e,*this) 
  60.   { point p = point(inf(source(e)));
  61.     point q = point(inf(target(e)));
  62.  
  63.     if (p.xcoord() < q.xcoord()) 
  64.     { X.insert(e,p);
  65.       X.insert(e,q);
  66.      }
  67.    }
  68.  
  69.  
  70.  
  71.  
  72.   // sweep
  73.  
  74.   strip Y;
  75.  
  76.   x_sweep = -MAXDOUBLE;
  77.  
  78.   strips.insert(x_sweep, Y);    
  79.  
  80.   while( !X.empty() )
  81.   { point    p = X.inf(X.find_min());
  82.     list(edge) L,R;
  83.  
  84.     while ( !X.empty() )
  85.     { pq_item it = X.find_min();
  86.       point    q = X.inf(it);
  87.       edge     e = X.key(it);
  88.  
  89.       if (q != p) break;
  90.  
  91.       if (q == point(inf(source(e))))  // left  end
  92.           L.append(e);    
  93.       else                             // right end
  94.           R.append(e);    
  95.  
  96.       X.del_item(it);
  97.      }
  98.  
  99.  
  100.     // Insert new strip into version List
  101.  
  102.     x_sweep = p.xcoord();
  103.  
  104.     edge e;
  105.     forall(e,R) Y = Y.del(segment(point(inf(source(e))),point(inf(target(e)))));
  106.     forall(e,L) Y = Y.insert(segment(point(inf(source(e))),
  107.                                      point(inf(target(e)))), adj_face(e));
  108.  
  109.     L.clear();
  110.     R.clear();
  111.  
  112.     strips.insert(x_sweep, Y);    
  113.  
  114.    }
  115.  
  116.    strips.insert(MAXDOUBLE, Y);    
  117.  
  118.  
  119.    // compute outer face
  120.  
  121.    seq_item sit = strips.min();
  122.    sit = strips.succ(sit);
  123.  
  124.    outer_face = Y.inf(strips.inf(sit).min());
  125.  
  126. }
  127.  
  128.  
  129.  
  130. face SubDivision::locate_point(point p) const
  131. {
  132.   seq_item sit = strips.locate(p.xcoord()); 
  133.   strip Y = strips.inf(strips.pred(sit));
  134.   x_sweep = p.xcoord();
  135.   p_dic_item it = Y.locate(segment(p,0,1));
  136.   return (it == nil) ? outer_face : Y.inf(it);
  137.  }
  138.  
  139.  
  140. void SubDivision::print_stripes() const
  141. { seq_item it1;
  142.   p_dic_item it2;
  143.  
  144.   forall_seq_items(it1,strips)
  145.   { strip sp = strips.inf(it1);
  146.     forall_items(it2,sp) 
  147.       cout << sp.key(it2) << " f = " << int(sp.inf(it2)) << "\n";
  148.     newline;
  149.   }
  150.   newline;
  151.  }
  152.