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

Generated on Tue Jul 27 21:41:56 2004 for WFMath by doxygen 1.3.7