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
36namespace WFMath {
37
38template<int dim> class Polygon;
39
40template<int dim>
41std::ostream& operator<<(std::ostream& os, const Polygon<dim>& r);
42template<int dim>
43std::istream& operator>>(std::istream& is, Polygon<dim>& r);
44
46template<>
47class 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
160private:
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
170typedef 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{
182public:
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
189private:
190 Poly2ReorientType m_type;
191 CoordType m_scale;
192};
193
194template<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
207template<int dim>
208int Intersect(const Poly2Orient<dim> &, const Poly2Orient<dim> &,
210
211// Keep track of the orientation of a 2D polygon in dim dimensions
212template<int dim>
214{
215public:
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> &,
294
295private:
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
304template<int dim = 3>
306{
307public:
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
439template<int dim>
440inline 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
449template<int dim>
450inline 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
457template<int dim>
458inline 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
A dim dimensional axis-aligned box.
Definition: axisbox.h:64
A dim dimensional ball.
Definition: ball.h:61
The 2D specialization of the Polygon<> template.
Definition: polygon.h:48
Polygon(const AtlasInType &a)
Construct a polygon from an object passed by Atlas.
Definition: polygon.h:53
A polygon, all of whose points lie in a plane, embedded in dim dimensions.
Definition: polygon.h:306
A normalized quaternion.
Definition: quaternion.h:36
Quaternion inverse() const
returns the inverse of the Quaternion
Definition: quaternion.cpp:189
A dim dimensional box, lying at an arbitrary angle.
Definition: rotbox.h:47
const RotMatrix< dim > & orientation() const
returns the orientation of the box
Definition: rotbox.h:100
A dim dimensional rotation matrix. Technically, a member of the group O(dim).
Definition: rotmatrix.h:87
A line segment embedded in dim dimensions.
Definition: segment.h:46
Vector & rotate(int axis1, int axis2, CoordType theta)
Rotate the vector in the (axis1, axis2) plane by the angle theta.
Definition: vector_funcs.h:174
Generic library namespace.
Definition: shape.h:41
double CoordType
Basic floating point type.
Definition: const.h:140
AxisBox< dim > BoundingBox(const container< AxisBox< dim >, std::allocator< AxisBox< dim > > > &c)
Get the axis-aligned bounding box for a set of boxes.
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
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
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
static FloatType epsilon()
This is the attempted precision of the library.