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

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

数值算法/人工智能

开发平台：

MultiPlatform

_polygon.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _polygon.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/polygon.h>
  14. #include <LEDA/plane_alg.h>
  15. #include <LEDA/map.h>
  16. #include <math.h>
  19. //------------------------------------------------------------------------------
  20. // polygons
  21. //------------------------------------------------------------------------------
  24. ostream& operator<<(ostream& out, const polygon& p) 
  25. { p.vertices().print(out);
  26.   return out << endl;
  27.  } 
  29. istream& operator>>(istream& in,  polygon& p) 
  30. { list<point> L; 
  31.   L.read(in,'n'); 
  32.   p = polygon(L); 
  33.   return in;
  34. }
  37. double polygon::compute_area(const list<segment>& seg_list) const
  38. {
  39.   if (seg_list.length() < 3) return 0;
  41.   list_item it = seg_list.item(1);
  42.   point     p  = seg_list[it].source();
  44.   it = seg_list.succ(it);
  46.   double    A  = 0;
  48.   while (it)
  49.   { segment s = seg_list[it];
  50.     A += ::area(p,s.source(),s.target());
  51.     it = seg_list.succ(it);
  52.    }
  54.   return A;
  55. }
  58. static void check_simplicity(const list<segment>& seg_list)
  59. { GRAPH<point,segment> G;
  60.   SWEEP_SEGMENTS(seg_list,G);
  61.   node v;
  62.   forall_nodes(v,G)
  63.     if (G.degree(v) != 2)
  64.       error_handler(1,"polygon: polygon must be simple");
  65. }
  69. polygon::polygon(const list<point>& pl)
  70. { 
  71.   list<segment> seglist;
  73.   for(list_item it = pl.first(); it; it = pl.succ(it))
  74.     seglist.append(segment(pl[it],pl[pl.cyclic_succ(it)]));
  76.   if (compute_area(seglist) < 0)
  77.   { // reverse edge list
  78.     seglist.clear();
  79.     for(list_item it = pl.last(); it; it = pl.pred(it))
  80.       seglist.append(segment(pl[it],pl[pl.cyclic_pred(it)]));
  81.    }
  82.   check_simplicity(seglist);
  84.   PTR = new polygon_rep(seglist);
  85. }
  88. list<point> polygon::vertices() const
  89. { list<point> result;
  90.   segment s;
  91.   forall(s,ptr()->seg_list) result.append(s.start());
  92.   return result;
  93. }
  96. polygon polygon::translate(double alpha, double d) const
  97. { list<segment> L;
  98.   segment s;
  99.   forall(s,ptr()->seg_list) L.append(s.translate(alpha,d));
  100.   return polygon(L);
  101. }
  104. polygon polygon::translate(const vector& v) const
  105. { list<segment> L;
  106.   segment s;
  107.   forall(s,ptr()->seg_list) L.append(s.translate(v));
  108.   return polygon(L);
  109. }
  112. polygon polygon::rotate(const point& origin, double alpha) const
  113. { list<segment> L;
  114.   segment s;
  115.   forall(s,ptr()->seg_list) L.append(s.rotate(origin,alpha));
  116.   return polygon(L);
  117. }
  120. polygon polygon::rotate(double alpha) const
  121. { return rotate(point(0,0),alpha); }
  124. bool polygon::inside(const point& p) const
  125. {
  126.   list<segment>& seglist = ptr()->seg_list;
  128.   int count = 0;
  130.   double px = p.xcoord();
  132.   list_item it0 = seglist.first();
  133.   list_item it1 = seglist.first();
  135.   double x0 = seglist[it0].xcoord2();
  136.   double x1 = seglist[it1].xcoord2();
  138.   list_item it;
  140.   forall_items(it,seglist)
  141.   { segment s = seglist[it];
  142.     if (s.xcoord2() < x0) 
  143.     { it0 = it;
  144.       x0 = s.xcoord2();
  145.      }
  146.     if (s.xcoord2() > x1) 
  147.     { it1 = it1;
  148.       x1 = s.xcoord2();
  149.      }
  150.    }
  152.   if (px <= x0 || x1 <= px) return false;
  154.   while (seglist[it0].xcoord2() <= px) it0 = seglist.cyclic_succ(it0);
  156.   it = it0;
  157.   do
  158.   { while (seglist[it].xcoord2() >= px) it = seglist.cyclic_succ(it);
  159.     if (orientation(seglist[it],p) > 0) count++;
  160.     while (seglist[it].xcoord2() <= px) it = seglist.cyclic_succ(it);
  161.     if (orientation(seglist[it],p) < 0) count++;
  162.   } while (it != it0);
  164.   return count % 2;
  166. }
  170. bool polygon::outside(const point& p) const { return !inside(p); }
  173. list<point> polygon::intersection(const segment& s) const
  174. { list<point> result;
  175.   segment t;
  176.   point p;
  178.   forall(t,ptr()->seg_list) 
  179.     if (s.intersection(t,p))
  180.      if (result.empty()) result.append(p);
  181.      else if (p != result.tail() ) result.append(p);
  183.   return result;
  184. }
  187. list<point> polygon::intersection(const line& l) const
  188. { list<point> result;
  189.   segment t;
  190.   point p;
  192.   forall(t,ptr()->seg_list) 
  193.     if (l.intersection(t,p))
  194.      if (result.empty()) result.append(p);
  195.      else if (p != result.tail() ) result.append(p);
  197.   return result;
  198. }
  201. // intersection or union with polygon
  203. static bool test_edge(GRAPH<point,segment>& G, edge i1, int mode)
  205. { node v  = G.target(i1);
  206.   edge i2 = G.cyclic_in_succ(i1);
  208.   if (i1 == i2) return false;
  210.   edge o1 = G.first_adj_edge(v);
  211.   edge o2 = G.last_adj_edge(v);
  213.   point p1 = G[o1].target();
  214.   point p2 = G[o2].target();
  216.   segment si1 = G[i1];
  217.   segment si2 = G[i2];
  219.   if (mode == 0) // intersection
  220.   { if (orientation(si1,si2.source()) > 0)
  221.       return orientation(si1,p1) > 0 && orientation(si2,p1) < 0 && 
  222.              orientation(si1,p2) > 0 && orientation(si2,p2) < 0;
  223.    else
  224.       return (orientation(si1,p1) > 0 || orientation(si2,p1) < 0) && 
  225.              (orientation(si1,p2) > 0 || orientation(si2,p2) < 0);
  226.   }
  227.   else // union
  228.   { if (orientation(si1,si2.source()) < 0)
  229.       return orientation(si1,p1) < 0 && orientation(si2,p1) > 0 && 
  230.              orientation(si1,p2) < 0 && orientation(si2,p2) > 0;
  231.    else
  232.       return (orientation(si1,p1) < 0 || orientation(si2,p1) > 0) && 
  233.              (orientation(si1,p2) < 0 || orientation(si2,p2) > 0);
  234.    }
  235. }
  239. static edge next_edge(GRAPH<point,segment>& G, edge i1, int dir)
  240. { 
  241.   // if dir = +1 turn left
  242.   // if dir = -1 turn right
  244.   node v = G.target(i1);
  246.   edge o1 = G.first_adj_edge(v);
  247.   edge o2 = G.last_adj_edge(v);
  249.   segment si1 = G[i1];
  250.   segment so1 = G[o1];
  251.   segment so2 = G[o2];
  253.   if (o2 == nil) return o1;
  255.   int orient1 = orientation(si1,so1.target());
  256.   int orient2 = orientation(si1,so2.target());
  258.   if (orient1 == orient2)
  259.      return (orientation(so1,so2.target()) == dir) ? o2 : o1;
  260.   else
  261.      return (orient1 - orient2 == dir) ? o1 : o2;
  263. }
  267. list_polygon_ polygon::intersection(const polygon& P) const
  268. {
  269.   list<polygon> result;
  270.   list<segment> seg_list;
  271.   GRAPH<point,segment> G;
  273.   segment s;
  274.   forall(s,ptr()->seg_list) seg_list.append(s);
  275.   forall(s,P.ptr()->seg_list) seg_list.append(s);
  277.   SWEEP_SEGMENTS(seg_list,G);
  279.   bool borders_intersect = false;
  281.   node v;
  282.   forall_nodes(v,G) 
  283.     if (degree(v) > 2) 
  284.     { borders_intersect = true;
  285.       break;
  286.      }
  288.   if ( ! borders_intersect )
  289.   { // no intersections between edges of (*this) and P
  290.     // check for inclusion
  292.     segment s1 = ptr()->seg_list.head();
  293.     segment s2 = P.ptr()->seg_list.head();
  295.     if ( P.inside(s1.start()) ) result.append(*this);
  296.     if ( inside(s2.start()) ) result.append(P);                   
  298.     return result;
  300.    }
  302.   edge_array<bool> marked(G,false);
  304.   edge e;
  305.   forall_edges(e,G) 
  306.     if ( ! marked[e] && test_edge(G,e,0) )
  307.     { list<segment> pol;
  308.       edge start = e;
  309.       do { node v = source(e);
  310.            node w = target(e);
  311.            pol.append(segment(G[v],G[w]));
  312.            marked[e] = true;
  313.            e = next_edge(G,e,+1);
  314.           } while (e != start);
  315.       result.append(polygon(pol));
  316.      }
  318.  return result;
  320. }
  323. list_polygon_ polygon::unite(const polygon& P) const
  324. {
  325.   list<polygon> result;
  326.   list<segment> seg_list;
  327.   GRAPH<point,segment> G;
  329.   segment s;
  330.   forall(s,ptr()->seg_list) seg_list.append(s);
  331.   forall(s,P.ptr()->seg_list) seg_list.append(s);
  333.   SWEEP_SEGMENTS(seg_list,G);
  335.   if (G.number_of_nodes() == size() + P.size())
  336.   { // no intersections between edges of (*this) and P
  337.     // check for inclusion
  339.     segment s1 = ptr()->seg_list.head();
  340.     segment s2 = P.ptr()->seg_list.head();
  342.     if ( ! P.inside(s1.start())) result.append(*this);
  343.     if ( ! inside(s2.start())) result.append(P);                   
  345.     return result;
  347.    }
  349.   edge_array<bool> marked(G,false);
  351.   edge e;
  352.   forall_edges(e,G) 
  353.     if ( ! marked[e] && test_edge(G,e,1) )
  354.     { list<segment> pol;
  355.       edge start = e;
  356.       do { node v = source(e);
  357.            node w = target(e);
  358.            pol.append(segment(G[v],G[w]));
  359.            marked[e] = true;
  360.            e = next_edge(G,e,-1);
  361.           } while (e != start);
  362.       result.append(polygon(pol));
  363.      }
  365.  return result;
  367. }