home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / plane / _polygon.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-09  |  8.4 KB  |  406 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _polygon.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 <math.h>
  18.  
  19. /*
  20. #ifndef __TURBOC__
  21. #include <LEDA/plane_alg.h>
  22. declare(edge_array,bool)
  23. #endif
  24. */
  25.  
  26.  
  27. //------------------------------------------------------------------------------
  28. // polygons
  29. //------------------------------------------------------------------------------
  30.  
  31.  
  32. polygon_rep::polygon_rep(list(segment) L) 
  33. { 
  34.   seg_list = L;
  35.   count = 1; 
  36.  }
  37.  
  38. polygon_rep::polygon_rep()         { count = 1; }
  39.  
  40. polygon::polygon()                 { ptr = new polygon_rep; }
  41. polygon::polygon(int)              { ptr = new polygon_rep; }
  42. polygon::polygon(polygon& P)       { ptr = P.ptr; ptr->count++; }
  43. polygon::polygon(ent x)            { ptr=(polygon_rep*)x; ptr->count++; }
  44. void polygon::clear()              { if (--(ptr->count)==0) delete ptr; }
  45.  
  46.  
  47. ostream& operator<<(ostream& out, const polygon& p) 
  48. { p.vertices().print();
  49.   return out;
  50.  } 
  51.  
  52. istream& operator>>(istream& in,  polygon& p) 
  53. { list(point) L; 
  54.   L.read(); 
  55.   p = polygon(L); 
  56.   return in;
  57. }
  58.  
  59.  
  60. void polygon_check(list(segment)&);
  61.  
  62. polygon::polygon(list(point)& pl, bool check)
  63. { ptr = new polygon_rep;
  64.  
  65.   list_item it,it1;
  66.  
  67.   forall_list_items(it,pl)
  68.   { it1 = pl.cyclic_succ(it);
  69.     ptr->seg_list.append(segment(pl[it],pl[it1]));
  70.    }
  71.  
  72.   if (check) polygon_check(ptr->seg_list);
  73. }
  74.  
  75. list(point) polygon::vertices() const
  76. { list(point) result;
  77.   segment s;
  78.   forall(s,ptr->seg_list) result.append(s.start());
  79.   return result;
  80. }
  81.  
  82.  
  83.  
  84.  
  85. void polygon_check(list(segment)& seg_list)
  86. {  if (seg_list.length() < 3) 
  87.      error_handler(1,"polygon: must be simple");
  88.  
  89. /*
  90. #ifndef __TURBOC__
  91.    list(point) L;
  92.    SWEEP_SEGMENTS(seg_list,L);
  93.  
  94.   if (L.length() != seg_list.length())
  95.    error_handler(1,"polygon: must be simple");
  96. #endif
  97. */
  98.  
  99.   list_item it;
  100.  
  101.   double angle = 0;
  102.  
  103.   forall_list_items(it,seg_list)
  104.   { list_item succ = seg_list.cyclic_succ(it);
  105.     segment s1 = seg_list[it];
  106.     segment s2 = seg_list[succ];
  107.     angle += s1.angle(s2);
  108.    }
  109.  
  110.   if (angle > 0)
  111.    error_handler(1,"polygon: point list must be clockwise oriented.");
  112. }
  113.  
  114. polygon polygon::translate(double alpha, double d)
  115. { list(point) L;
  116.   segment s;
  117.   forall(s,ptr->seg_list) L.append(s.start().translate(alpha,d));
  118.   return polygon(L,false);
  119. }
  120.  
  121. polygon polygon::translate(const vector& v)
  122. { list(point) L;
  123.   segment s;
  124.   forall(s,ptr->seg_list) L.append(s.start().translate(v));
  125.   return polygon(L,false);
  126. }
  127.  
  128. polygon polygon::rotate(point origin, double alpha)
  129. { list(point) L;
  130.   segment s;
  131.   forall(s,ptr->seg_list) L.append(s.start().rotate(origin,alpha));
  132.   return polygon(L,false);
  133. }
  134.  
  135. polygon polygon::rotate(double alpha)
  136. { return rotate(point(0,0),alpha);
  137.  }
  138.  
  139.  
  140. /*
  141.  
  142. bool polygon::inside(point p)
  143. {
  144.   line l(p,M_PI_2);  // vertical line through p
  145.  
  146.   int count = 0;
  147.  
  148.   segment s;
  149.   forall(s,ptr->seg_list)
  150.   { point q;
  151.     if (!l.intersection(s,q)) continue;
  152.     if (q.ycoord() < p.ycoord()) continue;
  153.     if (q == s.start())  continue;
  154.     if (q == s.end())  continue;
  155.     count++ ;
  156.    }
  157.  
  158.   list(point) plist = vertices();
  159.  
  160.   list_item i = plist.first();;
  161.  
  162.   forall_items(i,plist)
  163.   { 
  164.     point q = plist[i];
  165.  
  166.     if (q==p) return true;
  167.  
  168.     if (q.xcoord() == p.xcoord() && q.ycoord() > p.ycoord())
  169.     { list_item i0 = plist.cyclic_pred(i);
  170.       list_item i1 = plist.cyclic_succ(i);
  171.       point q0 = plist[i0];
  172.       point q1 = plist[i1];
  173.  
  174.       if (q0.xcoord() < p.xcoord() && q1.xcoord() > p.xcoord()) count++;
  175.       if (q0.xcoord() > p.xcoord() && q1.xcoord() < p.xcoord()) count++;
  176.  
  177.      }
  178.  
  179.    }
  180.  
  181.    return count%2;
  182.  
  183. }
  184.  
  185. */
  186.  
  187.  
  188.  
  189. bool polygon::inside( point p)
  190. {
  191.   line l(p,M_PI_2);  // vertical line through p
  192.  
  193.   int count = 0;
  194.  
  195.   segment s;
  196.   forall(s,ptr->seg_list)
  197.   { point q;
  198.     if (!l.intersection(s,q)) continue;
  199.     if (q.ycoord() < p.ycoord()) continue;
  200.     if (q == s.start())  continue;
  201.     if (q == s.end())  continue;
  202.     count++ ;
  203.    }
  204.  
  205.   list(point) plist = vertices();
  206.  
  207.   list_item i0 = plist.first();
  208.  
  209.   while (plist[i0].xcoord() == p.xcoord())  i0 = plist.cyclic_pred(i0);
  210.  
  211.   list_item i = plist.cyclic_succ(i0);
  212.  
  213.   for(;;)
  214.   { 
  215.     while ( i != i0 && (plist[i].xcoord() != p.xcoord() || 
  216.                         plist[i].ycoord() < p.ycoord()    )  )
  217.        i = plist.cyclic_succ(i);
  218.  
  219.     if (i==i0) break;
  220.  
  221.     point q  = plist[i];
  222.     point q0 = plist[plist.cyclic_pred(i)];
  223.  
  224.     while ((plist[i].xcoord()==p.xcoord()) && (plist[i].ycoord() >= p.ycoord()))
  225.     { if (plist[i]==p) return true;
  226.       i = plist.cyclic_succ(i);
  227.      }
  228.  
  229.     point q1 = plist[i];
  230.  
  231.      if (q0.xcoord() < p.xcoord() && q1.xcoord() > p.xcoord()) count++;
  232.       if (q0.xcoord() > p.xcoord() && q1.xcoord() < p.xcoord()) count++;
  233.  
  234.    }
  235.  
  236.    return count%2;
  237.  
  238. }
  239.  
  240. bool polygon::outside(point p) { return !inside(p); }
  241.  
  242.  
  243. list(point) polygon::intersection(segment s)
  244. { list(point) result;
  245.   segment t;
  246.   point p;
  247.  
  248.   forall(t,ptr->seg_list) 
  249.     if (s.intersection(t,p))
  250.      if (result.empty()) result.append(p);
  251.      else if (p != result.tail() ) result.append(p);
  252.  
  253.   return result;
  254. }
  255.  
  256.  
  257. list(point) polygon::intersection(line l)
  258. { list(point) result;
  259.   segment t;
  260.   point p;
  261.  
  262.   forall(t,ptr->seg_list) 
  263.     if (l.intersection(t,p))
  264.      if (result.empty()) result.append(p);
  265.      else if (p != result.tail() ) result.append(p);
  266.  
  267.   return result;
  268. }
  269.  
  270.  
  271. // intersection with polygon
  272. /*
  273. #ifndef __TURBOC__
  274.  
  275. static bool polygon_test_edge(GRAPH(point,int)& G,edge& i1)
  276. { node v = G.target(i1);
  277.  
  278.   edge e,i2=nil,o1=nil,o2=nil;
  279.  
  280.   forall_adj_edges(e,v)
  281.     if (e != i1)
  282.     { if (v==target(e)) i2 = e;
  283.       else if (G[e]== G[i1]) o1 = e;
  284.            else o2 = e;
  285.      }
  286.  
  287.   if (i2==nil) return false;
  288.  
  289.   segment si1(G[source(i1)],G[v]);
  290.   segment si2(G[v],G[source(i2)]);
  291.   segment so2(G[v],G[target(o2)]);
  292.  
  293.   double alpha = si1.angle(si2);
  294.   double beta  = si1.angle(so2);
  295.  
  296.   return (alpha > beta);
  297.  
  298. }
  299.  
  300.  
  301.  
  302. static edge polygon_switch_edge(GRAPH(point,int)& G,edge i1)
  303. { node v = G.target(i1);
  304.  
  305.   edge e,i2=nil,o1=nil,o2=nil;
  306.  
  307.   forall_adj_edges(e,v)
  308.     if (e != i1)
  309.     { if (v==target(e)) i2 = e;
  310.       else if (G[e]== G[i1]) o1 = e;
  311.            else o2 = e;
  312.      }
  313.  
  314.   if (i2==nil) return  o1;
  315.  
  316.   segment si1(G[source(i1)],G[v]);
  317.   segment si2(G[v],G[source(i2)]);
  318.   segment so1(G[v],G[target(o1)]);
  319.   segment so2(G[v],G[target(o2)]);
  320.  
  321.   double alpha = si1.angle(si2);
  322.   double beta  = si1.angle(so2);
  323.   double gamma = si1.angle(so1);
  324.  
  325.   if (alpha < beta) cout << "error: alpa < beta!!\n";
  326.  
  327.   if (gamma >= beta) return o2;
  328.   else return o1;
  329.  
  330. }
  331.  
  332. #endif
  333. */
  334.  
  335. list(polygon) polygon::intersection(polygon P)
  336. {
  337.  
  338.   list(polygon) result;
  339.  
  340. /*
  341. #ifndef __TURBOC__
  342.  
  343.   GRAPH(point,int) SUB;
  344.  
  345.   SWEEP_SEGMENTS(segments(),P.segments(),SUB);
  346.  
  347.   int N = SUB.number_of_nodes();
  348.  
  349.   if (N < size() + P.size())
  350.    error_handler(1,"polygon: sorry, internal error in intersection");
  351.  
  352.   if (N == size() + P.size())
  353.   { // no intersections between edges of (*this) and P
  354.     // check for inclusion
  355.  
  356.     segment s1 = ptr->seg_list.head();
  357.     segment s2 = P.ptr->seg_list.head();
  358.     point   p1 = s1.start();
  359.     point   p2 = s2.start();
  360.  
  361.     if (P.inside(p1))                     // (*this) is conained in P
  362.       result.append(*this);
  363.     else
  364.       if (inside(p2))                     // P is conained in (*this)
  365.         result.append(P);                   
  366.  
  367.  
  368.     return result;
  369.  
  370.    }
  371.  
  372.   SUB.make_undirected();
  373.  
  374.   edge e;
  375.  
  376.   list(point) PL;
  377.  
  378.   edge_array(bool) marked(SUB,false);
  379.  
  380.   forall_edges(e,SUB) 
  381.   { edge f;
  382.     if (!marked[e]  && SUB.outdeg(target(e))>1) 
  383.       if (polygon_test_edge(SUB,e))
  384.       { // new polygon found
  385.        marked[e] = true;
  386.        PL.append(SUB[source(e)]);
  387.        f = polygon_switch_edge(SUB,e);
  388.        while (f!=e)
  389.        { marked[f] = true;
  390.          PL.append(SUB[source(f)]);
  391.          f = polygon_switch_edge(SUB,f);
  392.         }
  393.        result.append(polygon(PL,false));
  394.        PL.clear();
  395.       }
  396.   }
  397.  
  398.  SUB.make_directed();
  399.  
  400. #endif
  401. */
  402.  
  403.  return result;
  404.  
  405. }
  406.