WFMath 0.3.12
|
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() < 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<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 > 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 /= 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 * 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 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(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<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<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<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(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<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(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<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 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<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(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<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