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 }
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
00446
00447 Vector<2> vec1(corner2 - corner1), vec2(corner3 - corner1);
00448
00449 RotMatrix<2> m;
00450
00451 try {
00452 m.rotation(Vector<2>(1, 0), vec1);
00453 }
00454 catch(ColinearVectors<2>) {
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)
00548 return false;
00549
00550 d1 = v1.mag();
00551 d2 = v2.mag();
00552 Point<2> p_intersect;
00553
00554 if(d1 + d2 == 0)
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
00586
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
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 }
00731
00732 #endif // WFMATH_POLYGON_INTERSECT_H