WFMath  0.3.12
polygon.h
1 // polygon.h (A 2D polygon embeded in a <dim> dimensional space)
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 
26 #ifndef WFMATH_POLYGON_H
27 #define WFMATH_POLYGON_H
28 
29 #include <wfmath/axisbox.h>
30 #include <wfmath/ball.h>
31 #include <wfmath/vector.h>
32 #include <wfmath/point.h>
33 #include <wfmath/quaternion.h>
34 #include <wfmath/rotbox.h>
35 #include <wfmath/intersect_decls.h>
36 
37 #include <vector>
38 
39 namespace WFMath {
40 
41 template<int dim> class Polygon;
42 
43 template<int dim>
44 std::ostream& operator<<(std::ostream& os, const Polygon<dim>& r);
45 template<int dim>
46 std::istream& operator>>(std::istream& is, Polygon<dim>& r);
47 
49 template<>
50 class Polygon<2>
51 {
52  public:
53  Polygon() : m_points() {}
54  Polygon(const Polygon& p) : m_points(p.m_points) {}
56  explicit Polygon(const AtlasInType& a) : m_points() {fromAtlas(a);}
57 
58  ~Polygon() {}
59 
60  friend std::ostream& operator<< <2>(std::ostream& os, const Polygon& p);
61  friend std::istream& operator>> <2>(std::istream& is, Polygon& p);
62 
63 
65  AtlasOutType toAtlas() const;
67  void fromAtlas(const AtlasInType& a);
68 
69  Polygon& operator=(const Polygon& p)
70  {m_points = p.m_points; return *this;}
71 
72  bool isEqualTo(const Polygon& p, double epsilon = WFMATH_EPSILON) const;
73 
74  bool operator==(const Polygon& p) const {return isEqualTo(p);}
75  bool operator!=(const Polygon& p) const {return !isEqualTo(p);}
76 
77  bool isValid() const;
78 
79  // Descriptive characteristics
80 
81  int numCorners() const {return m_points.size();}
82  Point<2> getCorner(int i) const {return m_points[i];}
83  Point<2> getCenter() const {return Barycenter(m_points);}
84 
85  // For a Polygon<2>, addCorner() and moveCorner() always succeed.
86  // The return values are present for the sake of a unified template
87  // interface, and the epsilon argument is ignored
88 
89  // Add before i'th corner, zero is beginning, numCorners() is end
90  bool addCorner(int i, const Point<2>& p, double epsilon = WFMATH_EPSILON)
91  {m_points.insert(m_points.begin() + i, p); return true;}
92 
93  // Remove the i'th corner
94  void removeCorner(int i) {m_points.erase(m_points.begin() + i);}
95 
96  // Move the i'th corner to p
97  bool moveCorner(int i, const Point<2>& p, double epsilon = WFMATH_EPSILON)
98  {m_points[i] = p; return true;}
99 
100  // Remove all points
101  void clear() {m_points.clear();}
102 
103  const Point<2>& operator[](int i) const {return m_points[i];}
104  Point<2>& operator[](int i) {return m_points[i];}
105 
106  void resize(unsigned int size) {m_points.resize(size);}
107 
108  // Movement functions
109 
110  Polygon& shift(const Vector<2>& v);
111  Polygon& moveCornerTo(const Point<2>& p, int corner)
112  {return shift(p - getCorner(corner));}
113  Polygon& moveCenterTo(const Point<2>& p)
114  {return shift(p - getCenter());}
115 
116  Polygon& rotateCorner(const RotMatrix<2>& m, int corner)
117  {rotatePoint(m, getCorner(corner)); return *this;}
118  Polygon& rotateCenter(const RotMatrix<2>& m)
119  {rotatePoint(m, getCenter()); return *this;}
120  Polygon& rotatePoint(const RotMatrix<2>& m, const Point<2>& p);
121 
122  // Intersection functions
123 
124  AxisBox<2> boundingBox() const {return BoundingBox(m_points);}
125  Ball<2> boundingSphere() const {return BoundingSphere(m_points);}
126  Ball<2> boundingSphereSloppy() const {return BoundingSphereSloppy(m_points);}
127 
128  Polygon toParentCoords(const Point<2>& origin,
129  const RotMatrix<2>& rotation = RotMatrix<2>().identity()) const;
130  Polygon toParentCoords(const AxisBox<2>& coords) const;
131  Polygon toParentCoords(const RotBox<2>& coords) const;
132 
133  // toLocal is just like toParent, expect we reverse the order of
134  // translation and rotation and use the opposite sense of the rotation
135  // matrix
136 
137  Polygon toLocalCoords(const Point<2>& origin,
138  const RotMatrix<2>& rotation = RotMatrix<2>().identity()) const;
139  Polygon toLocalCoords(const AxisBox<2>& coords) const;
140  Polygon toLocalCoords(const RotBox<2>& coords) const;
141 
142  friend bool Intersect<2>(const Polygon& r, const Point<2>& p, bool proper);
143  friend bool Contains<2>(const Point<2>& p, const Polygon& r, bool proper);
144 
145  friend bool Intersect<2>(const Polygon& p, const AxisBox<2>& b, bool proper);
146  friend bool Contains<2>(const Polygon& p, const AxisBox<2>& b, bool proper);
147  friend bool Contains<2>(const AxisBox<2>& b, const Polygon& p, bool proper);
148 
149  friend bool Intersect<2>(const Polygon& p, const Ball<2>& b, bool proper);
150  friend bool Contains<2>(const Polygon& p, const Ball<2>& b, bool proper);
151  friend bool Contains<2>(const Ball<2>& b, const Polygon& p, bool proper);
152 
153  friend bool Intersect<2>(const Polygon& r, const Segment<2>& s, bool proper);
154  friend bool Contains<2>(const Polygon& p, const Segment<2>& s, bool proper);
155  friend bool Contains<2>(const Segment<2>& s, const Polygon& p, bool proper);
156 
157  friend bool Intersect<2>(const Polygon& p, const RotBox<2>& r, bool proper);
158  friend bool Contains<2>(const Polygon& p, const RotBox<2>& r, bool proper);
159  friend bool Contains<2>(const RotBox<2>& r, const Polygon& p, bool proper);
160 
161  friend bool Intersect<2>(const Polygon& p1, const Polygon& p2, bool proper);
162  friend bool Contains<2>(const Polygon& outer, const Polygon& inner, bool proper);
163 
164 private:
165  std::vector<Point<2> > m_points;
166  typedef std::vector<Point<2> >::iterator theIter;
167  typedef std::vector<Point<2> >::const_iterator theConstIter;
168 
169 };
170 
171 // Helper classes, to keep track of the orientation of
172 // a 2D polygon in dim dimensions
173 
174 typedef enum {
175  _WFMATH_POLY2REORIENT_NONE,
176  _WFMATH_POLY2REORIENT_CLEAR_AXIS2,
177  _WFMATH_POLY2REORIENT_CLEAR_BOTH_AXES,
178  _WFMATH_POLY2REORIENT_MOVE_AXIS2_TO_AXIS1,
179  _WFMATH_POLY2REORIENT_SCALE1_CLEAR2
180 } _Poly2ReorientType;
181 
182 // Reorient a 2D polygon to match a change in the basis
183 // used by _Poly2Orient
184 class _Poly2Reorient
185 {
186 public:
187  _Poly2Reorient(_Poly2ReorientType type, CoordType scale = 0.0)
188  : m_type(type), m_scale(scale) {}
189  ~_Poly2Reorient() {}
190 
191  void reorient(Polygon<2>& poly, int skip = -1) const;
192 
193 private:
194  _Poly2ReorientType m_type;
195  CoordType m_scale;
196 };
197 
198 template<int dim> class _Poly2Orient;
199 
200 struct _Poly2OrientIntersectData {
201  int dim;
202  Point<2> p1, p2;
203  Vector<2> v1, v2, off;
204  bool o1_is_line, o2_is_line;
205 };
206 
207 // Finds the intersection of the two planes, returns the
208 // dimension of the intersection space, the rest of the arguments
209 // are various information returned depending on the dimension of
210 // the intersection
211 template<int dim>
212 int _Intersect(const _Poly2Orient<dim> &, const _Poly2Orient<dim> &,
213  _Poly2OrientIntersectData &);
214 
215 // Keep track of the orientation of a 2D polygon in dim dimensions
216 template<int dim>
217 class _Poly2Orient
218 {
219 public:
220  _Poly2Orient() : m_origin() {}
221  _Poly2Orient(const _Poly2Orient& p) : m_origin() {operator=(p);}
222  ~_Poly2Orient() {}
223 
224  _Poly2Orient& operator=(const _Poly2Orient& p);
225 
226  // Convert a point in the 2D polygon to a point in dim dimensional space
227  Point<dim> convert(const Point<2>& p) const;
228 
229  // Try to convert a point from dim dimensions into 2D, expanding the
230  // basis if necessary. Returns true on success. On failure, the
231  // basis is unchanged.
232  bool expand(const Point<dim>& pd, Point<2>& p2, double epsilon = WFMATH_EPSILON);
233 
234  // Reduce the basis to the minimum necessary to span the points in
235  // poly (with the exception of skip). Returns _Poly2Reorient, which needs
236  // to be used to reorient the points to match the new basis.
237  _Poly2Reorient reduce(const Polygon<2>& poly, int skip = -1);
238 
239  void shift(const Vector<dim>& v) {if(m_origin.isValid()) m_origin += v;}
240  void rotate(const RotMatrix<dim>& m, const Point<dim>& p);
241  // Rotates about the point which corresponds to "p" in the oriented plane
242  void rotate2(const RotMatrix<dim>& m, const Point<2>& p);
243 
244 //3D only
245  void rotate(const Quaternion& q, const Point<3>& p);
246  // Rotates about the point which corresponds to "p" in the oriented plane
247  void rotate2(const Quaternion& q, const Point<2>& p);
248 
249  _Poly2Orient toParentCoords(const Point<dim>& origin,
250  const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
251  {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(origin, rotation);
252  p.m_axes[0].rotate(rotation); p.m_axes[1].rotate(rotation); return p;}
253  _Poly2Orient toParentCoords(const AxisBox<dim>& coords) const
254  {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(coords); return p;}
255  _Poly2Orient toParentCoords(const RotBox<dim>& coords) const
256  {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(coords);
257  p.m_axes[0].rotate(coords.orientation());
258  p.m_axes[1].rotate(coords.orientation()); return p;}
259 
260  // toLocal is just like toParent, expect we reverse the order of
261  // translation and rotation and use the opposite sense of the rotation
262  // matrix
263 
264  _Poly2Orient toLocalCoords(const Point<dim>& origin,
265  const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
266  {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(origin, rotation);
267  p.m_axes[0] = rotation * p.m_axes[0];
268  p.m_axes[1] = rotation * p.m_axes[1]; return p;}
269  _Poly2Orient toLocalCoords(const AxisBox<dim>& coords) const
270  {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(coords); return p;}
271  _Poly2Orient toLocalCoords(const RotBox<dim>& coords) const
272  {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(coords);
273  p.m_axes[0] = coords.orientation() * p.m_axes[0];
274  p.m_axes[1] = coords.orientation() * p.m_axes[1]; return p;}
275 
276  // 3D only
277  _Poly2Orient<3> toParentCoords(const Point<3>& origin, const Quaternion& rotation) const
278  {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(origin, rotation);
279  p.m_axes[0].rotate(rotation); p.m_axes[0].rotate(rotation); return p;}
280  _Poly2Orient<3> toLocalCoords(const Point<3>& origin, const Quaternion& rotation) const
281  {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(origin, rotation);
282  p.m_axes[0].rotate(rotation.inverse());
283  p.m_axes[0].rotate(rotation.inverse()); return p;}
284 
285  // Gives the offset from pd to the space spanned by
286  // the basis, and puts the nearest point in p2.
287  Vector<dim> offset(const Point<dim>& pd, Point<2>& p2) const;
288 
289  // Like offset, but returns true if the point is in the plane
290  bool checkContained(const Point<dim>& pd, Point<2> & p2) const;
291 
292  // Check if the AxisBox intersects the spanned space, and if so
293  // return a point in the intersection.
294  bool checkIntersect(const AxisBox<dim>& b, Point<2>& p2, bool proper) const;
295 
296  friend int _Intersect<dim>(const _Poly2Orient<dim> &, const _Poly2Orient<dim> &,
297  _Poly2OrientIntersectData &);
298 
299 private:
300  // special case of the above when both axes are valid
301  bool checkIntersectPlane(const AxisBox<dim>& b, Point<2>& p2, bool proper) const;
302 
303  Point<dim> m_origin;
304  Vector<dim> m_axes[2]; // Normalized to unit length
305 };
306 
308 template<int dim = 3>
309 class Polygon
310 {
311 public:
312  Polygon() : m_orient(), m_poly() {}
313  Polygon(const Polygon& p) : m_orient(p.m_orient), m_poly(p.m_poly) {}
314 
315  ~Polygon() {}
316 
317  friend std::ostream& operator<< <dim>(std::ostream& os, const Polygon& p);
318  friend std::istream& operator>> <dim>(std::istream& is, Polygon& p);
319 
320  Polygon& operator=(const Polygon& p)
321  {m_orient = p.m_orient; m_poly = p.m_poly; return *this;}
322 
323  bool isEqualTo(const Polygon& p2, double epsilon = WFMATH_EPSILON) const;
324 
325  bool operator==(const Polygon& p) const {return isEqualTo(p);}
326  bool operator!=(const Polygon& p) const {return !isEqualTo(p);}
327 
328  bool isValid() const {return m_poly.isValid();}
329 
330  // Descriptive characteristics
331 
332  int numCorners() const {return m_poly.numCorners();}
333  Point<dim> getCorner(int i) const {return m_orient.convert(m_poly[i]);}
334  Point<dim> getCenter() const {return m_orient.convert(m_poly.getCenter());}
335 
336  // The failure of the following functions does not invalidate the
337  // polygon, but merely leaves it unchaged.
338 
339  // Add before i'th corner, zero is beginning, numCorners() is end
340  // Only succeeds if p lies in a plane with all current points
341  bool addCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
342 
343  // Remove the i'th corner
344  void removeCorner(int i);
345 
346  // Move the i'th corner to p, only succeeds if new location
347  // lies in the same plane as all the other points. Note that,
348  // under certain circumstances, this plane may not contain the
349  // original location of the point.
350  bool moveCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
351 
352  // Remove all points
353  void clear() {m_poly.clear(); m_orient = _Poly2Orient<dim>();}
354 
355  // Movement functions
356 
357  Polygon& shift(const Vector<dim>& v)
358  {m_orient.shift(v); return *this;}
359  Polygon& moveCornerTo(const Point<dim>& p, int corner)
360  {return shift(p - getCorner(corner));}
361  Polygon& moveCenterTo(const Point<dim>& p)
362  {return shift(p - getCenter());}
363 
364  Polygon& rotateCorner(const RotMatrix<dim>& m, int corner)
365  {m_orient.rotate2(m, m_poly[corner]); return *this;}
366  Polygon& rotateCenter(const RotMatrix<dim>& m)
367  {if(m_poly.numCorners() > 0)
368  m_orient.rotate2(m, m_poly.getCenter());
369  return *this;}
370  Polygon& rotatePoint(const RotMatrix<dim>& m, const Point<dim>& p)
371  {m_orient.rotate(m, p); return *this;}
372 
373  // 3D rotation functions
374  Polygon<3>& rotateCorner(const Quaternion& q, int corner)
375  {m_orient.rotate2(q, m_poly[corner]); return *this;}
376  Polygon<3>& rotateCenter(const Quaternion& q)
377  {if(m_poly.numCorners() > 0)
378  m_orient.rotate2(q, m_poly.getCenter());
379  return *this;}
380  Polygon<3>& rotatePoint(const Quaternion& q, const Point<3>& p)
381  {m_orient.rotate(q, p); return *this;}
382 
383  // Intersection functions
384 
385  AxisBox<dim> boundingBox() const;
386  Ball<dim> boundingSphere() const;
387  Ball<dim> boundingSphereSloppy() const;
388 
389  Polygon toParentCoords(const Point<dim>& origin,
390  const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
391  {Polygon p(*this); p.m_orient = m_orient.toParentCoords(origin, rotation); return p;}
392  Polygon toParentCoords(const AxisBox<dim>& coords) const
393  {Polygon p(*this); p.m_orient = m_orient.toParentCoords(coords); return p;}
394  Polygon toParentCoords(const RotBox<dim>& coords) const
395  {Polygon p(*this); p.m_orient = m_orient.toParentCoords(coords); return p;}
396 
397  // toLocal is just like toParent, expect we reverse the order of
398  // translation and rotation and use the opposite sense of the rotation
399  // matrix
400 
401  Polygon toLocalCoords(const Point<dim>& origin,
402  const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
403  {Polygon p(*this); p.m_orient = m_orient.toLocalCoords(origin, rotation); return p;}
404  Polygon toLocalCoords(const AxisBox<dim>& coords) const
405  {Polygon p(*this); p.m_orient = m_orient.toLocalCoords(coords); return p;}
406  Polygon toLocalCoords(const RotBox<dim>& coords) const
407  {Polygon p(*this); p.m_orient = m_orient.toLocalCoords(coords); return p;}
408 
409  // 3D only
410  Polygon<3> toParentCoords(const Point<3>& origin, const Quaternion& rotation) const
411  {Polygon<3> p(*this); p.m_orient = m_orient.toParentCoords(origin, rotation); return p;}
412  Polygon<3> toLocalCoords(const Point<3>& origin, const Quaternion& rotation) const
413  {Polygon<3> p(*this); p.m_orient = m_orient.toLocalCoords(origin, rotation); return p;}
414 
415  friend bool Intersect<dim>(const Polygon& r, const Point<dim>& p, bool proper);
416  friend bool Contains<dim>(const Point<dim>& p, const Polygon& r, bool proper);
417 
418  friend bool Intersect<dim>(const Polygon& p, const AxisBox<dim>& b, bool proper);
419  friend bool Contains<dim>(const Polygon& p, const AxisBox<dim>& b, bool proper);
420  friend bool Contains<dim>(const AxisBox<dim>& b, const Polygon& p, bool proper);
421 
422  friend bool Intersect<dim>(const Polygon& p, const Ball<dim>& b, bool proper);
423  friend bool Contains<dim>(const Polygon& p, const Ball<dim>& b, bool proper);
424  friend bool Contains<dim>(const Ball<dim>& b, const Polygon& p, bool proper);
425 
426  friend bool Intersect<dim>(const Polygon& r, const Segment<dim>& s, bool proper);
427  friend bool Contains<dim>(const Polygon& p, const Segment<dim>& s, bool proper);
428  friend bool Contains<dim>(const Segment<dim>& s, const Polygon& p, bool proper);
429 
430  friend bool Intersect<dim>(const Polygon& p, const RotBox<dim>& r, bool proper);
431  friend bool Contains<dim>(const Polygon& p, const RotBox<dim>& r, bool proper);
432  friend bool Contains<dim>(const RotBox<dim>& r, const Polygon& p, bool proper);
433 
434  friend bool Intersect<dim>(const Polygon& p1, const Polygon& p2, bool proper);
435  friend bool Contains<dim>(const Polygon& outer, const Polygon& inner, bool proper);
436 
437  private:
438 
439  _Poly2Orient<dim> m_orient;
440  Polygon<2> m_poly;
441 };
442 
443 } // namespace WFMath
444 
445 #endif // WFMATH_POLYGON_H
A polygon, all of whose points lie in a plane, embedded in dim dimensions.
Definition: const.h:51
Ball< dim > BoundingSphereSloppy(const container< Point< dim >, std::allocator< Point< dim > > > &c)
get a bounding sphere for a set of points
Definition: ball_funcs.h:99
Polygon(const AtlasInType &a)
Construct a polygon from an object passed by Atlas.
Definition: polygon.h:56
float CoordType
Basic floating point type.
Definition: const.h:79
Ball< dim > BoundingSphere(const container< Point< dim >, std::allocator< Point< dim > > > &c)
get the minimal bounding sphere for a set of points
Definition: ball_funcs.h:64
Point< dim > Barycenter(const container< Point< dim >, std::allocator< Point< dim > > > &c)
Find the center of a set of points, all weighted equally.
Definition: point_funcs.h:237
AxisBox< dim > BoundingBox(const container< AxisBox< dim >, std::allocator< AxisBox< dim > > > &c)
Get the axis-aligned bounding box for a set of boxes.
Definition: axisbox_funcs.h:137