开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_sweep_old.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：13k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_sweep_old.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _sweep_old.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. //------------------------------------------------------------------------------
  15. //
  16. // SWEEP_SEGMENTS
  17. //
  18. // a plane sweep algorithm for computing line segment intersections
  19. //
  20. // SWEEP_SEGMENTS(list<segment>& L1, list<segment>& L2, GRAPH<point,int> G);
  21. //
  22. // computes the planar subdivision created by the (directed) straight
  23. // line segments of L1 and L2
  24. // 
  25. // G = (V,E) with
  26. //
  27. // 1. each node v in V contains a point of intersectoin between two segments
  28. //    (from L1 or L2)
  29. //
  30. // 2. each edge e = (v,w) corresponds to a
  31. //
  32. //
  33. //------------------------------------------------------------------------------
  36. #include <LEDA/sweep_segments.h>
  37. #include <LEDA/sortseq.h>
  38. #include <LEDA/p_queue.h>
  39. #include <math.h>
  42. #define EPS  0.00001
  43. #define EPS2 0.0000000001
  45. class S_POINT;
  46. class S_SEGMENT;
  47. typedef S_POINT* S_point;
  48. typedef S_SEGMENT* S_segment;
  50. enum S_point_type {Cross=0,Rightend=1,Leftend=2}; 
  52. class S_POINT
  53. {
  54.   friend class S_SEGMENT;
  56.   S_segment seg;
  57.   int     kind;
  58.   double  x;
  59.   double  y;
  61.   public:
  63.   S_POINT(double a,double b)  
  64.   { 
  65.     x=a; y=b; seg=0; kind=Cross;
  66.    }
  70.   S_POINT(point p)         
  71.   { 
  72.     x=p.xcoord();y=p.ycoord();seg=0;kind=Cross;
  73.    }
  76.   LEDA_MEMORY(S_POINT);
  78.   friend double    get_x(S_point);
  79.   friend double    get_y(S_point);
  80.   friend int       get_kind(S_point);
  81.   friend S_segment get_seg(S_point);
  83.   friend bool intersection(S_segment, S_segment, S_point&);
  84. };
  86. inline double    get_x(S_point p)    { return p->x; }
  87. inline double    get_y(S_point p)    { return p->y; }
  88. inline int       get_kind(S_point p) { return p->kind; }
  89. inline S_segment get_seg(S_point p)  { return p->seg; }   
  92. #if defined(__GNUC__)
  93. inline
  94. #else
  95. static 
  96. #endif
  97. int compare(const S_point& p1, const S_point& p2)
  98. { if (p1==p2) return 0;
  100.   double diffx = get_x(p1) - get_x(p2);
  101.   if (diffx >  EPS2 ) return  1;
  102.   if (diffx < -EPS2 ) return -1;
  104.   int    diffk = get_kind(p1)-get_kind(p2);
  105.   if (diffk != 0) return diffk;
  107.   double diffy = get_y(p1) - get_y(p2);
  108.   if (diffy >  EPS2 ) return  1;
  109.   if (diffy < -EPS2 ) return -1;
  111.   return 0;
  113. }
  116. class S_SEGMENT
  117. {
  118.   S_point startpoint;
  119.   S_point endpoint;
  120.   double  slope;
  121.   double  yshift;
  122.   node  left_node;
  123.   int   orient;
  124.   int   color;
  125.   int   name;
  128.   public:
  130.   S_SEGMENT(S_point, S_point,int,int);     
  132.  ~S_SEGMENT() { delete startpoint; delete endpoint; }     
  134.   LEDA_MEMORY(S_SEGMENT);
  136.   friend S_point get_startpoint(S_segment);
  137.   friend S_point get_endpoint(S_segment);
  138.   friend double get_slope(S_segment);
  139.   friend double get_yshift(S_segment);
  140.   friend int  get_orient(S_segment);
  141.   friend int  get_color(S_segment);
  142.   friend int  get_name(S_segment);
  143.   friend node get_left_node(S_segment);
  144.   friend void set_left_node(S_segment, node);
  146.   friend bool intersection(S_segment, S_segment, S_point&);
  147. };
  150. inline S_point get_startpoint(S_segment seg)     { return seg->startpoint; }
  151. inline S_point get_endpoint(S_segment seg)       { return seg->endpoint; }
  152. inline double get_slope(S_segment seg)           { return seg->slope; }
  153. inline double get_yshift(S_segment seg)          { return seg->yshift; }
  154. inline int  get_orient(S_segment seg)            { return seg->orient; }
  155. inline int  get_color(S_segment seg)             { return seg->color; }
  156. inline int  get_name(S_segment seg)              { return seg->name; }
  157. inline node get_left_node(S_segment seg)         { return seg->left_node; }
  158. inline void set_left_node(S_segment seg, node v) { seg->left_node = v; }
  162. S_SEGMENT::S_SEGMENT(S_point p1,S_point p2,int c, int n)    
  163.   {
  164.     left_node  = nil;
  165.     color      = c;
  166.     name       = n;
  168.     if (compare(p1,p2) < 0)
  169.      { startpoint = p1; 
  170.        endpoint = p2; 
  171.        orient = 0;
  172.       }
  173.     else
  174.      { startpoint = p2; 
  175.        endpoint = p1; 
  176.        orient = 1;
  177.       }
  179.     startpoint->kind = Leftend; 
  180.     endpoint->kind = Rightend; 
  181.     startpoint->seg = this; 
  182.     endpoint->seg = this;
  184.     if (endpoint->x != startpoint->x)
  185.     {
  186.       slope = (endpoint->y - startpoint->y)/(endpoint->x - startpoint->x);
  187.       yshift = startpoint->y - slope * startpoint->x;
  189.       startpoint->x -= EPS;
  190.       startpoint->y -= EPS * slope;
  191.       endpoint->x += EPS;
  192.       endpoint->y += EPS * slope;
  193.     }
  194.     else //vertical segment
  195.     { startpoint->y -= EPS;
  196.       endpoint->y   += EPS;
  197.      }
  198.   }
  201. static double x_sweep;
  202. static double y_sweep;
  205. #if defined(__GNUC__)
  206. inline
  207. #else
  208. static 
  209. #endif
  210. int compare(const S_segment& s1, const S_segment& s2)
  211. {
  212.   double y1 = get_slope(s1)*x_sweep+get_yshift(s1);
  213.   double y2 = get_slope(s2)*x_sweep+get_yshift(s2);
  215.   double diff = y1-y2;
  216.   if (diff >  EPS2 ) return  1;
  217.   if (diff < -EPS2 ) return -1;
  219.   if (get_slope(s1) == get_slope(s2)) 
  220.         return compare(get_x(get_startpoint(s1)), get_x(get_startpoint(s2)));
  222.   if (y1 <= y_sweep+EPS2)
  223.         return compare(get_slope(s1),get_slope(s2));
  224.   else
  225.         return compare(get_slope(s2),get_slope(s1));
  227. }
  230. void Print(S_segment& x) 
  231. { S_point s = get_startpoint(x);
  232.   S_point e = get_endpoint(x);
  233.   cout << 
  234.     string("[(%f,%f)----(%f,%f)]",get_x(s),get_y(s), get_x(e),get_y(e));
  235. }
  238. static p_queue<S_point,seq_item>  X_structure;
  240. static sortseq<S_segment,pq_item> Y_structure;
  243. bool intersection(S_segment seg1,S_segment seg2, S_point& inter)
  244. {
  245.   if (seg1->slope == seg2->slope)
  246.     return false;
  247.   else
  248.   { 
  249.     double cx = (seg2->yshift - seg1->yshift) / (seg1->slope - seg2->slope);
  250.  
  251.     if (cx <= x_sweep) return false;
  253.     if (seg1->startpoint->x > cx || seg2->startpoint->x > cx ||
  254.         seg1->endpoint->x < cx || seg2->endpoint->x < cx ) return false;
  256.     inter = new S_POINT(cx,seg1->slope * cx + seg1->yshift);
  258.     return true;
  259.   }
  260. }
  263. static pq_item Xinsert(seq_item i, S_point p) 
  264. { 
  265.   return X_structure.insert(p,i);
  266. }
  268. static S_point Xdelete(pq_item i) 
  269. {
  270.   S_point p = X_structure.prio(i);
  271.   X_structure.del_item(i);
  272.   return p;
  273. }
  276. static node New_Node(GRAPH<point,int>& G,double x, double y )
  277. { return G.new_node(point(x,y)); }
  279. static void New_Edge(GRAPH<point,int>& G,node v, node w, S_segment l )
  280. { if (get_orient(l)==0)
  281.        G.new_edge(v,w,get_color(l));
  282.   else G.new_edge(w,v,get_color(l));
  283. }
  286. void handle_vertical_segment(GRAPH<point,int>& SUB, S_segment l)
  287. { 
  288.   S_point p = new S_POINT(get_x(get_startpoint(l)),get_y(get_startpoint(l)));
  289.   S_point q = new S_POINT(get_x(get_endpoint(l)),get_y(get_endpoint(l)));
  291.   S_point r = new S_POINT(get_x(p)+1,get_y(p));
  292.   S_point s = new S_POINT(get_x(q)+1,get_y(q));
  294.   S_segment bot = new S_SEGMENT(p,r,0,0);
  295.   S_segment top = new S_SEGMENT(q,s,0,0);
  297.   seq_item bot_it = Y_structure.insert(bot,nil);
  298.   seq_item top_it = Y_structure.insert(top,nil);
  299.   seq_item sit;
  301.   node u,v,w;
  302.   S_segment seg;
  303.   
  305.   for(sit=Y_structure.succ(bot_it); sit != top_it; sit=Y_structure.succ(sit))
  306.   { seg = Y_structure.key(sit);
  308.     double cross_y = (get_slope(seg) * get_x(p) + get_yshift(seg));
  310.     v = get_left_node(seg);
  311.     if (v==nil)
  312.     { w = New_Node(SUB,get_x(p),cross_y);
  313.       set_left_node(seg,w);
  314.      }
  315.     else
  316.     { double vx = SUB[v].xcoord();
  317.       if ( vx < get_x(p)-EPS2) 
  318.       { w = New_Node(SUB,get_x(p),cross_y);
  319.         New_Edge(SUB,v,w,seg);
  320.         set_left_node(seg,w);
  321.        }
  322.       else w = v;
  323.      }
  325.     u = get_left_node(l);
  326.     if (u!=nil && u!=w) New_Edge(SUB,u,w,l);
  327.     set_left_node(l,w);
  329.    }
  330.   
  331.   delete l;
  332.   delete top;
  333.   delete bot;
  334.     
  335.   Y_structure.del_item(bot_it);
  336.   Y_structure.del_item(top_it);
  338.  }
  341. void SWEEP_SEGMENTS(const list<segment>& S, list<point>& P)
  342. { GRAPH<point,int> G;
  343.   list<segment> S0;
  345.   SWEEP_SEGMENTS(S,S0,G);
  347.   node v;
  348.   forall_nodes(v,G) P.append(G[v]);
  350. }
  352. void SWEEP_SEGMENTS(const list<segment>& L1, 
  353.                     const list<segment>& L2, GRAPH<point,int>& SUB)
  354. {
  355.   S_point    p,inter;
  356.   S_segment  seg, l,lsit,lpred,lsucc,lpredpred;
  357.   pq_item  pqit,pxmin;
  358.   seq_item sitmin,sit,sitpred,sitsucc,sitpredpred;
  361.   int count=1;
  362.  
  363.   //initialization of the X-structure
  365.   segment s;
  367.   forall(s,L1) 
  368.    { S_point p = new S_POINT(s.start());
  369.      S_point q = new S_POINT(s.end());
  370.      seg = new S_SEGMENT(p,q,0,count++);
  371.      Xinsert(nil,get_startpoint(seg));
  372.    }
  374.   count = -1;
  376.   forall(s,L2) 
  377.    { S_point p = new S_POINT(s.start());
  378.      S_point q = new S_POINT(s.end());
  379.      seg = new S_SEGMENT(p,q,1,count--);
  380.      Xinsert(nil,get_startpoint(seg));
  381.    }
  384.   count = 0;
  386.   x_sweep = -MAXINT;
  387.   y_sweep = -MAXINT;
  390.   while(!X_structure.empty())
  391.   {
  392.     pxmin = X_structure.find_min();
  393.     p = X_structure.prio(pxmin);
  395.     sitmin = X_structure.inf(pxmin);
  397.     Xdelete(pxmin);
  401.     if (sitmin == nil) //left endpoint
  402.     { 
  404.       l = get_seg(p); 
  406.       x_sweep = get_x(p);
  407.       y_sweep = get_y(p);
  410.       if (get_x(p) == get_x(get_endpoint(l)))
  411.         handle_vertical_segment(SUB,l);
  412.       else
  413.       {
  415. /*
  416.       sit = Y_structure.lookup(l);
  417.       if (sit!=nil)  
  418.            error_handler(1,"plane sweep: sorry, overlapping segments");
  419. */
  422.       sit = Y_structure.insert(l,nil);
  424.       Xinsert(sit,get_endpoint(l));
  426.       sitpred = Y_structure.pred(sit);
  427.       sitsucc = Y_structure.succ(sit);
  429.       if (sitpred != nil) 
  430.       { if ((pqit = Y_structure.inf(sitpred)) != nil)
  431.           delete Xdelete(pqit);
  433.         lpred = Y_structure.key(sitpred);
  435.         Y_structure.change_inf(sitpred,nil);
  437.         if (intersection(lpred,l,inter))
  438.             Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  439.       }
  442.       if (sitsucc != nil)
  443.       { lsucc = Y_structure.key(sitsucc);
  444.         if (intersection(lsucc,l,inter))
  445.            Y_structure.change_inf(sit,Xinsert(sit,inter));
  446.       }
  447.      } /* else if vertical */
  449.     }
  450.     else if (get_kind(p) == Rightend)
  451.          //right endpoint
  452.          { 
  453.            x_sweep = get_x(p);
  454.            y_sweep = get_y(p);
  456.            sit = sitmin;
  458.            sitpred = Y_structure.pred(sit);
  459.            sitsucc = Y_structure.succ(sit);
  461.            S_segment seg = Y_structure.key(sit);
  463.            Y_structure.del_item(sit);
  465.            delete seg;
  467.            if((sitpred != nil)&&(sitsucc != nil))
  468.            {
  469.              lpred = Y_structure.key(sitpred);
  470.              lsucc = Y_structure.key(sitsucc);
  471.              if (intersection(lsucc,lpred,inter))
  472.                 Y_structure.change_inf(sitpred,Xinsert(sitpred,inter));
  473.            }
  474.          }
  475.          else // point of intersection
  476.          { 
  477.            node w = New_Node(SUB,get_x(p),get_y(p));
  479.            count++;
  481.            /* Let L = list of all lines intersecting in p 
  482.  
  483.               we compute sit     = L.head();
  484.               and        sitpred = L.tail();
  486.               by scanning the Y_structure in both directions 
  487.               starting at sitmin;
  489.            */
  491.            /* search for sitpred upwards from sitmin: */
  493.            Y_structure.change_inf(sitmin,nil);
  495.            sitpred = Y_structure.succ(sitmin);
  498.            while ((pqit=Y_structure.inf(sitpred)) != nil)
  499.            { S_point q = X_structure.prio(pqit);
  500.              if (compare(p,q) != 0) break; 
  501.              X_structure.del_item(pqit);
  502.              Y_structure.change_inf(sitpred,nil);
  503.              sitpred = Y_structure.succ(sitpred);
  504.             }
  507.            /* search for sit downwards from sitmin: */
  509.            sit = sitmin;
  511.            seq_item sit1;
  512.            
  513.            while ((sit1=Y_structure.pred(sit)) != nil)
  514.            { pqit = Y_structure.inf(sit1);
  515.              if (pqit == nil) break;
  516.              S_point q = X_structure.prio(pqit);
  517.              if (compare(p,q) != 0) break; 
  518.              X_structure.del_item(pqit);
  519.              Y_structure.change_inf(sit1,nil);
  520.              sit = sit1;
  521.             }
  525.            // insert edges to p for all S_segments in sit, ..., sitpred into SUB
  526.            // and set left node to w 
  528.            lsit = Y_structure.key(sitpred);
  530.            node v = get_left_node(lsit);
  531.            if (v!=nil) New_Edge(SUB,v,w,lsit);
  532.            set_left_node(lsit,w);
  534.            for(sit1=sit; sit1!=sitpred; sit1 = Y_structure.succ(sit1))
  535.            { lsit = Y_structure.key(sit1);
  537.              v = get_left_node(lsit);
  538.              if (v!=nil) New_Edge(SUB,v,w,lsit);
  539.              set_left_node(lsit,w);
  540.             }
  542.            lsit = Y_structure.key(sit);
  543.            lpred=Y_structure.key(sitpred);
  544.            sitpredpred = Y_structure.pred(sit);
  545.            sitsucc=Y_structure.succ(sitpred);
  548.            if (sitpredpred != nil)
  549.             { 
  550.               lpredpred=Y_structure.key(sitpredpred);
  552.               if ((pqit = Y_structure.inf(sitpredpred)) != nil)
  553.                 delete Xdelete(pqit);
  555.               Y_structure.change_inf(sitpredpred,nil);
  558.               if (intersection(lpred,lpredpred,inter))
  559.                 Y_structure.change_inf(sitpredpred,
  560.                                        Xinsert(sitpredpred,inter));
  561.              }
  564.            if (sitsucc != nil)
  565.             {
  566.               lsucc=Y_structure.key(sitsucc);
  568.               if ((pqit = Y_structure.inf(sitpred)) != nil)
  569.                 delete Xdelete(pqit);
  570.                  
  571.               Y_structure.change_inf(sitpred,nil);
  573.               if (intersection(lsucc,lsit,inter))
  574.                   Y_structure.change_inf(sit,Xinsert(sit,inter));
  575.              }
  578. // reverse the subsequence sit, ... ,sitpred  in the Y_structure
  580.            x_sweep = get_x(p);
  581.            y_sweep = get_y(p);
  583.            Y_structure.reverse_items(sit,sitpred);
  585.           delete p;
  587.          } // intersection
  589.   }
  591.   X_structure.clear();
  593. }