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