• Main Page
  • Namespaces
  • Classes
  • Files
  • File List

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

Generated for WFMath by  doxygen 1.7.1