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

Generated on Thu Jul 29 07:09:56 2004 for WFMath by doxygen 1.3.7