polygon_intersect.h

00001 // polygon_funcs.h (Polygon<> intersection functions)
00002 //
00003 //  The WorldForge Project
00004 //  Copyright (C) 2002  The WorldForge Project
00005 //
00006 //  This program is free software; you can redistribute it and/or modify
00007 //  it under the terms of the GNU General Public License as published by
00008 //  the Free Software Foundation; either version 2 of the License, or
00009 //  (at your option) any later version.
00010 //
00011 //  This program is distributed in the hope that it will be useful,
00012 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 //  GNU General Public License for more details.
00015 //
00016 //  You should have received a copy of the GNU General Public License
00017 //  along with this program; if not, write to the Free Software
00018 //  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00019 //
00020 //  For information about WorldForge and its authors, please contact
00021 //  the Worldforge Web Site at http://www.worldforge.org.
00022 //
00023 
00024 // Author: Ron Steinke
00025 // Created: 2002-2-20
00026 
00027 #ifndef WFMATH_POLYGON_INTERSECT_H
00028 #define WFMATH_POLYGON_INTERSECT_H
00029 
00030 #include <wfmath/const.h>
00031 #include <wfmath/vector.h>
00032 #include <wfmath/point.h>
00033 #include <wfmath/axisbox.h>
00034 #include <wfmath/ball.h>
00035 #include <wfmath/polygon.h>
00036 #include <wfmath/intersect.h>
00037 
00038 #ifndef _MSC_VER
00039 #warning "The Intersect() and Contains() functions involving WFMath::Polygon<>"
00040 #warning "are still under development, and probably shouldn't be used yet."
00041 #else
00042 #pragma warning "The Intersect() and Contains() functions involving WFMath::Polygon<>"
00043 #pragma warning "are still under development, and probably shouldn't be used yet."
00044 #endif
00045 
00046 namespace WFMath {
00047 
00048 template<const int dim>
00049 inline Vector<dim> _Poly2Orient<dim>::offset(const Point<dim>& pd, Point<2>& p2) const
00050 {
00051   assert(m_origin.isValid()); // Check for empty polygon before calling this
00052 
00053   Vector<dim> out = pd - m_origin;
00054 
00055   for(int j = 0; j < 2; ++j) {
00056     p2[j] = Dot(out, m_axes[j]);
00057     out -= p2[j] * m_axes[j];
00058   }
00059 
00060   return out;
00061 }
00062 
00063 template<const int dim>
00064 inline bool _Poly2Orient<dim>::checkContained(const Point<dim>& pd, Point<2> & p2) const
00065 {
00066   Vector<dim> off = offset(pd, p2);
00067 
00068   CoordType sqrsum = 0;
00069   for(int i = 0; i < dim; ++i)
00070     sqrsum += pd[i] * pd[i];
00071 
00072   return off.sqrMag() < WFMATH_EPSILON * sqrsum;
00073 }
00074 
00075 template<>
00076 bool _Poly2Orient<3>::checkIntersectPlane(const AxisBox<3>& b, Point<2>& p2,
00077                                           bool proper) const;
00078 
00079 template<const int dim>
00080 bool _Poly2Orient<dim>::checkIntersect(const AxisBox<dim>& b, Point<2>& p2,
00081                                        bool proper) const
00082 {
00083   assert(m_origin.isValid());
00084 
00085   if(!m_axes[0].isValid()) {
00086     // Single point
00087     p2[0] = p2[1] = 0;
00088     return Intersect(b, convert(p2), proper);
00089   }
00090 
00091   if(m_axes[1].isValid()) {
00092     // A plane
00093 
00094     // I only know how to do this in 3D, so write a function which will
00095     // specialize to different dimensions
00096 
00097     return checkIntersectPlane(b, p2, proper);
00098   }
00099 
00100   // A line
00101 
00102   // This is a modified version of AxisBox<>/Segment<> intersection
00103 
00104   CoordType min = 0, max = 0; // Initialize to avoid compiler warnings
00105   bool got_bounds = false;
00106 
00107   for(int i = 0; i < dim; ++i) {
00108     const CoordType dist = (m_axes[0])[i]; // const may optimize away better
00109     if(dist == 0) {
00110       if(_Less(m_origin[i], b.lowCorner()[i], proper)
00111         || _Greater(m_origin[i], b.highCorner()[i], proper))
00112         return false;
00113     }
00114     else {
00115       CoordType low = (b.lowCorner()[i] - m_origin[i]) / dist;
00116       CoordType high = (b.highCorner()[i] - m_origin[i]) / dist;
00117       if(low > high) {
00118         CoordType tmp = high;
00119         high = low;
00120         low = tmp;
00121       }
00122       if(got_bounds) {
00123         if(low > min)
00124           min = low;
00125         if(high < max)
00126           max = high;
00127       }
00128       else {
00129         min = low;
00130         max = high;
00131         got_bounds = true;
00132       }
00133     }
00134   }
00135 
00136   assert(got_bounds); // We can't be parallel in _all_ dimensions
00137 
00138   if(_LessEq(min, max, proper)) {
00139     p2[0] = (max - min) / 2;
00140     p2[1] = 0;
00141     return true;
00142   }
00143   else
00144     return false;
00145 }
00146 
00147 template<const int dim>
00148 int  _Intersect(const _Poly2Orient<dim> &o1, const _Poly2Orient<dim> &o2,
00149                 _Poly2OrientIntersectData &data)
00150 {
00151   if(!o1.m_origin.isValid() || !o2.m_origin.isValid()) { // No points
00152     return -1;
00153   }
00154 
00155   // Check for single point basis
00156 
00157   if(!o1.m_axes[0].isValid()) {
00158     if(!o2.checkContained(o1.m_origin, data.p2))
00159       return -1; // no intersect
00160 
00161     _Poly2OrientIntersectData data;
00162 
00163     data.p1[0] = data.p1[1] = 0;
00164 
00165     return 0; // point intersect
00166   }
00167 
00168   if(!o2.m_axes[0].isValid()) {
00169     if(!o1.checkContained(o2.m_origin, data.p1))
00170       return -1; // no intersect
00171 
00172     data.p2[0] = data.p2[1] = 0;
00173 
00174     return 0; // point intersect
00175   }
00176 
00177   // Find a common basis for the plane's orientations
00178   // by projecting out the part of o1's basis that lies
00179   // in o2's basis
00180 
00181   Vector<dim> basis1, basis2;
00182   CoordType sqrmag1, sqrmag2;
00183   int basis_size = 0;
00184 
00185   basis1 = o2.m_axes[0] * Dot(o2.m_axes[0], o1.m_axes[0]);
00186   if(o2.m_axes[1].isValid())
00187     basis1 += o2.m_axes[1] * Dot(o2.m_axes[1], o1.m_axes[0]);
00188 
00189   // Don't need to scale, the m_axes are unit vectors
00190   sqrmag1 = basis1.sqrMag();
00191   if(sqrmag1 > WFMATH_EPSILON * WFMATH_EPSILON)
00192     basis_size = 1;
00193 
00194   if(o1.m_axes[1].isValid()) {
00195     basis2 = o2.m_axes[0] * Dot(o2.m_axes[0], o1.m_axes[1]);
00196     if(o2.m_axes[1].isValid())
00197       basis2 += o2.m_axes[1] * Dot(o2.m_axes[1], o1.m_axes[1]);
00198 
00199     // Project out part parallel to basis1
00200     if(basis_size == 1)
00201       basis2 -= basis1 * (Dot(basis1, basis2) / sqrmag1);
00202 
00203     sqrmag2 = basis2.sqrMag();
00204     if(sqrmag2 > WFMATH_EPSILON * WFMATH_EPSILON) {
00205       if(basis_size++ == 0) {
00206         basis1 = basis2;
00207         sqrmag1 = sqrmag2;
00208       }
00209     }
00210   }
00211 
00212   Vector<dim> off = o2.m_origin - o1.m_origin;
00213 
00214   switch(basis_size) {
00215     case 0:
00216       {
00217       // All vectors are orthogonal, check for a common point in the plane
00218       // This can happen even in 3d for degenerate bases
00219 
00220       data.p1[0] = Dot(o1.m_axes[0], off);
00221       Vector<dim> off1 = o1.m_axes[0] * data.p1[0];
00222       if(o1.m_axes[1].isValid()) {
00223         data.p1[1] = Dot(o1.m_axes[1], off);
00224         off1 += o1.m_axes[1] * data.p1[1];
00225       }
00226       else
00227         data.p1[1] = 0;
00228 
00229       data.p2[0] = -Dot(o2.m_axes[0], off);
00230       Vector<dim> off2 = o2.m_axes[0] * data.p2[0];
00231       if(o1.m_axes[1].isValid()) {
00232         data.p2[1] = -Dot(o2.m_axes[1], off);
00233         off2 += o1.m_axes[1] * data.p2[1];
00234       }
00235       else
00236         data.p2[1] = 0;
00237 
00238       if(off1 - off2 != off) // No common point
00239         return -1;
00240       else  // Got a point
00241         return 1;
00242       }
00243     case 1:
00244       {
00245       // Check for an intersection line
00246 
00247       data.o1_is_line = !o1.m_axes[1].isValid();
00248       data.o2_is_line = !o2.m_axes[1].isValid();
00249 
00250       if(!o1.m_axes[1].isValid() && !o2.m_axes[1].isValid()) {
00251         CoordType proj = Dot(off, o2.m_axes[0]);
00252         if(off != o2.m_axes[0] * proj)
00253           return -1;
00254 
00255         data.v1[0] = 1;
00256         data.v1[1] = 0;
00257         data.p1[0] = data.p1[1] = 0;
00258         data.v2[0] = (Dot(o1.m_axes[0], o2.m_axes[0]) > 0) ? 1 : -1;
00259         data.v2[1] = 0;
00260         data.p2[0] = -proj;
00261         data.p2[1] = 0;
00262 
00263         return 1;
00264       }
00265 
00266       if(!o1.m_axes[1].isValid()) {
00267         data.p2[0] = -Dot(off, o2.m_axes[0]);
00268         data.p2[1] = -Dot(off, o2.m_axes[1]);
00269 
00270         if(off != - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
00271           return -1;
00272 
00273         data.v1[0] = 1;
00274         data.v1[1] = 0;
00275         data.p1[0] = data.p1[1] = 0;
00276         data.v2[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
00277         data.v2[1] = Dot(o1.m_axes[0], o2.m_axes[1]);
00278 
00279         return 1;
00280       }
00281 
00282       if(!o2.m_axes[1].isValid()) {
00283         data.p1[0] = Dot(off, o1.m_axes[0]);
00284         data.p1[1] = Dot(off, o1.m_axes[1]);
00285 
00286         if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1])
00287           return -1;
00288 
00289         data.v2[0] = 1;
00290         data.v2[1] = 0;
00291         data.p2[0] = data.p2[1] = 0;
00292         data.v1[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
00293         data.v1[1] = Dot(o1.m_axes[1], o2.m_axes[0]);
00294 
00295         return 1;
00296       }
00297 
00298       data.p1[0] = Dot(off, o1.m_axes[0]);
00299       data.p1[1] = Dot(off, o1.m_axes[1]);
00300       data.p2[0] = -Dot(off, o2.m_axes[0]);
00301       data.p2[1] = -Dot(off, o2.m_axes[1]);
00302 
00303       if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1]
00304         - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
00305         return -1;
00306 
00307       basis1 /= sqrt(sqrmag1);
00308 
00309       data.v1[0] = Dot(o1.m_axes[0], basis1);
00310       data.v1[1] = Dot(o1.m_axes[1], basis1);
00311       data.v2[0] = Dot(o2.m_axes[0], basis1);
00312       data.v2[1] = Dot(o2.m_axes[1], basis1);
00313 
00314       return 1;
00315       }
00316     case 2:
00317       {
00318       assert(o1.m_axes[1].isValid() && o2.m_axes[1].isValid());
00319 
00320       // The planes are parallel, check if they are the same plane
00321       CoordType off_sqr_mag = data.off.sqrMag();
00322 
00323       // Find the offset between the origins in o2's coordnates
00324 
00325       if(off_sqr_mag != 0) { // The offsets aren't identical
00326         Vector<dim> off_copy = off;
00327 
00328         data.off[0] = Dot(o2.m_axes[0], off);
00329         off_copy -= o1.m_axes[0] * data.off[0];
00330         data.off[1] = Dot(o2.m_axes[1], off);
00331         off_copy -= o1.m_axes[1] * data.off[1];
00332 
00333         if(off_copy.sqrMag() > off_sqr_mag * WFMATH_EPSILON)
00334           return -1; // The planes are different
00335       }
00336       else
00337         data.off[0] = data.off[1] = 0;
00338 
00339       // Define o2's basis vectors in o1's coordinates
00340       data.v1[0] = Dot(o2.m_axes[0], o1.m_axes[0]);
00341       data.v1[1] = Dot(o2.m_axes[0], o1.m_axes[1]);
00342       data.v2[0] = Dot(o2.m_axes[1], o1.m_axes[0]);
00343       data.v2[1] = Dot(o2.m_axes[1], o1.m_axes[1]);
00344 
00345       return 2;
00346       }
00347     default:
00348       assert(false);
00349   }
00350 }
00351 
00352 template<const int dim>
00353 inline bool Intersect(const Polygon<dim>& r, const Point<dim>& p, bool proper)
00354 {
00355   Point<2> p2;
00356 
00357   return r.m_poly.numCorners() > 0 && r.m_orient.checkContained(p, p2)
00358          && Intersect(r.m_poly, p2, proper);
00359 }
00360 
00361 template<const int dim>
00362 inline bool Contains(const Point<dim>& p, const Polygon<dim>& r, bool proper)
00363 {
00364   if(r.m_poly.numCorners() == 0)
00365     return true;
00366 
00367   if(proper)
00368     return false;
00369 
00370   for(int i = 1; i < r.m_poly.numCorners(); ++i)
00371     if(r.m_poly[i] != r.m_poly[0])
00372       return false;
00373 
00374   Point<2> p2;
00375 
00376   return r.m_orient.checkContained(p, p2) && p2 == r.m_poly[0];
00377 }
00378 
00379 template<const int dim>
00380 bool Intersect(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00381 {
00382   int corners = p.m_poly.numCorners();
00383 
00384   if(corners == 0)
00385     return false;
00386 
00387   Point<2> p2;
00388 
00389   if(!p.m_orient.checkIntersect(b, p2, proper))
00390     return false;
00391 
00392   Segment<dim> s;
00393   s.endpoint(0) = p.m_orient.convert(p.m_poly.getCorner(corners-1));
00394   int next_end = 1;
00395 
00396   for(int i = 0; i < corners; ++i) {
00397     s.endpoint(next_end) = p.m_orient.convert(p.m_poly.getCorner(i));
00398     if(Intersect(b, s, proper))
00399       return true;
00400     next_end = next_end ? 0 : 1;
00401   }
00402 
00403   return Contains(p, p2, proper);
00404 }
00405 
00406 template<const int dim>
00407 bool _PolyContainsBox(const _Poly2Orient<dim> &orient, const Polygon<2> &poly,
00408                   const Point<dim> &corner, const Vector<dim> &size, bool proper)
00409 {
00410   int num_dim = 0, nonzero_dim = -1;
00411 
00412   for(int i = 0; i < dim; ++i) {
00413     if(size[i] == 0)
00414       continue;
00415     if(num_dim == 2)
00416       return false;
00417     if(nonzero_dim == -1 || fabs(size[nonzero_dim]) < fabs(size[i]));
00418       nonzero_dim = i;
00419     ++num_dim;
00420   }
00421 
00422   Point<2> corner1;
00423 
00424   if(!orient.checkContained(corner, corner1))
00425     return false;
00426 
00427   if(num_dim == 0)
00428     return Contains(poly, corner1, proper);
00429 
00430   Point<2> corner2;
00431 
00432   if(!orient.checkContained(corner + size, corner2))
00433     return false;
00434 
00435   if(num_dim == 1)
00436     return Contains(poly, Segment<2>(corner1, corner2), proper);
00437 
00438   Point<dim> other_corner = corner;
00439   other_corner[nonzero_dim] += size[nonzero_dim];
00440 
00441   Point<2> corner3;
00442   if(!orient.checkContained(other_corner, corner3))
00443     return false;
00444 
00445   // Create a RotBox<2>
00446 
00447   Vector<2> vec1(corner2 - corner1), vec2(corner3 - corner1);
00448 
00449   RotMatrix<2> m; // A matrix which gives the rotation from the x-axis to vec1
00450 
00451   try {
00452     m.rotation(Vector<2>(1, 0), vec1);
00453   }
00454   catch(ColinearVectors<2>) { // vec1 is parallel to (-1, 0), so we're fine
00455     m.identity();
00456   }
00457 
00458   RotBox<2> box(corner1, ProdInv(vec2, m), m);
00459 
00460   return Contains(poly, box, proper);
00461 }
00462 
00463 template<const int dim>
00464 inline bool Contains(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00465 {
00466   return _PolyContainsBox(p.m_orient, p.m_poly, b.m_low, b.m_high - b.m_low, proper);
00467 }
00468 
00469 template<const int dim>
00470 inline bool Contains(const AxisBox<dim>& b, const Polygon<dim>& p, bool proper)
00471 {
00472   for(int i = 0; i < p.m_poly.numCorners(); ++i)
00473     if(!Contains(b, p.getCorner(i), proper))
00474       return false;
00475 
00476   return true;
00477 }
00478 
00479 template<const int dim>
00480 inline bool Intersect(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00481 {
00482   if(p.m_poly.numCorners() == 0)
00483     return false;
00484 
00485   Point<2> c2;
00486   CoordType dist;
00487 
00488   dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00489 
00490   if(_Less(dist, 0, proper))
00491     return false;
00492 
00493   return Intersect(p.m_poly, Ball<2>(c2, sqrt(dist)), proper);
00494 }
00495 
00496 template<const int dim>
00497 inline bool Contains(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00498 {
00499   if(p.m_poly.numCorners() == 0)
00500     return false;
00501 
00502   if(b.m_radius > 0)
00503     return false;
00504 
00505   Point<2> c2;
00506 
00507   if(!p.m_orient.checkContained(b.m_center, c2))
00508     return false;
00509 
00510   return Contains(p.m_poly, c2, proper);
00511 }
00512 
00513 template<const int dim>
00514 inline bool Contains(const Ball<dim>& b, const Polygon<dim>& p, bool proper)
00515 {
00516   if(p.m_poly.numCorners() == 0)
00517     return true;
00518 
00519   Point<2> c2;
00520   CoordType dist;
00521 
00522   dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00523 
00524   if(_Less(dist, 0, proper))
00525     return false;
00526 
00527   for(int i = 0; i != p.m_poly.numCorners(); ++i)
00528     if(_Less(dist, SquaredDistance(c2, p.m_poly[i]), proper))
00529       return false;
00530 
00531   return true;
00532 }
00533 
00534 template<const int dim>
00535 bool Intersect(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00536 {
00537   if(p.m_poly.numCorners() == 0)
00538     return false;
00539 
00540   Point<2> p1, p2;
00541   CoordType d1, d2;
00542   Vector<dim> v1, v2;
00543 
00544   v1 = p.m_orient.offset(s.m_p1, p1);
00545   v2 = p.m_orient.offset(s.m_p2, p2);
00546 
00547   if(Dot(v1, v2) > 0) // Both points on same side of sheet
00548     return false;
00549 
00550   d1 = v1.mag();
00551   d2 = v2.mag();
00552   Point<2> p_intersect;
00553 
00554   if(d1 + d2 == 0) // Avoid divide by zero later
00555     return Intersect(p.m_poly, Segment<2>(p1, p2), proper);
00556 
00557   for(int i = 0; i < 2; ++i)
00558     p_intersect[i] = (p1[i] * d2 + p2[i] * d1) / (d1 + d2);
00559 
00560   return Intersect(p.m_poly, p_intersect, proper);
00561 }
00562 
00563 template<const int dim>
00564 inline bool Contains(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00565 {
00566   if(p.m_poly.numCorners() == 0)
00567     return false;
00568 
00569   Segment<2> s2;
00570 
00571   if(!p.m_orient.checkContained(s.m_p1, s2.endpoint(0)))
00572     return false;
00573   if(!p.m_orient.checkContained(s.m_p2, s2.endpoint(1)))
00574     return false;
00575 
00576   return Contains(p.m_poly, s2, proper);
00577 }
00578 
00579 template<const int dim>
00580 inline bool Contains(const Segment<dim>& s, const Polygon<dim>& p, bool proper)
00581 {
00582   if(p.m_poly.numCorners() == 0)
00583     return true;
00584 
00585   // Expand the basis to include the segment, this deals well with
00586   // degenerate polygons
00587 
00588   Segment<2> s2;
00589   _Poly2Orient<dim> orient(p.m_orient);
00590 
00591   for(int i = 0; i < 2; ++i)
00592     if(!orient.expand(s.endpoint(i), s2.endpoint(i)))
00593       return false;
00594 
00595   return Contains(s2, p.m_poly, proper);
00596 }
00597 
00598 template<const int dim>
00599 bool Intersect(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00600 {
00601   int corners = p.m_poly.numCorners();
00602 
00603   if(corners == 0)
00604     return false;
00605 
00606   _Poly2Orient<dim> orient(p.m_orient);
00607   // FIXME rotateInverse()
00608   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00609 
00610   AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00611 
00612   Point<2> p2;
00613 
00614   if(!orient.checkIntersect(b, p2, proper))
00615     return false;
00616 
00617   Segment<dim> s;
00618   s.endpoint(0) = orient.convert(p.m_poly.getCorner(corners-1));
00619   int next_end = 1;
00620 
00621   for(int i = 0; i < corners; ++i) {
00622     s.endpoint(next_end) = orient.convert(p.m_poly.getCorner(i));
00623     if(Intersect(b, s, proper))
00624       return true;
00625     next_end = next_end ? 0 : 1;
00626   }
00627 
00628   return Contains(p, p2, proper);
00629 }
00630 
00631 template<const int dim>
00632 inline bool Contains(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00633 {
00634   _Poly2Orient<dim> orient(p.m_orient);
00635   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00636 
00637   return _PolyContainsBox(orient, p.m_poly, r.m_corner0, r.m_size, proper);
00638 }
00639 
00640 template<const int dim>
00641 inline bool Contains(const RotBox<dim>& r, const Polygon<dim>& p, bool proper)
00642 {
00643   if(p.m_poly.numCorners() == 0)
00644     return true;
00645 
00646   AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00647 
00648   _Poly2Orient<dim> orient(p.m_orient);
00649   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00650 
00651   for(int i = 0; i < p.m_poly.numCorners(); ++i)
00652     if(!Contains(b, orient.convert(p.m_poly[i]), proper))
00653       return false;
00654 
00655   return true;
00656 }
00657 
00658 bool _PolyPolyIntersect(const Polygon<2> &poly1, const Polygon<2> &poly2,
00659                         const int intersect_dim,
00660                         const _Poly2OrientIntersectData &data, bool proper);
00661 
00662 template<const int dim>
00663 inline bool Intersect(const Polygon<dim>& p1, const Polygon<dim>& p2, bool proper)
00664 {
00665   _Poly2OrientIntersectData data;
00666 
00667   int intersect_dim = _Intersect(p1.m_orient, p2.m_orient, data);
00668 
00669   return _PolyPolyIntersect(p1.m_poly, p2.m_poly, intersect_dim, data, proper);
00670 }
00671 
00672 bool _PolyPolyContains(const Polygon<2> &outer, const Polygon<2> &inner,
00673                        const int intersect_dim,
00674                        const _Poly2OrientIntersectData &data, bool proper);
00675 
00676 template<const int dim>
00677 inline bool Contains(const Polygon<dim>& outer, const Polygon<dim>& inner, bool proper)
00678 {
00679   if(outer.m_poly.numCorners() == 0)
00680     return !proper && inner.m_poly.numCorners() == 0;
00681 
00682   if(inner.m_poly.numCorners() == 0)
00683     return true;
00684 
00685   _Poly2OrientIntersectData data;
00686 
00687   int intersect_dim = _Intersect(outer.m_orient, inner.m_orient, data);
00688 
00689   return _PolyPolyContains(outer.m_poly, inner.m_poly, intersect_dim, data, proper);
00690 }
00691 
00692 template<>
00693 bool Intersect(const Polygon<2>& r, const Point<2>& p, bool proper);
00694 template<>
00695 bool Contains(const Point<2>& p, const Polygon<2>& r, bool proper);
00696 
00697 template<>
00698 bool Intersect(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00699 template<>
00700 bool Contains(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00701 template<>
00702 bool Contains(const AxisBox<2>& b, const Polygon<2>& p, bool proper);
00703 
00704 template<>
00705 bool Intersect(const Polygon<2>& p, const Ball<2>& b, bool proper);
00706 template<>
00707 bool Contains(const Polygon<2>& p, const Ball<2>& b, bool proper);
00708 template<>
00709 bool Contains(const Ball<2>& b, const Polygon<2>& p, bool proper);
00710 
00711 template<>
00712 bool Intersect(const Polygon<2>& r, const Segment<2>& s, bool proper);
00713 template<>
00714 bool Contains(const Polygon<2>& p, const Segment<2>& s, bool proper);
00715 template<>
00716 bool Contains(const Segment<2>& s, const Polygon<2>& p, bool proper);
00717 
00718 template<>
00719 bool Intersect(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00720 template<>
00721 bool Contains(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00722 template<>
00723 bool Contains(const RotBox<2>& r, const Polygon<2>& p, bool proper);
00724 
00725 template<>
00726 bool Intersect(const Polygon<2>& p1, const Polygon<2>& p2, bool proper);
00727 template<>
00728 bool Contains(const Polygon<2>& outer, const Polygon<2>& inner, bool proper);
00729 
00730 } // namespace WFMath
00731 
00732 #endif  // WFMATH_POLYGON_INTERSECT_H

Generated on Sun Aug 27 21:30:29 2006 for WFMath by  doxygen 1.4.7