00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
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());
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
00087 p2[0] = p2[1] = 0;
00088 return Intersect(b, convert(p2), proper);
00089 }
00090
00091 if(m_axes[1].isValid()) {
00092
00093
00094
00095
00096
00097 return checkIntersectPlane(b, p2, proper);
00098 }
00099
00100
00101
00102
00103
00104 CoordType min = 0, max = 0;
00105 bool got_bounds = false;
00106
00107 for(int i = 0; i < dim; ++i) {
00108 const CoordType dist = (m_axes[0])[i];
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);
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()) {
00152 return -1;
00153 }
00154
00155
00156
00157 if(!o1.m_axes[0].isValid()) {
00158 if(!o2.checkContained(o1.m_origin, data.p2))
00159 return -1;
00160
00161 _Poly2OrientIntersectData data;
00162
00163 data.p1[0] = data.p1[1] = 0;
00164
00165 return 0;
00166 }
00167
00168 if(!o2.m_axes[0].isValid()) {
00169 if(!o1.checkContained(o2.m_origin, data.p1))
00170 return -1;
00171
00172 data.p2[0] = data.p2[1] = 0;
00173
00174 return 0;
00175 }
00176
00177
00178
00179
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
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
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
00218
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)
00239 return -1;
00240 else
00241 return 1;
00242 }
00243 case 1:
00244 {
00245
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
00321 CoordType off_sqr_mag = data.off.sqrMag();
00322
00323
00324
00325 if(off_sqr_mag != 0) {
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;
00335 }
00336 else
00337 data.off[0] = data.off[1] = 0;
00338
00339
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 return -1;
00350 }
00351 }
00352
00353 template<const int dim>
00354 inline bool Intersect(const Polygon<dim>& r, const Point<dim>& p, bool proper)
00355 {
00356 Point<2> p2;
00357
00358 return r.m_poly.numCorners() > 0 && r.m_orient.checkContained(p, p2)
00359 && Intersect(r.m_poly, p2, proper);
00360 }
00361
00362 template<const int dim>
00363 inline bool Contains(const Point<dim>& p, const Polygon<dim>& r, bool proper)
00364 {
00365 if(r.m_poly.numCorners() == 0)
00366 return true;
00367
00368 if(proper)
00369 return false;
00370
00371 for(int i = 1; i < r.m_poly.numCorners(); ++i)
00372 if(r.m_poly[i] != r.m_poly[0])
00373 return false;
00374
00375 Point<2> p2;
00376
00377 return r.m_orient.checkContained(p, p2) && p2 == r.m_poly[0];
00378 }
00379
00380 template<const int dim>
00381 bool Intersect(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00382 {
00383 int corners = p.m_poly.numCorners();
00384
00385 if(corners == 0)
00386 return false;
00387
00388 Point<2> p2;
00389
00390 if(!p.m_orient.checkIntersect(b, p2, proper))
00391 return false;
00392
00393 Segment<dim> s;
00394 s.endpoint(0) = p.m_orient.convert(p.m_poly.getCorner(corners-1));
00395 int next_end = 1;
00396
00397 for(int i = 0; i < corners; ++i) {
00398 s.endpoint(next_end) = p.m_orient.convert(p.m_poly.getCorner(i));
00399 if(Intersect(b, s, proper))
00400 return true;
00401 next_end = next_end ? 0 : 1;
00402 }
00403
00404 return Contains(p, p2, proper);
00405 }
00406
00407 template<const int dim>
00408 bool _PolyContainsBox(const _Poly2Orient<dim> &orient, const Polygon<2> &poly,
00409 const Point<dim> &corner, const Vector<dim> &size, bool proper)
00410 {
00411 int num_dim = 0, nonzero_dim = -1;
00412
00413 for(int i = 0; i < dim; ++i) {
00414 if(size[i] == 0)
00415 continue;
00416 if(num_dim == 2)
00417 return false;
00418 if(nonzero_dim == -1 || fabs(size[nonzero_dim]) < fabs(size[i]));
00419 nonzero_dim = i;
00420 ++num_dim;
00421 }
00422
00423 Point<2> corner1;
00424
00425 if(!orient.checkContained(corner, corner1))
00426 return false;
00427
00428 if(num_dim == 0)
00429 return Contains(poly, corner1, proper);
00430
00431 Point<2> corner2;
00432
00433 if(!orient.checkContained(corner + size, corner2))
00434 return false;
00435
00436 if(num_dim == 1)
00437 return Contains(poly, Segment<2>(corner1, corner2), proper);
00438
00439 Point<dim> other_corner = corner;
00440 other_corner[nonzero_dim] += size[nonzero_dim];
00441
00442 Point<2> corner3;
00443 if(!orient.checkContained(other_corner, corner3))
00444 return false;
00445
00446
00447
00448 Vector<2> vec1(corner2 - corner1), vec2(corner3 - corner1);
00449
00450 RotMatrix<2> m;
00451
00452 try {
00453 m.rotation(Vector<2>(1, 0), vec1);
00454 }
00455 catch(ColinearVectors<2>) {
00456 m.identity();
00457 }
00458
00459 RotBox<2> box(corner1, ProdInv(vec2, m), m);
00460
00461 return Contains(poly, box, proper);
00462 }
00463
00464 template<const int dim>
00465 inline bool Contains(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
00466 {
00467 return _PolyContainsBox(p.m_orient, p.m_poly, b.m_low, b.m_high - b.m_low, proper);
00468 }
00469
00470 template<const int dim>
00471 inline bool Contains(const AxisBox<dim>& b, const Polygon<dim>& p, bool proper)
00472 {
00473 for(int i = 0; i < p.m_poly.numCorners(); ++i)
00474 if(!Contains(b, p.getCorner(i), proper))
00475 return false;
00476
00477 return true;
00478 }
00479
00480 template<const int dim>
00481 inline bool Intersect(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00482 {
00483 if(p.m_poly.numCorners() == 0)
00484 return false;
00485
00486 Point<2> c2;
00487 CoordType dist;
00488
00489 dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00490
00491 if(_Less(dist, 0, proper))
00492 return false;
00493
00494 return Intersect(p.m_poly, Ball<2>(c2, sqrt(dist)), proper);
00495 }
00496
00497 template<const int dim>
00498 inline bool Contains(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
00499 {
00500 if(p.m_poly.numCorners() == 0)
00501 return false;
00502
00503 if(b.m_radius > 0)
00504 return false;
00505
00506 Point<2> c2;
00507
00508 if(!p.m_orient.checkContained(b.m_center, c2))
00509 return false;
00510
00511 return Contains(p.m_poly, c2, proper);
00512 }
00513
00514 template<const int dim>
00515 inline bool Contains(const Ball<dim>& b, const Polygon<dim>& p, bool proper)
00516 {
00517 if(p.m_poly.numCorners() == 0)
00518 return true;
00519
00520 Point<2> c2;
00521 CoordType dist;
00522
00523 dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
00524
00525 if(_Less(dist, 0, proper))
00526 return false;
00527
00528 for(int i = 0; i != p.m_poly.numCorners(); ++i)
00529 if(_Less(dist, SquaredDistance(c2, p.m_poly[i]), proper))
00530 return false;
00531
00532 return true;
00533 }
00534
00535 template<const int dim>
00536 bool Intersect(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00537 {
00538 if(p.m_poly.numCorners() == 0)
00539 return false;
00540
00541 Point<2> p1, p2;
00542 CoordType d1, d2;
00543 Vector<dim> v1, v2;
00544
00545 v1 = p.m_orient.offset(s.m_p1, p1);
00546 v2 = p.m_orient.offset(s.m_p2, p2);
00547
00548 if(Dot(v1, v2) > 0)
00549 return false;
00550
00551 d1 = v1.mag();
00552 d2 = v2.mag();
00553 Point<2> p_intersect;
00554
00555 if(d1 + d2 == 0)
00556 return Intersect(p.m_poly, Segment<2>(p1, p2), proper);
00557
00558 for(int i = 0; i < 2; ++i)
00559 p_intersect[i] = (p1[i] * d2 + p2[i] * d1) / (d1 + d2);
00560
00561 return Intersect(p.m_poly, p_intersect, proper);
00562 }
00563
00564 template<const int dim>
00565 inline bool Contains(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
00566 {
00567 if(p.m_poly.numCorners() == 0)
00568 return false;
00569
00570 Segment<2> s2;
00571
00572 if(!p.m_orient.checkContained(s.m_p1, s2.endpoint(0)))
00573 return false;
00574 if(!p.m_orient.checkContained(s.m_p2, s2.endpoint(1)))
00575 return false;
00576
00577 return Contains(p.m_poly, s2, proper);
00578 }
00579
00580 template<const int dim>
00581 inline bool Contains(const Segment<dim>& s, const Polygon<dim>& p, bool proper)
00582 {
00583 if(p.m_poly.numCorners() == 0)
00584 return true;
00585
00586
00587
00588
00589 Segment<2> s2;
00590 _Poly2Orient<dim> orient(p.m_orient);
00591
00592 for(int i = 0; i < 2; ++i)
00593 if(!orient.expand(s.endpoint(i), s2.endpoint(i)))
00594 return false;
00595
00596 return Contains(s2, p.m_poly, proper);
00597 }
00598
00599 template<const int dim>
00600 bool Intersect(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00601 {
00602 int corners = p.m_poly.numCorners();
00603
00604 if(corners == 0)
00605 return false;
00606
00607 _Poly2Orient<dim> orient(p.m_orient);
00608
00609 orient.rotate(r.m_orient.inverse(), r.m_corner0);
00610
00611 AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00612
00613 Point<2> p2;
00614
00615 if(!orient.checkIntersect(b, p2, proper))
00616 return false;
00617
00618 Segment<dim> s;
00619 s.endpoint(0) = orient.convert(p.m_poly.getCorner(corners-1));
00620 int next_end = 1;
00621
00622 for(int i = 0; i < corners; ++i) {
00623 s.endpoint(next_end) = orient.convert(p.m_poly.getCorner(i));
00624 if(Intersect(b, s, proper))
00625 return true;
00626 next_end = next_end ? 0 : 1;
00627 }
00628
00629 return Contains(p, p2, proper);
00630 }
00631
00632 template<const int dim>
00633 inline bool Contains(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
00634 {
00635 _Poly2Orient<dim> orient(p.m_orient);
00636 orient.rotate(r.m_orient.inverse(), r.m_corner0);
00637
00638 return _PolyContainsBox(orient, p.m_poly, r.m_corner0, r.m_size, proper);
00639 }
00640
00641 template<const int dim>
00642 inline bool Contains(const RotBox<dim>& r, const Polygon<dim>& p, bool proper)
00643 {
00644 if(p.m_poly.numCorners() == 0)
00645 return true;
00646
00647 AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
00648
00649 _Poly2Orient<dim> orient(p.m_orient);
00650 orient.rotate(r.m_orient.inverse(), r.m_corner0);
00651
00652 for(int i = 0; i < p.m_poly.numCorners(); ++i)
00653 if(!Contains(b, orient.convert(p.m_poly[i]), proper))
00654 return false;
00655
00656 return true;
00657 }
00658
00659 bool _PolyPolyIntersect(const Polygon<2> &poly1, const Polygon<2> &poly2,
00660 const int intersect_dim,
00661 const _Poly2OrientIntersectData &data, bool proper);
00662
00663 template<const int dim>
00664 inline bool Intersect(const Polygon<dim>& p1, const Polygon<dim>& p2, bool proper)
00665 {
00666 _Poly2OrientIntersectData data;
00667
00668 int intersect_dim = _Intersect(p1.m_orient, p2.m_orient, data);
00669
00670 return _PolyPolyIntersect(p1.m_poly, p2.m_poly, intersect_dim, data, proper);
00671 }
00672
00673 bool _PolyPolyContains(const Polygon<2> &outer, const Polygon<2> &inner,
00674 const int intersect_dim,
00675 const _Poly2OrientIntersectData &data, bool proper);
00676
00677 template<const int dim>
00678 inline bool Contains(const Polygon<dim>& outer, const Polygon<dim>& inner, bool proper)
00679 {
00680 if(outer.m_poly.numCorners() == 0)
00681 return !proper && inner.m_poly.numCorners() == 0;
00682
00683 if(inner.m_poly.numCorners() == 0)
00684 return true;
00685
00686 _Poly2OrientIntersectData data;
00687
00688 int intersect_dim = _Intersect(outer.m_orient, inner.m_orient, data);
00689
00690 return _PolyPolyContains(outer.m_poly, inner.m_poly, intersect_dim, data, proper);
00691 }
00692
00693 template<>
00694 bool Intersect(const Polygon<2>& r, const Point<2>& p, bool proper);
00695 template<>
00696 bool Contains(const Point<2>& p, const Polygon<2>& r, bool proper);
00697
00698 template<>
00699 bool Intersect(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00700 template<>
00701 bool Contains(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
00702 template<>
00703 bool Contains(const AxisBox<2>& b, const Polygon<2>& p, bool proper);
00704
00705 template<>
00706 bool Intersect(const Polygon<2>& p, const Ball<2>& b, bool proper);
00707 template<>
00708 bool Contains(const Polygon<2>& p, const Ball<2>& b, bool proper);
00709 template<>
00710 bool Contains(const Ball<2>& b, const Polygon<2>& p, bool proper);
00711
00712 template<>
00713 bool Intersect(const Polygon<2>& r, const Segment<2>& s, bool proper);
00714 template<>
00715 bool Contains(const Polygon<2>& p, const Segment<2>& s, bool proper);
00716 template<>
00717 bool Contains(const Segment<2>& s, const Polygon<2>& p, bool proper);
00718
00719 template<>
00720 bool Intersect(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00721 template<>
00722 bool Contains(const Polygon<2>& p, const RotBox<2>& r, bool proper);
00723 template<>
00724 bool Contains(const RotBox<2>& r, const Polygon<2>& p, bool proper);
00725
00726 template<>
00727 bool Intersect(const Polygon<2>& p1, const Polygon<2>& p2, bool proper);
00728 template<>
00729 bool Contains(const Polygon<2>& outer, const Polygon<2>& inner, bool proper);
00730
00731 }
00732
00733 #endif // WFMATH_POLYGON_INTERSECT_H