1 // polygon_funcs.h (Polygon<> intersection functions)
2 //
3 // The WorldForge Project
4 // Copyright (C) 2002 The WorldForge Project
5 //
6 // This program is free software; you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 2 of the License, or
9 // (at your option) any later version.
10 //
11 // This program is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program; if not, write to the Free Software
18 // Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19 //
20 // For information about WorldForge and its authors, please contact
21 // the Worldforge Web Site at http://www.worldforge.org.
22 //
23
24 // Author: Ron Steinke
25 // Created: 2002-2-20
26
27 #ifndef WFMATH_POLYGON_INTERSECT_H
28 #define WFMATH_POLYGON_INTERSECT_H
29
30 #include <wfmath/axisbox.h>
31 #include <wfmath/ball.h>
32 #include <wfmath/polygon.h>
33 #include <wfmath/intersect.h>
34 #include <wfmath/error.h>
35
36 #include <cmath>
37
38 #include <cassert>
39
40 // FIXME Work is needed on this code. At very least the following notes
41 // from the original author apply:
42 // "The Intersect() and Contains() functions involving WFMath::Polygon<>"
43 // "are still under development, and probably shouldn't be used yet."
44
45 namespace WFMath {
46
47 template<int dim>
offset(const Point<dim> & pd,Point<2> & p2)48 inline Vector<dim> _Poly2Orient<dim>::offset(const Point<dim>& pd, Point<2>& p2) const
49 {
50 assert(m_origin.isValid()); // Check for empty polygon before calling this
51
52 Vector<dim> out = pd - m_origin;
53
54 for(int j = 0; j < 2; ++j) {
55 p2[j] = Dot(out, m_axes[j]);
56 out -= p2[j] * m_axes[j];
57 }
58
59 return out;
60 }
61
62 template<int dim>
checkContained(const Point<dim> & pd,Point<2> & p2)63 inline bool _Poly2Orient<dim>::checkContained(const Point<dim>& pd, Point<2> & p2) const
64 {
65 Vector<dim> off = offset(pd, p2);
66
67 CoordType sqrsum = 0;
68 for(int i = 0; i < dim; ++i)
69 sqrsum += pd[i] * pd[i];
70
71 return off.sqrMag() < numeric_constants<CoordType>::epsilon() * sqrsum;
72 }
73
74 template<>
75 bool _Poly2Orient<3>::checkIntersectPlane(const AxisBox<3>& b, Point<2>& p2,
76 bool proper) const;
77
78 template<int dim>
checkIntersect(const AxisBox<dim> & b,Point<2> & p2,bool proper)79 bool _Poly2Orient<dim>::checkIntersect(const AxisBox<dim>& b, Point<2>& p2,
80 bool proper) const
81 {
82 assert(m_origin.isValid());
83
84 if(!m_axes[0].isValid()) {
85 // Single point
86 p2[0] = p2[1] = 0;
87 return Intersect(b, convert(p2), proper);
88 }
89
90 if(m_axes[1].isValid()) {
91 // A plane
92
93 // I only know how to do this in 3D, so write a function which will
94 // specialize to different dimensions
95
96 return checkIntersectPlane(b, p2, proper);
97 }
98
99 // A line
100
101 // This is a modified version of AxisBox<>/Segment<> intersection
102
103 CoordType min = 0, max = 0; // Initialize to avoid compiler warnings
104 bool got_bounds = false;
105
106 for(int i = 0; i < dim; ++i) {
107 const CoordType dist = (m_axes[0])[i]; // const may optimize away better
108 if(dist == 0) {
109 if(_Less(m_origin[i], b.lowCorner()[i], proper)
110 || _Greater(m_origin[i], b.highCorner()[i], proper))
111 return false;
112 }
113 else {
114 CoordType low = (b.lowCorner()[i] - m_origin[i]) / dist;
115 CoordType high = (b.highCorner()[i] - m_origin[i]) / dist;
116 if(low > high) {
117 CoordType tmp = high;
118 high = low;
119 low = tmp;
120 }
121 if(got_bounds) {
122 if(low > min)
123 min = low;
124 if(high < max)
125 max = high;
126 }
127 else {
128 min = low;
129 max = high;
130 got_bounds = true;
131 }
132 }
133 }
134
135 assert(got_bounds); // We can't be parallel in _all_ dimensions
136
137 if(_LessEq(min, max, proper)) {
138 p2[0] = (max - min) / 2;
139 p2[1] = 0;
140 return true;
141 }
142 else
143 return false;
144 }
145
146 template<int dim>
_Intersect(const _Poly2Orient<dim> & o1,const _Poly2Orient<dim> & o2,_Poly2OrientIntersectData & data)147 int _Intersect(const _Poly2Orient<dim> &o1, const _Poly2Orient<dim> &o2,
148 _Poly2OrientIntersectData &data)
149 {
150 if(!o1.m_origin.isValid() || !o2.m_origin.isValid()) { // No points
151 return -1;
152 }
153
154 // Check for single point basis
155
156 if(!o1.m_axes[0].isValid()) {
157 if(!o2.checkContained(o1.m_origin, data.p2))
158 return -1; // no intersect
159
160 _Poly2OrientIntersectData data;
161
162 data.p1[0] = data.p1[1] = 0;
163
164 return 0; // point intersect
165 }
166
167 if(!o2.m_axes[0].isValid()) {
168 if(!o1.checkContained(o2.m_origin, data.p1))
169 return -1; // no intersect
170
171 data.p2[0] = data.p2[1] = 0;
172
173 return 0; // point intersect
174 }
175
176 // Find a common basis for the plane's orientations
177 // by projecting out the part of o1's basis that lies
178 // in o2's basis
179
180 Vector<dim> basis1, basis2;
181 CoordType sqrmag1, sqrmag2;
182 int basis_size = 0;
183
184 basis1 = o2.m_axes[0] * Dot(o2.m_axes[0], o1.m_axes[0]);
185 if(o2.m_axes[1].isValid())
186 basis1 += o2.m_axes[1] * Dot(o2.m_axes[1], o1.m_axes[0]);
187
188 // Don't need to scale, the m_axes are unit vectors
189 sqrmag1 = basis1.sqrMag();
190 if(sqrmag1 > numeric_constants<CoordType>::epsilon() * numeric_constants<CoordType>::epsilon())
191 basis_size = 1;
192
193 if(o1.m_axes[1].isValid()) {
194 basis2 = o2.m_axes[0] * Dot(o2.m_axes[0], o1.m_axes[1]);
195 if(o2.m_axes[1].isValid())
196 basis2 += o2.m_axes[1] * Dot(o2.m_axes[1], o1.m_axes[1]);
197
198 // Project out part parallel to basis1
199 if(basis_size == 1)
200 basis2 -= basis1 * (Dot(basis1, basis2) / sqrmag1);
201
202 sqrmag2 = basis2.sqrMag();
203 if(sqrmag2 > numeric_constants<CoordType>::epsilon() * numeric_constants<CoordType>::epsilon()) {
204 if(basis_size++ == 0) {
205 basis1 = basis2;
206 sqrmag1 = sqrmag2;
207 }
208 }
209 }
210
211 Vector<dim> off = o2.m_origin - o1.m_origin;
212
213 switch(basis_size) {
214 case 0:
215 {
216 // All vectors are orthogonal, check for a common point in the plane
217 // This can happen even in 3d for degenerate bases
218
219 data.p1[0] = Dot(o1.m_axes[0], off);
220 Vector<dim> off1 = o1.m_axes[0] * data.p1[0];
221 if(o1.m_axes[1].isValid()) {
222 data.p1[1] = Dot(o1.m_axes[1], off);
223 off1 += o1.m_axes[1] * data.p1[1];
224 }
225 else
226 data.p1[1] = 0;
227
228 data.p2[0] = -Dot(o2.m_axes[0], off);
229 Vector<dim> off2 = o2.m_axes[0] * data.p2[0];
230 if(o1.m_axes[1].isValid()) {
231 data.p2[1] = -Dot(o2.m_axes[1], off);
232 off2 += o1.m_axes[1] * data.p2[1];
233 }
234 else
235 data.p2[1] = 0;
236
237 if(off1 - off2 != off) // No common point
238 return -1;
239 else // Got a point
240 return 1;
241 }
242 case 1:
243 {
244 // Check for an intersection line
245
246 data.o1_is_line = !o1.m_axes[1].isValid();
247 data.o2_is_line = !o2.m_axes[1].isValid();
248
249 if(!o1.m_axes[1].isValid() && !o2.m_axes[1].isValid()) {
250 CoordType proj = Dot(off, o2.m_axes[0]);
251 if(off != o2.m_axes[0] * proj)
252 return -1;
253
254 data.v1[0] = 1;
255 data.v1[1] = 0;
256 data.p1[0] = data.p1[1] = 0;
257 data.v2[0] = (Dot(o1.m_axes[0], o2.m_axes[0]) > 0) ? 1 : -1;
258 data.v2[1] = 0;
259 data.p2[0] = -proj;
260 data.p2[1] = 0;
261
262 return 1;
263 }
264
265 if(!o1.m_axes[1].isValid()) {
266 data.p2[0] = -Dot(off, o2.m_axes[0]);
267 data.p2[1] = -Dot(off, o2.m_axes[1]);
268
269 if(off != - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
270 return -1;
271
272 data.v1[0] = 1;
273 data.v1[1] = 0;
274 data.p1[0] = data.p1[1] = 0;
275 data.v2[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
276 data.v2[1] = Dot(o1.m_axes[0], o2.m_axes[1]);
277
278 return 1;
279 }
280
281 if(!o2.m_axes[1].isValid()) {
282 data.p1[0] = Dot(off, o1.m_axes[0]);
283 data.p1[1] = Dot(off, o1.m_axes[1]);
284
285 if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1])
286 return -1;
287
288 data.v2[0] = 1;
289 data.v2[1] = 0;
290 data.p2[0] = data.p2[1] = 0;
291 data.v1[0] = Dot(o1.m_axes[0], o2.m_axes[0]);
292 data.v1[1] = Dot(o1.m_axes[1], o2.m_axes[0]);
293
294 return 1;
295 }
296
297 data.p1[0] = Dot(off, o1.m_axes[0]);
298 data.p1[1] = Dot(off, o1.m_axes[1]);
299 data.p2[0] = -Dot(off, o2.m_axes[0]);
300 data.p2[1] = -Dot(off, o2.m_axes[1]);
301
302 if(off != data.p1[0] * o1.m_axes[0] + data.p1[1] * o1.m_axes[1]
303 - data.p2[0] * o2.m_axes[0] - data.p2[1] * o2.m_axes[1])
304 return -1;
305
306 basis1 /= std::sqrt(sqrmag1);
307
308 data.v1[0] = Dot(o1.m_axes[0], basis1);
309 data.v1[1] = Dot(o1.m_axes[1], basis1);
310 data.v2[0] = Dot(o2.m_axes[0], basis1);
311 data.v2[1] = Dot(o2.m_axes[1], basis1);
312
313 return 1;
314 }
315 case 2:
316 {
317 assert(o1.m_axes[1].isValid() && o2.m_axes[1].isValid());
318
319 // The planes are parallel, check if they are the same plane
320 CoordType off_sqr_mag = data.off.sqrMag();
321
322 // Find the offset between the origins in o2's coordnates
323
324 if(off_sqr_mag != 0) { // The offsets aren't identical
325 Vector<dim> off_copy = off;
326
327 data.off[0] = Dot(o2.m_axes[0], off);
328 off_copy -= o1.m_axes[0] * data.off[0];
329 data.off[1] = Dot(o2.m_axes[1], off);
330 off_copy -= o1.m_axes[1] * data.off[1];
331
332 if(off_copy.sqrMag() > off_sqr_mag * numeric_constants<CoordType>::epsilon())
333 return -1; // The planes are different
334 }
335 else
336 data.off[0] = data.off[1] = 0;
337
338 // Define o2's basis vectors in o1's coordinates
339 data.v1[0] = Dot(o2.m_axes[0], o1.m_axes[0]);
340 data.v1[1] = Dot(o2.m_axes[0], o1.m_axes[1]);
341 data.v2[0] = Dot(o2.m_axes[1], o1.m_axes[0]);
342 data.v2[1] = Dot(o2.m_axes[1], o1.m_axes[1]);
343
344 return 2;
345 }
346 default:
347 assert(false);
348 return -1;
349 }
350 }
351
352 template<int dim>
Intersect(const Polygon<dim> & r,const Point<dim> & p,bool proper)353 inline bool Intersect(const Polygon<dim>& r, const Point<dim>& p, bool proper)
354 {
355 Point<2> p2;
356
357 return r.m_poly.numCorners() > 0 && r.m_orient.checkContained(p, p2)
358 && Intersect(r.m_poly, p2, proper);
359 }
360
361 template<int dim>
Contains(const Point<dim> & p,const Polygon<dim> & r,bool proper)362 inline bool Contains(const Point<dim>& p, const Polygon<dim>& r, bool proper)
363 {
364 if(r.m_poly.numCorners() == 0)
365 return true;
366
367 if(proper)
368 return false;
369
370 for(size_t i = 1; i < r.m_poly.numCorners(); ++i)
371 if(r.m_poly[i] != r.m_poly[0])
372 return false;
373
374 Point<2> p2;
375
376 return r.m_orient.checkContained(p, p2) && p2 == r.m_poly[0];
377 }
378
379 template<int dim>
Intersect(const Polygon<dim> & p,const AxisBox<dim> & b,bool proper)380 bool Intersect(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
381 {
382 size_t corners = p.m_poly.numCorners();
383
384 if(corners == 0)
385 return false;
386
387 Point<2> p2;
388
389 if(!p.m_orient.checkIntersect(b, p2, proper))
390 return false;
391
392 Segment<dim> s;
393 s.endpoint(0) = p.m_orient.convert(p.m_poly.getCorner(corners-1));
394 int next_end = 1;
395
396 for(size_t i = 0; i < corners; ++i) {
397 s.endpoint(next_end) = p.m_orient.convert(p.m_poly.getCorner(i));
398 if(Intersect(b, s, proper))
399 return true;
400 next_end = next_end ? 0 : 1;
401 }
402
403 return Contains(p, p2, proper);
404 }
405
406 template<int dim>
_PolyContainsBox(const _Poly2Orient<dim> & orient,const Polygon<2> & poly,const Point<dim> & corner,const Vector<dim> & size,bool proper)407 bool _PolyContainsBox(const _Poly2Orient<dim> &orient, const Polygon<2> &poly,
408 const Point<dim> &corner, const Vector<dim> &size, bool proper)
409 {
410 int num_dim = 0, nonzero_dim = -1;
411
412 for(int i = 0; i < dim; ++i) {
413 if(size[i] == 0)
414 continue;
415 if(num_dim == 2)
416 return false;
417 if(nonzero_dim == -1 || std::fabs(size[nonzero_dim]) < std::fabs(size[i]))
418 nonzero_dim = i;
419 ++num_dim;
420 }
421
422 Point<2> corner1;
423
424 if(!orient.checkContained(corner, corner1))
425 return false;
426
427 if(num_dim == 0)
428 return Contains(poly, corner1, proper);
429
430 Point<2> corner2;
431
432 if(!orient.checkContained(corner + size, corner2))
433 return false;
434
435 if(num_dim == 1)
436 return Contains(poly, Segment<2>(corner1, corner2), proper);
437
438 Point<dim> other_corner = corner;
439 other_corner[nonzero_dim] += size[nonzero_dim];
440
441 Point<2> corner3;
442 if(!orient.checkContained(other_corner, corner3))
443 return false;
444
445 // Create a RotBox<2>
446
447 Vector<2> vec1(corner2 - corner1), vec2(corner3 - corner1);
448
449 RotMatrix<2> m; // A matrix which gives the rotation from the x-axis to vec1
450
451 try {
452 m.rotation(Vector<2>(1, 0), vec1);
453 }
454 catch(ColinearVectors<2>) { // vec1 is parallel to (-1, 0), so we're fine
455 m.identity();
456 }
457
458 RotBox<2> box(corner1, ProdInv(vec2, m), m);
459
460 return Contains(poly, box, proper);
461 }
462
463 template<int dim>
Contains(const Polygon<dim> & p,const AxisBox<dim> & b,bool proper)464 inline bool Contains(const Polygon<dim>& p, const AxisBox<dim>& b, bool proper)
465 {
466 return _PolyContainsBox(p.m_orient, p.m_poly, b.m_low, b.m_high - b.m_low, proper);
467 }
468
469 template<int dim>
Contains(const AxisBox<dim> & b,const Polygon<dim> & p,bool proper)470 inline bool Contains(const AxisBox<dim>& b, const Polygon<dim>& p, bool proper)
471 {
472 for(size_t i = 0; i < p.m_poly.numCorners(); ++i)
473 if(!Contains(b, p.getCorner(i), proper))
474 return false;
475
476 return true;
477 }
478
479 template<int dim>
Intersect(const Polygon<dim> & p,const Ball<dim> & b,bool proper)480 inline bool Intersect(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
481 {
482 if(p.m_poly.numCorners() == 0)
483 return false;
484
485 Point<2> c2;
486 CoordType dist;
487
488 dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
489
490 if(_Less(dist, 0, proper))
491 return false;
492
493 return Intersect(p.m_poly, Ball<2>(c2, std::sqrt(dist)), proper);
494 }
495
496 template<int dim>
Contains(const Polygon<dim> & p,const Ball<dim> & b,bool proper)497 inline bool Contains(const Polygon<dim>& p, const Ball<dim>& b, bool proper)
498 {
499 if(p.m_poly.numCorners() == 0)
500 return false;
501
502 if(b.m_radius > 0)
503 return false;
504
505 Point<2> c2;
506
507 if(!p.m_orient.checkContained(b.m_center, c2))
508 return false;
509
510 return Contains(p.m_poly, c2, proper);
511 }
512
513 template<int dim>
Contains(const Ball<dim> & b,const Polygon<dim> & p,bool proper)514 inline bool Contains(const Ball<dim>& b, const Polygon<dim>& p, bool proper)
515 {
516 if(p.m_poly.numCorners() == 0)
517 return true;
518
519 Point<2> c2;
520 CoordType dist;
521
522 dist = b.m_radius * b.m_radius - p.m_orient.offset(b.m_center, c2).sqrMag();
523
524 if(_Less(dist, 0, proper))
525 return false;
526
527 for(size_t i = 0; i != p.m_poly.numCorners(); ++i)
528 if(_Less(dist, SquaredDistance(c2, p.m_poly[i]), proper))
529 return false;
530
531 return true;
532 }
533
534 template<int dim>
Intersect(const Polygon<dim> & p,const Segment<dim> & s,bool proper)535 bool Intersect(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
536 {
537 if(p.m_poly.numCorners() == 0)
538 return false;
539
540 Point<2> p1, p2;
541 CoordType d1, d2;
542 Vector<dim> v1, v2;
543
544 v1 = p.m_orient.offset(s.m_p1, p1);
545 v2 = p.m_orient.offset(s.m_p2, p2);
546
547 if(Dot(v1, v2) > 0) // Both points on same side of sheet
548 return false;
549
550 d1 = v1.mag();
551 d2 = v2.mag();
552 Point<2> p_intersect;
553
554 if(d1 + d2 == 0) // Avoid divide by zero later
555 return Intersect(p.m_poly, Segment<2>(p1, p2), proper);
556
557 for(int i = 0; i < 2; ++i)
558 p_intersect[i] = (p1[i] * d2 + p2[i] * d1) / (d1 + d2);
559
560 return Intersect(p.m_poly, p_intersect, proper);
561 }
562
563 template<int dim>
Contains(const Polygon<dim> & p,const Segment<dim> & s,bool proper)564 inline bool Contains(const Polygon<dim>& p, const Segment<dim>& s, bool proper)
565 {
566 if(p.m_poly.numCorners() == 0)
567 return false;
568
569 Segment<2> s2;
570
571 if(!p.m_orient.checkContained(s.m_p1, s2.endpoint(0)))
572 return false;
573 if(!p.m_orient.checkContained(s.m_p2, s2.endpoint(1)))
574 return false;
575
576 return Contains(p.m_poly, s2, proper);
577 }
578
579 template<int dim>
Contains(const Segment<dim> & s,const Polygon<dim> & p,bool proper)580 inline bool Contains(const Segment<dim>& s, const Polygon<dim>& p, bool proper)
581 {
582 if(p.m_poly.numCorners() == 0)
583 return true;
584
585 // Expand the basis to include the segment, this deals well with
586 // degenerate polygons
587
588 Segment<2> s2;
589 _Poly2Orient<dim> orient(p.m_orient);
590
591 for(int i = 0; i < 2; ++i)
592 if(!orient.expand(s.endpoint(i), s2.endpoint(i)))
593 return false;
594
595 return Contains(s2, p.m_poly, proper);
596 }
597
598 template<int dim>
Intersect(const Polygon<dim> & p,const RotBox<dim> & r,bool proper)599 bool Intersect(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
600 {
601 size_t corners = p.m_poly.numCorners();
602
603 if(corners == 0)
604 return false;
605
606 _Poly2Orient<dim> orient(p.m_orient);
607 // FIXME rotateInverse()
608 orient.rotate(r.m_orient.inverse(), r.m_corner0);
609
610 AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
611
612 Point<2> p2;
613
614 if(!orient.checkIntersect(b, p2, proper))
615 return false;
616
617 Segment<dim> s;
618 s.endpoint(0) = orient.convert(p.m_poly.getCorner(corners-1));
619 int next_end = 1;
620
621 for(size_t i = 0; i < corners; ++i) {
622 s.endpoint(next_end) = orient.convert(p.m_poly.getCorner(i));
623 if(Intersect(b, s, proper))
624 return true;
625 next_end = next_end ? 0 : 1;
626 }
627
628 return Contains(p, p2, proper);
629 }
630
631 template<int dim>
Contains(const Polygon<dim> & p,const RotBox<dim> & r,bool proper)632 inline bool Contains(const Polygon<dim>& p, const RotBox<dim>& r, bool proper)
633 {
634 _Poly2Orient<dim> orient(p.m_orient);
635 orient.rotate(r.m_orient.inverse(), r.m_corner0);
636
637 return _PolyContainsBox(orient, p.m_poly, r.m_corner0, r.m_size, proper);
638 }
639
640 template<int dim>
Contains(const RotBox<dim> & r,const Polygon<dim> & p,bool proper)641 inline bool Contains(const RotBox<dim>& r, const Polygon<dim>& p, bool proper)
642 {
643 if(p.m_poly.numCorners() == 0)
644 return true;
645
646 AxisBox<dim> b(r.m_corner0, r.m_corner0 + r.m_size);
647
648 _Poly2Orient<dim> orient(p.m_orient);
649 orient.rotate(r.m_orient.inverse(), r.m_corner0);
650
651 for(size_t i = 0; i < p.m_poly.numCorners(); ++i)
652 if(!Contains(b, orient.convert(p.m_poly[i]), proper))
653 return false;
654
655 return true;
656 }
657
658 bool _PolyPolyIntersect(const Polygon<2> &poly1, const Polygon<2> &poly2,
659 const int intersect_dim,
660 const _Poly2OrientIntersectData &data, bool proper);
661
662 template<int dim>
Intersect(const Polygon<dim> & p1,const Polygon<dim> & p2,bool proper)663 inline bool Intersect(const Polygon<dim>& p1, const Polygon<dim>& p2, bool proper)
664 {
665 _Poly2OrientIntersectData data;
666
667 int intersect_dim = _Intersect(p1.m_orient, p2.m_orient, data);
668
669 return _PolyPolyIntersect(p1.m_poly, p2.m_poly, intersect_dim, data, proper);
670 }
671
672 bool _PolyPolyContains(const Polygon<2> &outer, const Polygon<2> &inner,
673 const int intersect_dim,
674 const _Poly2OrientIntersectData &data, bool proper);
675
676 template<int dim>
Contains(const Polygon<dim> & outer,const Polygon<dim> & inner,bool proper)677 inline bool Contains(const Polygon<dim>& outer, const Polygon<dim>& inner, bool proper)
678 {
679 if(outer.m_poly.numCorners() == 0)
680 return !proper && inner.m_poly.numCorners() == 0;
681
682 if(inner.m_poly.numCorners() == 0)
683 return true;
684
685 _Poly2OrientIntersectData data;
686
687 int intersect_dim = _Intersect(outer.m_orient, inner.m_orient, data);
688
689 return _PolyPolyContains(outer.m_poly, inner.m_poly, intersect_dim, data, proper);
690 }
691
692 template<>
693 bool Intersect(const Polygon<2>& r, const Point<2>& p, bool proper);
694 template<>
695 bool Contains(const Point<2>& p, const Polygon<2>& r, bool proper);
696
697 template<>
698 bool Intersect(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
699 template<>
700 bool Contains(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
701 template<>
702 bool Contains(const AxisBox<2>& b, const Polygon<2>& p, bool proper);
703
704 template<>
705 bool Intersect(const Polygon<2>& p, const Ball<2>& b, bool proper);
706 template<>
707 bool Contains(const Polygon<2>& p, const Ball<2>& b, bool proper);
708 template<>
709 bool Contains(const Ball<2>& b, const Polygon<2>& p, bool proper);
710
711 template<>
712 bool Intersect(const Polygon<2>& r, const Segment<2>& s, bool proper);
713 template<>
714 bool Contains(const Polygon<2>& p, const Segment<2>& s, bool proper);
715 template<>
716 bool Contains(const Segment<2>& s, const Polygon<2>& p, bool proper);
717
718 template<>
719 bool Intersect(const Polygon<2>& p, const RotBox<2>& r, bool proper);
720 template<>
721 bool Contains(const Polygon<2>& p, const RotBox<2>& r, bool proper);
722 template<>
723 bool Contains(const RotBox<2>& r, const Polygon<2>& p, bool proper);
724
725 template<>
726 bool Intersect(const Polygon<2>& p1, const Polygon<2>& p2, bool proper);
727 template<>
728 bool Contains(const Polygon<2>& outer, const Polygon<2>& inner, bool proper);
729
730 } // namespace WFMath
731
732 #endif // WFMATH_POLYGON_INTERSECT_H
733