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       return -1;
00350   }
00351 }
00352 
00353 template<const int dim>
00354 inline bool Intersect(const Polygon<dim>& r, const Point<dim>& p, bool proper)
00355 {
00356   Point<2> p2;
00357 
00358   return r.m_poly.numCorners() > 0 && r.m_orient.checkContained(p, p2)
00359          && Intersect(r.m_poly, p2, proper);
00360 }
00361 
00362 template<const int dim>
00363 inline bool Contains(const Point<dim>& p, const Polygon<dim>& r, bool proper)
00364 {
00365   if(r.m_poly.numCorners() == 0)
00366     return true;
00367 
00368   if(proper)
00369     return false;
00370 
00371   for(int i = 1; i < r.m_poly.numCorners(); ++i)
00372     if(r.m_poly[i] != r.m_poly[0])
00373       return false;
00374 
00375   Point<2> p2;
00376 
00377   return r.m_orient.checkContained(p, p2) && p2 == r.m_poly[0];
00378 }
00379 
00380 template<const int dim>
00381 bool Intersect(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00382 {
00383   int corners = p.m_poly.numCorners();
00384 
00385   if(corners == 0)
00386     return false;
00387 
00388   Point<2> p2;
00389 
00390   if(!p.m_orient.checkIntersect(b, p2, proper))
00391     return false;
00392 
00393   Segment<dim> s;
00394   s.endpoint(0) = p.m_orient.convert(p.m_poly.getCorner(corners-1));
00395   int next_end = 1;
00396 
00397   for(int i = 0; i < corners; ++i) {
00398     s.endpoint(next_end) = p.m_orient.convert(p.m_poly.getCorner(i));
00399     if(Intersect(b, s, proper))
00400       return true;
00401     next_end = next_end ? 0 : 1;
00402   }
00403 
00404   return Contains(p, p2, proper);
00405 }
00406 
00407 template<const int dim>
00408 bool _PolyContainsBox(const _Poly2Orient<dim> &orient, const Polygon<2> &poly,
00409                   const Point<dim> &corner, const Vector<dim> &size, bool proper)
00410 {
00411   int num_dim = 0, nonzero_dim = -1;
00412 
00413   for(int i = 0; i < dim; ++i) {
00414     if(size[i] == 0)
00415       continue;
00416     if(num_dim == 2)
00417       return false;
00418     if(nonzero_dim == -1 || fabs(size[nonzero_dim]) < fabs(size[i]));
00419       nonzero_dim = i;
00420     ++num_dim;
00421   }
00422 
00423   Point<2> corner1;
00424 
00425   if(!orient.checkContained(corner, corner1))
00426     return false;
00427 
00428   if(num_dim == 0)
00429     return Contains(poly, corner1, proper);
00430 
00431   Point<2> corner2;
00432 
00433   if(!orient.checkContained(corner + size, corner2))
00434     return false;
00435 
00436   if(num_dim == 1)
00437     return Contains(poly, Segment<2>(corner1, corner2), proper);
00438 
00439   Point<dim> other_corner = corner;
00440   other_corner[nonzero_dim] += size[nonzero_dim];
00441 
00442   Point<2> corner3;
00443   if(!orient.checkContained(other_corner, corner3))
00444     return false;
00445 
00446   // Create a RotBox<2>
00447 
00448   Vector<2> vec1(corner2 - corner1), vec2(corner3 - corner1);
00449 
00450   RotMatrix<2> m; // A matrix which gives the rotation from the x-axis to vec1
00451 
00452   try {
00453     m.rotation(Vector<2>(1, 0), vec1);
00454   }
00455   catch(ColinearVectors<2>) { // vec1 is parallel to (-1, 0), so we're fine
00456     m.identity();
00457   }
00458 
00459   RotBox<2> box(corner1, ProdInv(vec2, m), m);
00460 
00461   return Contains(poly, box, proper);
00462 }
00463 
00464 template<const int dim>
00465 inline bool Contains(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00466 {
00467   return _PolyContainsBox(p.m_orient, p.m_poly, b.m_low, b.m_high - b.m_low, proper);
00468 }
00469 
00470 template<const int dim>
00471 inline bool Contains(const AxisBox<dim>& b, const Polygon<dim>& p, bool proper)
00472 {
00473   for(int i = 0; i < p.m_poly.numCorners(); ++i)
00474     if(!Contains(b, p.getCorner(i), proper))
00475       return false;
00476 
00477   return true;
00478 }
00479 
00480 template<const int dim>
00481 inline bool Intersect(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00482 {
00483   if(p.m_poly.numCorners() == 0)
00484     return false;
00485 
00486   Point<2> c2;
00487   CoordType dist;
00488 
00489   dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00490 
00491   if(_Less(dist, 0, proper))
00492     return false;
00493 
00494   return Intersect(p.m_poly, Ball<2>(c2, sqrt(dist)), proper);
00495 }
00496 
00497 template<const int dim>
00498 inline bool Contains(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00499 {
00500   if(p.m_poly.numCorners() == 0)
00501     return false;
00502 
00503   if(b.m_radius > 0)
00504     return false;
00505 
00506   Point<2> c2;
00507 
00508   if(!p.m_orient.checkContained(b.m_center, c2))
00509     return false;
00510 
00511   return Contains(p.m_poly, c2, proper);
00512 }
00513 
00514 template<const int dim>
00515 inline bool Contains(const Ball<dim>& b, const Polygon<dim>& p, bool proper)
00516 {
00517   if(p.m_poly.numCorners() == 0)
00518     return true;
00519 
00520   Point<2> c2;
00521   CoordType dist;
00522 
00523   dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00524 
00525   if(_Less(dist, 0, proper))
00526     return false;
00527 
00528   for(int i = 0; i != p.m_poly.numCorners(); ++i)
00529     if(_Less(dist, SquaredDistance(c2, p.m_poly[i]), proper))
00530       return false;
00531 
00532   return true;
00533 }
00534 
00535 template<const int dim>
00536 bool Intersect(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00537 {
00538   if(p.m_poly.numCorners() == 0)
00539     return false;
00540 
00541   Point<2> p1, p2;
00542   CoordType d1, d2;
00543   Vector<dim> v1, v2;
00544 
00545   v1 = p.m_orient.offset(s.m_p1, p1);
00546   v2 = p.m_orient.offset(s.m_p2, p2);
00547 
00548   if(Dot(v1, v2) > 0) // Both points on same side of sheet
00549     return false;
00550 
00551   d1 = v1.mag();
00552   d2 = v2.mag();
00553   Point<2> p_intersect;
00554 
00555   if(d1 + d2 == 0) // Avoid divide by zero later
00556     return Intersect(p.m_poly, Segment<2>(p1, p2), proper);
00557 
00558   for(int i = 0; i < 2; ++i)
00559     p_intersect[i] = (p1[i] * d2 + p2[i] * d1) / (d1 + d2);
00560 
00561   return Intersect(p.m_poly, p_intersect, proper);
00562 }
00563 
00564 template<const int dim>
00565 inline bool Contains(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00566 {
00567   if(p.m_poly.numCorners() == 0)
00568     return false;
00569 
00570   Segment<2> s2;
00571 
00572   if(!p.m_orient.checkContained(s.m_p1, s2.endpoint(0)))
00573     return false;
00574   if(!p.m_orient.checkContained(s.m_p2, s2.endpoint(1)))
00575     return false;
00576 
00577   return Contains(p.m_poly, s2, proper);
00578 }
00579 
00580 template<const int dim>
00581 inline bool Contains(const Segment<dim>& s, const Polygon<dim>& p, bool proper)
00582 {
00583   if(p.m_poly.numCorners() == 0)
00584     return true;
00585 
00586   // Expand the basis to include the segment, this deals well with
00587   // degenerate polygons
00588 
00589   Segment<2> s2;
00590   _Poly2Orient<dim> orient(p.m_orient);
00591 
00592   for(int i = 0; i < 2; ++i)
00593     if(!orient.expand(s.endpoint(i), s2.endpoint(i)))
00594       return false;
00595 
00596   return Contains(s2, p.m_poly, proper);
00597 }
00598 
00599 template<const int dim>
00600 bool Intersect(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00601 {
00602   int corners = p.m_poly.numCorners();
00603 
00604   if(corners == 0)
00605     return false;
00606 
00607   _Poly2Orient<dim> orient(p.m_orient);
00608   // FIXME rotateInverse()
00609   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00610 
00611   AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00612 
00613   Point<2> p2;
00614 
00615   if(!orient.checkIntersect(b, p2, proper))
00616     return false;
00617 
00618   Segment<dim> s;
00619   s.endpoint(0) = orient.convert(p.m_poly.getCorner(corners-1));
00620   int next_end = 1;
00621 
00622   for(int i = 0; i < corners; ++i) {
00623     s.endpoint(next_end) = orient.convert(p.m_poly.getCorner(i));
00624     if(Intersect(b, s, proper))
00625       return true;
00626     next_end = next_end ? 0 : 1;
00627   }
00628 
00629   return Contains(p, p2, proper);
00630 }
00631 
00632 template<const int dim>
00633 inline bool Contains(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00634 {
00635   _Poly2Orient<dim> orient(p.m_orient);
00636   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00637 
00638   return _PolyContainsBox(orient, p.m_poly, r.m_corner0, r.m_size, proper);
00639 }
00640 
00641 template<const int dim>
00642 inline bool Contains(const RotBox<dim>& r, const Polygon<dim>& p, bool proper)
00643 {
00644   if(p.m_poly.numCorners() == 0)
00645     return true;
00646 
00647   AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00648 
00649   _Poly2Orient<dim> orient(p.m_orient);
00650   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00651 
00652   for(int i = 0; i < p.m_poly.numCorners(); ++i)
00653     if(!Contains(b, orient.convert(p.m_poly[i]), proper))
00654       return false;
00655 
00656   return true;
00657 }
00658 
00659 bool _PolyPolyIntersect(const Polygon<2> &poly1, const Polygon<2> &poly2,
00660                         const int intersect_dim,
00661                         const _Poly2OrientIntersectData &data, bool proper);
00662 
00663 template<const int dim>
00664 inline bool Intersect(const Polygon<dim>& p1, const Polygon<dim>& p2, bool proper)
00665 {
00666   _Poly2OrientIntersectData data;
00667 
00668   int intersect_dim = _Intersect(p1.m_orient, p2.m_orient, data);
00669 
00670   return _PolyPolyIntersect(p1.m_poly, p2.m_poly, intersect_dim, data, proper);
00671 }
00672 
00673 bool _PolyPolyContains(const Polygon<2> &outer, const Polygon<2> &inner,
00674                        const int intersect_dim,
00675                        const _Poly2OrientIntersectData &data, bool proper);
00676 
00677 template<const int dim>
00678 inline bool Contains(const Polygon<dim>& outer, const Polygon<dim>& inner, bool proper)
00679 {
00680   if(outer.m_poly.numCorners() == 0)
00681     return !proper && inner.m_poly.numCorners() == 0;
00682 
00683   if(inner.m_poly.numCorners() == 0)
00684     return true;
00685 
00686   _Poly2OrientIntersectData data;
00687 
00688   int intersect_dim = _Intersect(outer.m_orient, inner.m_orient, data);
00689 
00690   return _PolyPolyContains(outer.m_poly, inner.m_poly, intersect_dim, data, proper);
00691 }
00692 
00693 template<>
00694 bool Intersect(const Polygon<2>& r, const Point<2>& p, bool proper);
00695 template<>
00696 bool Contains(const Point<2>& p, const Polygon<2>& r, bool proper);
00697 
00698 template<>
00699 bool Intersect(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00700 template<>
00701 bool Contains(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00702 template<>
00703 bool Contains(const AxisBox<2>& b, const Polygon<2>& p, bool proper);
00704 
00705 template<>
00706 bool Intersect(const Polygon<2>& p, const Ball<2>& b, bool proper);
00707 template<>
00708 bool Contains(const Polygon<2>& p, const Ball<2>& b, bool proper);
00709 template<>
00710 bool Contains(const Ball<2>& b, const Polygon<2>& p, bool proper);
00711 
00712 template<>
00713 bool Intersect(const Polygon<2>& r, const Segment<2>& s, bool proper);
00714 template<>
00715 bool Contains(const Polygon<2>& p, const Segment<2>& s, bool proper);
00716 template<>
00717 bool Contains(const Segment<2>& s, const Polygon<2>& p, bool proper);
00718 
00719 template<>
00720 bool Intersect(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00721 template<>
00722 bool Contains(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00723 template<>
00724 bool Contains(const RotBox<2>& r, const Polygon<2>& p, bool proper);
00725 
00726 template<>
00727 bool Intersect(const Polygon<2>& p1, const Polygon<2>& p2, bool proper);
00728 template<>
00729 bool Contains(const Polygon<2>& outer, const Polygon<2>& inner, bool proper);
00730 
00731 } // namespace WFMath
00732 
00733 #endif  // WFMATH_POLYGON_INTERSECT_H

Generated on Tue Dec 11 06:29:45 2007 for WFMath by  doxygen 1.5.4