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 
45 namespace WFMath {
46 
47 template<int dim>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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>
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
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