WFMath 1.0.2
polygon_intersect.h
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
45namespace WFMath {
46
47template<int dim>
48inline 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
62template<int dim>
63inline 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
74template<>
75bool _Poly2Orient<3>::checkIntersectPlane(const AxisBox<3>& b, Point<2>& p2,
76 bool proper) const;
77
78template<int dim>
79bool _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
146template<int dim>
147int _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
352template<int dim>
353inline 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
361template<int dim>
362inline 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
379template<int dim>
380bool 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
406template<int dim>
407bool _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
463template<int dim>
464inline 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
469template<int dim>
470inline 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
479template<int dim>
480inline 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
496template<int dim>
497inline 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
513template<int dim>
514inline 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
534template<int dim>
535bool 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
563template<int dim>
564inline 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
579template<int dim>
580inline 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
598template<int dim>
599bool 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
631template<int dim>
632inline 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
640template<int dim>
641inline 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
658bool _PolyPolyIntersect(const Polygon<2> &poly1, const Polygon<2> &poly2,
659 const int intersect_dim,
660 const _Poly2OrientIntersectData &data, bool proper);
661
662template<int dim>
663inline 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
672bool _PolyPolyContains(const Polygon<2> &outer, const Polygon<2> &inner,
673 const int intersect_dim,
674 const _Poly2OrientIntersectData &data, bool proper);
675
676template<int dim>
677inline 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
692template<>
693bool Intersect(const Polygon<2>& r, const Point<2>& p, bool proper);
694template<>
695bool Contains(const Point<2>& p, const Polygon<2>& r, bool proper);
696
697template<>
698bool Intersect(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
699template<>
700bool Contains(const Polygon<2>& p, const AxisBox<2>& b, bool proper);
701template<>
702bool Contains(const AxisBox<2>& b, const Polygon<2>& p, bool proper);
703
704template<>
705bool Intersect(const Polygon<2>& p, const Ball<2>& b, bool proper);
706template<>
707bool Contains(const Polygon<2>& p, const Ball<2>& b, bool proper);
708template<>
709bool Contains(const Ball<2>& b, const Polygon<2>& p, bool proper);
710
711template<>
712bool Intersect(const Polygon<2>& r, const Segment<2>& s, bool proper);
713template<>
714bool Contains(const Polygon<2>& p, const Segment<2>& s, bool proper);
715template<>
716bool Contains(const Segment<2>& s, const Polygon<2>& p, bool proper);
717
718template<>
719bool Intersect(const Polygon<2>& p, const RotBox<2>& r, bool proper);
720template<>
721bool Contains(const Polygon<2>& p, const RotBox<2>& r, bool proper);
722template<>
723bool Contains(const RotBox<2>& r, const Polygon<2>& p, bool proper);
724
725template<>
726bool Intersect(const Polygon<2>& p1, const Polygon<2>& p2, bool proper);
727template<>
728bool Contains(const Polygon<2>& outer, const Polygon<2>& inner, bool proper);
729
730} // namespace WFMath
731
732#endif // WFMATH_POLYGON_INTERSECT_H
Generic library namespace.
Definition atlasconv.h:45
float CoordType
Basic floating point type.
Definition const.h:140
RotMatrix< dim > ProdInv(const RotMatrix< dim > &m1, const RotMatrix< dim > &m2)
returns m1 * m2^-1
Definition rotmatrix_funcs.h:111