Main Page   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members  

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 
00037 #ifndef _MSC_VER
00038 #warning "The Intersect() and Contains() functions involving WFMath::Polygon<>"
00039 #warning "are still under development, and probably shouldn't be used yet."
00040 #else
00041 #pragma warning "The Intersect() and Contains() functions involving WFMath::Polygon<>"
00042 #pragma warning "are still under development, and probably shouldn't be used yet."
00043 #endif
00044 
00045 namespace WFMath {
00046 
00047 template<const int dim>
00048 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<const int dim>
00063 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() < WFMATH_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<const 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<const 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_basis[0] * Dot(o2.m_basis[0], o1.m_basis[0]);
00185   if(o2.m_axes[1].isValid())
00186     basis1 += o2.m_basis[1] * Dot(o2.m_basis[1], o1.m_basis[0]);
00187 
00188   // Don't need to scale, the m_basis are unit vectors
00189   sqrmag1 = basis1.sqrMag();
00190   if(sqrmag1 > WFMATH_EPSILON * WFMATH_EPSILON)
00191     basis_size = 1;
00192 
00193   if(o1.m_axes[1].isValid()) {
00194     basis2 = o2.m_basis[0] * Dot(o2.m_basis[0], o1.m_basis[1]);
00195     if(o2.m_axes[1].isValid())
00196       basis2 += o2.m_basis[1] * Dot(o2.m_basis[1], o1.m_basis[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 > WFMATH_EPSILON * WFMATH_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       // All vectors are orthogonal, check for a common point in the plane
00216       // This can happen even in 3d for degenerate bases
00217 
00218       data.p1[0] = Dot(o1.m_axes[0], off);
00219       Vector<dim> off1 = o1.m_axes[0] * data.p1[0];
00220       if(o1.m_axes[1].isValid()) {
00221         data.p1[1] = Dot(o1.m_axes[1], off);
00222         off1 += o1.m_axes[1] * data.p1[1];
00223       }
00224       else
00225         data.p1[1] = 0;
00226 
00227       data.p2[0] = -Dot(o2.m_axes[0], off);
00228       Vector<dim> off2 = o2.m_axes[0] * data.p2[0];
00229       if(o1.m_axes[1].isValid()) {
00230         data.p2[1] = -Dot(o2.m_axes[1], off);
00231         off2 += o1.m_axes[1] * data.p2[1];
00232       }
00233       else
00234         data.p2[1] = 0;
00235 
00236       if(off1 - off2 != off) // No common point
00237         return -1;
00238       else  // Got a point
00239         return 1;
00240     case 1:
00241       // Check for an intersection line
00242 
00243       data.o1_is_line = !o1.m_axes[1].isValid();
00244       data.o2_is_line = !o2.m_axes[1].isValid();
00245 
00246       if(!o1.m_axes[1].isValid() && !o2.m_axes[1].isValid()) {
00247         CoordType proj2 = Dot(off, data.v2);
00248         if(off != data.v2 * proj)
00249           return -1;
00250 
00251         data.v1[0] = 1;
00252         data.v1[1] = 0;
00253         data.p1[0] = data.p1[1] = 0;
00254         data.v2[0] = (Dot(o1.m_axes[0], o2.m_axes[0]) > 0) ? 1 : -1;
00255         data.v2[1] = 0;
00256         data.p2[0] = -proj;
00257         data.p2[1] = 0;
00258 
00259         return 1;
00260       }
00261 
00262       if(!o1.m_axes[1].isValid()) {
00263         data.p2[0] = -Dot(off, o2.m_axes[0]);
00264         data.p2[1] = -Dot(off, o2.m_axes[1]);
00265 
00266         if(off != - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
00267           return -1;
00268 
00269         data.v1[0] = 1;
00270         data.v1[1] = 0;
00271         data.p1[0] = data.p1[1] = 0;
00272         data.v2[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
00273         data.v2[1] = Dot(o1.m_axes[0], o2.m_axes[1]);
00274 
00275         return 1;
00276       }
00277 
00278       if(!o2.m_axes[1].isValid()) {
00279         data.p1[0] = Dot(off, o1.m_axes[0]);
00280         data.p1[1] = Dot(off, o1.m_axes[1]);
00281 
00282         if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1])
00283           return -1;
00284 
00285         data.v2[0] = 1;
00286         data.v2[1] = 0;
00287         data.p2[0] = data.p2[1] = 0;
00288         data.v1[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
00289         data.v1[1] = Dot(o1.m_axes[1], o2.m_axes[0]);
00290 
00291         return 1;
00292       }
00293 
00294       data.p1[0] = Dot(off, o1.m_axes[0]);
00295       data.p1[1] = Dot(off, o1.m_axes[1]);
00296       data.p2[0] = -Dot(off, o2.m_axes[0]);
00297       data.p2[1] = -Dot(off, o2.m_axes[1]);
00298 
00299       if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1]
00300         - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
00301         return -1;
00302 
00303       basis1 /= sqrt(sqrmag1);
00304 
00305       data.v1[0] = Dot(o1.m_axes[0], basis1);
00306       data.v1[1] = Dot(o1.m_axes[1], basis1);
00307       data.v2[0] = Dot(o2.m_axes[0], basis1);
00308       data.v2[1] = Dot(o2.m_axes[1], basis1);
00309 
00310       return 1;
00311     case 2:
00312       assert(o1.m_axes[1].isValid() && o2.m_axes[1].isValid());
00313 
00314       // The planes are parallel, check if they are the same plane
00315       CoordType off_sqr_mag = data.off.sqrMag();
00316 
00317       // Find the offset between the origins in o2's coordnates
00318 
00319       if(off_sqr_mag != 0) { // The offsets aren't identical
00320         Vector<dim> off_copy = off;
00321 
00322         data.off[0] = Dot(o2.m_axes[0], off);
00323         off_copy -= o1.m_axes[0] * data.off[0];
00324         data.off[1] = Dot(o2.m_axes[1], off);
00325         off_copy -= o1.m_axes[1] * data.off[1];
00326 
00327         if(off_copy.sqrMag() > off_sqr_mag * WFMATH_EPSILON)
00328           return -1; // The planes are different
00329       }
00330       else
00331         data.off[0] = data.off[1] = 0;
00332 
00333       // Define o2's basis vectors in o1's coordinates
00334       data.v1[0] = Dot(o2.m_axes[0], o1.m_axes[0]);
00335       data.v1[1] = Dot(o2.m_axes[0], o1.m_axes[1]);
00336       data.v2[0] = Dot(o2.m_axes[1], o1.m_axes[0]);
00337       data.v2[1] = Dot(o2.m_axes[1], o1.m_axes[1]);
00338 
00339       return 2;
00340     default:
00341       assert(false);
00342   }
00343 }
00344 
00345 template<const int dim>
00346 bool Intersect(const Polygon<dim>& r, const Point<dim>& p, bool proper)
00347 {
00348   Point<2> p2;
00349 
00350   return m_poly.numCorners() > 0 && m_orient.checkContained(p, p2)
00351          && Intersect(m_poly, p2, proper);
00352 }
00353 
00354 template<const int dim>
00355 bool Contains(const Point<dim>& p, const Polygon<dim>& r, bool proper)
00356 {
00357   if(r.m_poly.numCorners() == 0)
00358     return true;
00359 
00360   if(proper)
00361     return false;
00362 
00363   for(int i = 1; i < m_poly.numCorners(); ++i)
00364     if(m_poly[i] != m_poly[0])
00365       return false;
00366 
00367   Point<2> p2;
00368 
00369   return m_orient.checkContained(p, p2) && p2 = m_poly[0];
00370 }
00371 
00372 template<const int dim>
00373 bool Intersect(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00374 {
00375   int corners = p.m_poly.numCorners();
00376 
00377   if(corners == 0)
00378     return false;
00379 
00380   Point<2> p2;
00381 
00382   if(!p.m_orient.checkIntersect(b, p2, proper))
00383     return false;
00384 
00385   Segment<dim> s;
00386   s.endpoint(0) = p.m_orient.convert(p.m_poly.getCorner(corners-1));
00387   int next_end = 1;
00388 
00389   for(int i = 0; i < corners; ++i) {
00390     s.endpoint(next_end) = p.m_orient.convert(p.m_poly.getCorner(i));
00391     if(Intersect(b, s, proper))
00392       return true;
00393     next_end = next_end ? 0 : 1;
00394   }
00395 
00396   return Contains(p, p2, proper);
00397 }
00398 
00399 template<const int dim>
00400 bool _PolyContainsBox(const _Poly2Orient<dim> &orient, const Polygon<2> &poly,
00401                   const Point<dim> &corner, const Vector<dim> &size, bool proper)
00402 {
00403   int num_dim = 0, nonzero_dim = -1;
00404 
00405   for(int i = 0; i < dim; ++i) {
00406     if(size[i] == 0)
00407       continue;
00408     if(num_dim == 2)
00409       return false;
00410     if(nonzero_dim == -1 || fabs(size[nonzero_dim]) < fabs(size[i]));
00411       nonzero_dim = i;
00412     ++num_dim;
00413   }
00414 
00415   Point<2> corner1;
00416 
00417   if(!orient.checkContained(corner, corner1))
00418     return false;
00419 
00420   if(num_dim == 0)
00421     return Contains(poly, corner1);
00422 
00423   Point<2> corner2;
00424 
00425   if(!orient.checkContained(corner + size, corner2))
00426     return false;
00427 
00428   if(num_dim == 1)
00429     return Contains(poly, Segment<2>(corner1, corner2));
00430 
00431   Point<dim> other_corner = corner;
00432   other_corner[nonzero_dim] += size[nonzero_dim];
00433 
00434   Point<2> corner3;
00435   if(!orient.checkContained(other_corner, corner3))
00436     return false;
00437 
00438   // Create a RotBox<2>
00439 
00440   Vector<2> vec1(corner2 - corner1), vec2(corner3 - corner1);
00441 
00442   RotMatrix<2> m; // A matrix which gives the rotation from the x-axis to vec1
00443 
00444   try {
00445     m.rotation(Vector<2>(1, 0), vec1);
00446   }
00447   catch(ColinearVectors<2>) { // vec1 is parallel to (-1, 0), so we're fine
00448     m.identity();
00449   }
00450 
00451   RotBox<2> box(corner1, ProdInv(vec2, m), m);
00452 
00453   return Contains(poly, box);
00454 }
00455 
00456 template<const int dim>
00457 bool Contains(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00458 {
00459   return _PolyContainsBox(p.m_orient, p.m_poly, b.m_low, b.m_high - b.m_low, proper);
00460 }
00461 
00462 template<const int dim>
00463 bool Contains(const AxisBox<dim>& b, const Polygon<dim>& p, bool proper)
00464 {
00465   for(int i = 0; i < p.m_poly.numCorners(); ++i)
00466     if(!Contains(b, p.getCorner(i), proper))
00467       return false;
00468 
00469   return true;
00470 }
00471 
00472 template<const int dim>
00473 bool Intersect(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00474 {
00475   if(p.m_poly.numCorners() == 0)
00476     return false;
00477 
00478   Point<2> c2;
00479   CoordType dist;
00480 
00481   dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00482 
00483   if(_Less(dist, 0, proper))
00484     return false;
00485 
00486   return Intersect(p.m_poly, Ball<2>(c2, sqrt(dist)), proper);
00487 }
00488 
00489 template<const int dim>
00490 bool Contains(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00491 {
00492   if(p.m_poly.numCorners() == 0)
00493     return false;
00494 
00495   if(b.m_radius > 0)
00496     return false;
00497 
00498   Point<2> c2;
00499 
00500   if(!p.m_orient.checkContained(b.m_center, c2))
00501     return false;
00502 
00503   return Contains(p.m_poly, c2, proper);
00504 }
00505 
00506 template<const int dim>
00507 bool Contains(const Ball<dim>& b, const Polygon<dim>& p, bool proper)
00508 {
00509   if(p.m_poly.numCorners() == 0)
00510     return true;
00511 
00512   Point<2> c2;
00513   CoordType dist;
00514 
00515   dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00516 
00517   if(_Less(dist, 0, proper))
00518     return false;
00519 
00520   for(int i = 0; i != p.m_poly.numCorners(); ++i)
00521     if(_Less(dist, SquaredDistance(c2, p.m_poly[i]), proper))
00522       return false;
00523 
00524   return true;
00525 }
00526 
00527 template<const int dim>
00528 bool Intersect(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00529 {
00530   if(p.m_poly.numCorners() == 0)
00531     return false;
00532 
00533   Point<2> p1, p2;
00534   CoordType d1, d2;
00535   Vector<dim> v1, v2;
00536 
00537   v1 = p.m_orient.offset(s.m_p1, p1);
00538   v2 = p.m_orient.offset(s.m_p2, p2);
00539 
00540   if(Dot(v1, v2) > 0) // Both points on same side of sheet
00541     return false;
00542 
00543   d1 = v1.mag();
00544   d2 = v2.mag();
00545   Point<2> p_intersect;
00546 
00547   if(d1 + d2 == 0) // Avoid divide by zero later
00548     return Intersect(p.m_poly, Segment<2>(p1, p2), proper);
00549 
00550   for(int i = 0; i < 2; ++i)
00551     p_intersect[i] = (p1[i] * d2 + p2[i] * d1) / (d1 + d2);
00552 
00553   return Intersect(p.m_poly, p_intersect, proper);
00554 }
00555 
00556 template<const int dim>
00557 bool Contains(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00558 {
00559   if(p.m_poly.numCorners() == 0)
00560     return false;
00561 
00562   Segment<2> s2;
00563 
00564   if(!p.m_orient.checkContained(s.m_p1, s2.endpoint(0)))
00565     return false;
00566   if(!p.m_orient.checkContained(s.m_p2, s2.endpoint(1)))
00567     return false;
00568 
00569   return Contains(p.m_poly, Segment<2>(p1, p2), proper);
00570 }
00571 
00572 template<const int dim>
00573 bool Contains(const Segment<dim>& s, const Polygon<dim>& p, bool proper)
00574 {
00575   if(p.m_poly.numCorners() == 0)
00576     return true;
00577 
00578   // Expand the basis to include the segment, this deals well with
00579   // degenerate polygons
00580 
00581   Segment<2> s2;
00582   _Poly2Orient<dim> orient(p.m_orient);
00583 
00584   for(int i = 0; i < 2; ++i)
00585     if(!orient.expand(s.endpoint(i), s2.endpoint(i)))
00586       return false;
00587 
00588   return Contains(s2, p.m_poly, proper);
00589 }
00590 
00591 template<const int dim>
00592 bool Intersect(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00593 {
00594   int corners = p.m_poly.numCorners();
00595 
00596   if(corners == 0)
00597     return false;
00598 
00599   _Poly2Orient<dim> orient(p.m_orient);
00600   // FIXME rotateInverse()
00601   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00602 
00603   AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00604 
00605   Point<2> p2;
00606 
00607   if(!orient.checkIntersect(b, p2, proper))
00608     return false;
00609 
00610   Segment<dim> s;
00611   s.endpoint(0) = orient.convert(p.m_poly.getCorner(corners-1));
00612   int next_end = 1;
00613 
00614   for(int i = 0; i < corners; ++i) {
00615     s.endpoint(next_end) = orient.convert(p.m_poly.getCorner(i));
00616     if(Intersect(b, s, proper))
00617       return true;
00618     next_end = next_end ? 0 : 1;
00619   }
00620 
00621   return Contains(p, p2, proper);
00622 }
00623 
00624 template<const int dim>
00625 bool Contains(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00626 {
00627   _Poly2Orient<dim> orient(p.m_orient);
00628   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00629 
00630   return _PolyContainsBox(orient, p.m_poly, r.m_corner0, r.m_size, proper);
00631 }
00632 
00633 template<const int dim>
00634 bool Contains(const RotBox<dim>& r, const Polygon<dim>& p)
00635 {
00636   if(p.m_poly.numCorners() == 0)
00637     return true;
00638 
00639   AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00640 
00641   _Poly2Orient<dim> orient(p.m_orient);
00642   orient.rotate(r.m_orient.inverse(), r.m_corner0);
00643 
00644   for(int i = 0; i < p.m_poly.numCorners(); ++i)
00645     if(!Contains(b, orient.convert(p.m_poly[i]), proper))
00646       return false;
00647 
00648   return true;
00649 }
00650 
00651 bool _PolyPolyIntersect(const Polygon<2> &poly1, const Polygon<2> &poly2,
00652                         const int intersect_dim,
00653                         const _Poly2OrientIntersectData &data, bool proper);
00654 
00655 template<const int dim>
00656 bool Intersect(const Polygon<dim>& p1, const Polygon<dim>& p2, bool proper)
00657 {
00658   _Poly2OrientIntersectData data;
00659 
00660   int intersect_dim = _Intersect(p1.m_orient, p2.m_orient, data);
00661 
00662   return _PolyPolyIntersect(p1.m_poly, p2.m_poly, intersect_dim, data, proper);
00663 }
00664 
00665 bool _PolyPolyContains(const Polygon<2> &outer, const Polygon<2> &inner,
00666                        const int intersect_dim,
00667                        const _Poly2OrientIntersectData &data, bool proper);
00668 
00669 template<const int dim>
00670 bool Contains(const Polygon<dim>& outer, const Polygon<dim>& inner, bool proper)
00671 {
00672   if(outer.m_poly.numCorners == 0)
00673     return !proper && inner.m_poly.numCorners() == 0;
00674 
00675   if(inner.m_poly.numCorners() == 0)
00676     return true;
00677 
00678   _Poly2OrientIntersectData data;
00679 
00680   int intersect_dim = _Intersect(outer.m_orient, inner.m_orient, data);
00681 
00682   return _PolyPolyContains(outer.m_poly, inner.m_poly, intersect_dim, data, proper);
00683 }
00684 
00685 template<>
00686 bool Intersect(const Polygon<2>& r, const Point<2>& p, bool proper);
00687 template<>
00688 bool Contains(const Point<2>& p, const Polygon<2>& r, bool proper);
00689 
00690 template<>
00691 bool Intersect(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00692 template<>
00693 bool Contains(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00694 template<>
00695 bool Contains(const AxisBox<2>& b, const Polygon<2>& p, bool proper);
00696 
00697 template<>
00698 bool Intersect(const Polygon<2>& p, const Ball<2>& b, bool proper);
00699 template<>
00700 bool Contains(const Polygon<2>& p, const Ball<2>& b, bool proper);
00701 template<>
00702 bool Contains(const Ball<2>& b, const Polygon<2>& p, bool proper);
00703 
00704 template<>
00705 bool Intersect(const Polygon<2>& r, const Segment<2>& s, bool proper);
00706 template<>
00707 bool Contains(const Polygon<2>& p, const Segment<2>& s, bool proper);
00708 template<>
00709 bool Contains(const Segment<2>& s, const Polygon<2>& p, bool proper);
00710 
00711 template<>
00712 bool Intersect(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00713 template<>
00714 bool Contains(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00715 template<>
00716 bool Contains(const RotBox<2>& r, const Polygon<2>& p, bool proper);
00717 
00718 template<>
00719 bool Intersect(const Polygon<2>& p1, const Polygon<2>& p2, bool proper);
00720 template<>
00721 bool Contains(const Polygon<2>& outer, const Polygon<2>& inner, bool proper);
00722 
00723 } // namespace WFMath
00724 
00725 #endif  // WFMATH_POLYGON_INTERSECT_H

Generated on Wed May 28 09:20:32 2003 for WFMath by doxygen1.3-rc3