WFMath  1.0.2
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/axisbox.h>
00031 #include <wfmath/ball.h>
00032 #include <wfmath/polygon.h>
00033 #include <wfmath/intersect.h>
00034 #include <wfmath/error.h>
00035 
00036 #include <cmath>
00037 
00038 #include <cassert>
00039 
00040 // FIXME Work is needed on this code. At very least the following notes
00041 // from the original author apply:
00042 // "The Intersect() and Contains() functions involving WFMath::Polygon<>"
00043 // "are still under development, and probably shouldn't be used yet."
00044 
00045 namespace WFMath {
00046 
00047 template<int dim>
00048 inline Vector<dim> _Poly2Orient<dim>::offset(const Point<dim>& pd, Point<2>& p2) const
00049 {
00050   assert(m_origin.isValid()); // Check for empty polygon before calling this
00051 
00052   Vector<dim> out = pd - m_origin;
00053 
00054   for(int j = 0; j < 2; ++j) {
00055     p2[j] = Dot(out, m_axes[j]);
00056     out -= p2[j] * m_axes[j];
00057   }
00058 
00059   return out;
00060 }
00061 
00062 template<int dim>
00063 inline bool _Poly2Orient<dim>::checkContained(const Point<dim>& pd, Point<2> & p2) const
00064 {
00065   Vector<dim> off = offset(pd, p2);
00066 
00067   CoordType sqrsum = 0;
00068   for(int i = 0; i < dim; ++i)
00069     sqrsum += pd[i] * pd[i];
00070 
00071   return off.sqrMag() < numeric_constants<CoordType>::epsilon() * sqrsum;
00072 }
00073 
00074 template<>
00075 bool _Poly2Orient<3>::checkIntersectPlane(const AxisBox<3>& b, Point<2>& p2,
00076                                           bool proper) const;
00077 
00078 template<int dim>
00079 bool _Poly2Orient<dim>::checkIntersect(const AxisBox<dim>& b, Point<2>& p2,
00080                                        bool proper) const
00081 {
00082   assert(m_origin.isValid());
00083 
00084   if(!m_axes[0].isValid()) {
00085     // Single point
00086     p2[0] = p2[1] = 0;
00087     return Intersect(b, convert(p2), proper);
00088   }
00089 
00090   if(m_axes[1].isValid()) {
00091     // A plane
00092 
00093     // I only know how to do this in 3D, so write a function which will
00094     // specialize to different dimensions
00095 
00096     return checkIntersectPlane(b, p2, proper);
00097   }
00098 
00099   // A line
00100 
00101   // This is a modified version of AxisBox<>/Segment<> intersection
00102 
00103   CoordType min = 0, max = 0; // Initialize to avoid compiler warnings
00104   bool got_bounds = false;
00105 
00106   for(int i = 0; i < dim; ++i) {
00107     const CoordType dist = (m_axes[0])[i]; // const may optimize away better
00108     if(dist == 0) {
00109       if(_Less(m_origin[i], b.lowCorner()[i], proper)
00110         || _Greater(m_origin[i], b.highCorner()[i], proper))
00111         return false;
00112     }
00113     else {
00114       CoordType low = (b.lowCorner()[i] - m_origin[i]) / dist;
00115       CoordType high = (b.highCorner()[i] - m_origin[i]) / dist;
00116       if(low > high) {
00117         CoordType tmp = high;
00118         high = low;
00119         low = tmp;
00120       }
00121       if(got_bounds) {
00122         if(low > min)
00123           min = low;
00124         if(high < max)
00125           max = high;
00126       }
00127       else {
00128         min = low;
00129         max = high;
00130         got_bounds = true;
00131       }
00132     }
00133   }
00134 
00135   assert(got_bounds); // We can't be parallel in _all_ dimensions
00136 
00137   if(_LessEq(min, max, proper)) {
00138     p2[0] = (max - min) / 2;
00139     p2[1] = 0;
00140     return true;
00141   }
00142   else
00143     return false;
00144 }
00145 
00146 template<int dim>
00147 int  _Intersect(const _Poly2Orient<dim> &o1, const _Poly2Orient<dim> &o2,
00148                 _Poly2OrientIntersectData &data)
00149 {
00150   if(!o1.m_origin.isValid() || !o2.m_origin.isValid()) { // No points
00151     return -1;
00152   }
00153 
00154   // Check for single point basis
00155 
00156   if(!o1.m_axes[0].isValid()) {
00157     if(!o2.checkContained(o1.m_origin, data.p2))
00158       return -1; // no intersect
00159 
00160     _Poly2OrientIntersectData data;
00161 
00162     data.p1[0] = data.p1[1] = 0;
00163 
00164     return 0; // point intersect
00165   }
00166 
00167   if(!o2.m_axes[0].isValid()) {
00168     if(!o1.checkContained(o2.m_origin, data.p1))
00169       return -1; // no intersect
00170 
00171     data.p2[0] = data.p2[1] = 0;
00172 
00173     return 0; // point intersect
00174   }
00175 
00176   // Find a common basis for the plane's orientations
00177   // by projecting out the part of o1's basis that lies
00178   // in o2's basis
00179 
00180   Vector<dim> basis1, basis2;
00181   CoordType sqrmag1, sqrmag2;
00182   int basis_size = 0;
00183 
00184   basis1 = o2.m_axes[0] * Dot(o2.m_axes[0], o1.m_axes[0]);
00185   if(o2.m_axes[1].isValid())
00186     basis1 += o2.m_axes[1] * Dot(o2.m_axes[1], o1.m_axes[0]);
00187 
00188   // Don't need to scale, the m_axes are unit vectors
00189   sqrmag1 = basis1.sqrMag();
00190   if(sqrmag1 > numeric_constants<CoordType>::epsilon() * numeric_constants<CoordType>::epsilon())
00191     basis_size = 1;
00192 
00193   if(o1.m_axes[1].isValid()) {
00194     basis2 = o2.m_axes[0] * Dot(o2.m_axes[0], o1.m_axes[1]);
00195     if(o2.m_axes[1].isValid())
00196       basis2 += o2.m_axes[1] * Dot(o2.m_axes[1], o1.m_axes[1]);
00197 
00198     // Project out part parallel to basis1
00199     if(basis_size == 1)
00200       basis2 -= basis1 * (Dot(basis1, basis2) / sqrmag1);
00201 
00202     sqrmag2 = basis2.sqrMag();
00203     if(sqrmag2 > numeric_constants<CoordType>::epsilon() * numeric_constants<CoordType>::epsilon()) {
00204       if(basis_size++ == 0) {
00205         basis1 = basis2;
00206         sqrmag1 = sqrmag2;
00207       }
00208     }
00209   }
00210 
00211   Vector<dim> off = o2.m_origin - o1.m_origin;
00212 
00213   switch(basis_size) {
00214     case 0:
00215       {
00216       // All vectors are orthogonal, check for a common point in the plane
00217       // This can happen even in 3d for degenerate bases
00218 
00219       data.p1[0] = Dot(o1.m_axes[0], off);
00220       Vector<dim> off1 = o1.m_axes[0] * data.p1[0];
00221       if(o1.m_axes[1].isValid()) {
00222         data.p1[1] = Dot(o1.m_axes[1], off);
00223         off1 += o1.m_axes[1] * data.p1[1];
00224       }
00225       else
00226         data.p1[1] = 0;
00227 
00228       data.p2[0] = -Dot(o2.m_axes[0], off);
00229       Vector<dim> off2 = o2.m_axes[0] * data.p2[0];
00230       if(o1.m_axes[1].isValid()) {
00231         data.p2[1] = -Dot(o2.m_axes[1], off);
00232         off2 += o1.m_axes[1] * data.p2[1];
00233       }
00234       else
00235         data.p2[1] = 0;
00236 
00237       if(off1 - off2 != off) // No common point
00238         return -1;
00239       else  // Got a point
00240         return 1;
00241       }
00242     case 1:
00243       {
00244       // Check for an intersection line
00245 
00246       data.o1_is_line = !o1.m_axes[1].isValid();
00247       data.o2_is_line = !o2.m_axes[1].isValid();
00248 
00249       if(!o1.m_axes[1].isValid() && !o2.m_axes[1].isValid()) {
00250         CoordType proj = Dot(off, o2.m_axes[0]);
00251         if(off != o2.m_axes[0] * proj)
00252           return -1;
00253 
00254         data.v1[0] = 1;
00255         data.v1[1] = 0;
00256         data.p1[0] = data.p1[1] = 0;
00257         data.v2[0] = (Dot(o1.m_axes[0], o2.m_axes[0]) > 0) ? 1 : -1;
00258         data.v2[1] = 0;
00259         data.p2[0] = -proj;
00260         data.p2[1] = 0;
00261 
00262         return 1;
00263       }
00264 
00265       if(!o1.m_axes[1].isValid()) {
00266         data.p2[0] = -Dot(off, o2.m_axes[0]);
00267         data.p2[1] = -Dot(off, o2.m_axes[1]);
00268 
00269         if(off != - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
00270           return -1;
00271 
00272         data.v1[0] = 1;
00273         data.v1[1] = 0;
00274         data.p1[0] = data.p1[1] = 0;
00275         data.v2[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
00276         data.v2[1] = Dot(o1.m_axes[0], o2.m_axes[1]);
00277 
00278         return 1;
00279       }
00280 
00281       if(!o2.m_axes[1].isValid()) {
00282         data.p1[0] = Dot(off, o1.m_axes[0]);
00283         data.p1[1] = Dot(off, o1.m_axes[1]);
00284 
00285         if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1])
00286           return -1;
00287 
00288         data.v2[0] = 1;
00289         data.v2[1] = 0;
00290         data.p2[0] = data.p2[1] = 0;
00291         data.v1[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
00292         data.v1[1] = Dot(o1.m_axes[1], o2.m_axes[0]);
00293 
00294         return 1;
00295       }
00296 
00297       data.p1[0] = Dot(off, o1.m_axes[0]);
00298       data.p1[1] = Dot(off, o1.m_axes[1]);
00299       data.p2[0] = -Dot(off, o2.m_axes[0]);
00300       data.p2[1] = -Dot(off, o2.m_axes[1]);
00301 
00302       if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1]
00303         - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
00304         return -1;
00305 
00306       basis1 /= std::sqrt(sqrmag1);
00307 
00308       data.v1[0] = Dot(o1.m_axes[0], basis1);
00309       data.v1[1] = Dot(o1.m_axes[1], basis1);
00310       data.v2[0] = Dot(o2.m_axes[0], basis1);
00311       data.v2[1] = Dot(o2.m_axes[1], basis1);
00312 
00313       return 1;
00314       }
00315     case 2:
00316       {
00317       assert(o1.m_axes[1].isValid() && o2.m_axes[1].isValid());
00318 
00319       // The planes are parallel, check if they are the same plane
00320       CoordType off_sqr_mag = data.off.sqrMag();
00321 
00322       // Find the offset between the origins in o2's coordnates
00323 
00324       if(off_sqr_mag != 0) { // The offsets aren't identical
00325         Vector<dim> off_copy = off;
00326 
00327         data.off[0] = Dot(o2.m_axes[0], off);
00328         off_copy -= o1.m_axes[0] * data.off[0];
00329         data.off[1] = Dot(o2.m_axes[1], off);
00330         off_copy -= o1.m_axes[1] * data.off[1];
00331 
00332         if(off_copy.sqrMag() > off_sqr_mag * numeric_constants<CoordType>::epsilon())
00333           return -1; // The planes are different
00334       }
00335       else
00336         data.off[0] = data.off[1] = 0;
00337 
00338       // Define o2's basis vectors in o1's coordinates
00339       data.v1[0] = Dot(o2.m_axes[0], o1.m_axes[0]);
00340       data.v1[1] = Dot(o2.m_axes[0], o1.m_axes[1]);
00341       data.v2[0] = Dot(o2.m_axes[1], o1.m_axes[0]);
00342       data.v2[1] = Dot(o2.m_axes[1], o1.m_axes[1]);
00343 
00344       return 2;
00345       }
00346     default:
00347       assert(false);
00348       return -1;
00349   }
00350 }
00351 
00352 template<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<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(size_t 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<int dim>
00380 bool Intersect(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00381 {
00382   size_t 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(size_t 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<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 || std::fabs(size[nonzero_dim]) < std::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<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<int dim>
00470 inline bool Contains(const AxisBox<dim>& b, const Polygon<dim>& p, bool proper)
00471 {
00472   for(size_t 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<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, std::sqrt(dist)), proper);
00494 }
00495 
00496 template<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<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(size_t 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<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<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<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<int dim>
00599 bool Intersect(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00600 {
00601   size_t 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(size_t 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<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<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(size_t 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<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<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