26 #ifndef WFMATH_POLYGON_H 27 #define WFMATH_POLYGON_H 29 #include <wfmath/const.h> 30 #include <wfmath/axisbox.h> 31 #include <wfmath/ball.h> 32 #include <wfmath/quaternion.h> 38 template<
int dim>
class Polygon;
41 std::ostream& operator<<(std::ostream& os, const Polygon<dim>& r);
43 std::istream& operator>>(std::istream& is, Polygon<dim>& r);
53 explicit Polygon(
const AtlasInType& a) : m_points() {fromAtlas(a);}
57 friend std::ostream& operator<< <2>(std::ostream& os,
const Polygon& p);
58 friend std::istream&
operator>> <2>(std::istream& is, Polygon& p);
62 AtlasOutType toAtlas()
const;
64 void fromAtlas(
const AtlasInType& a);
66 Polygon& operator=(
const Polygon& p)
67 {m_points = p.m_points;
return *
this;}
69 bool isEqualTo(
const Polygon& p,
CoordType epsilon = numeric_constants<CoordType>::epsilon())
const;
71 bool operator==(
const Polygon& p)
const {
return isEqualTo(p);}
72 bool operator!=(
const Polygon& p)
const {
return !isEqualTo(p);}
78 size_t numCorners()
const {
return m_points.size();}
79 Point<2> getCorner(
size_t i)
const {
return m_points[i];}
80 Point<2> getCenter()
const {
return Barycenter(m_points);}
87 bool addCorner(
size_t i,
const Point<2>& p,
CoordType = numeric_constants<CoordType>::epsilon())
88 {m_points.insert(m_points.begin() + i, p);
return true;}
91 void removeCorner(
size_t i) {m_points.erase(m_points.begin() + i);}
94 bool moveCorner(
size_t i,
const Point<2>& p,
CoordType = numeric_constants<CoordType>::epsilon())
95 {m_points[i] = p;
return true;}
98 void clear() {m_points.clear();}
100 const Point<2>& operator[](
size_t i)
const {
return m_points[i];}
101 Point<2>& operator[](
size_t i) {
return m_points[i];}
103 void resize(std::vector<Point<2> >::size_type size) {m_points.resize(size);}
107 Polygon& shift(
const Vector<2>& v);
108 Polygon& moveCornerTo(
const Point<2>& p,
size_t corner)
109 {
return shift(p - getCorner(corner));}
110 Polygon& moveCenterTo(
const Point<2>& p)
111 {
return shift(p - getCenter());}
113 Polygon& rotateCorner(
const RotMatrix<2>& m,
size_t corner)
114 {rotatePoint(m, getCorner(corner));
return *
this;}
115 Polygon& rotateCenter(
const RotMatrix<2>& m)
116 {rotatePoint(m, getCenter());
return *
this;}
117 Polygon& rotatePoint(
const RotMatrix<2>& m,
const Point<2>& p);
121 AxisBox<2> boundingBox()
const {
return BoundingBox(m_points);}
125 Polygon toParentCoords(
const Point<2>& origin,
126 const RotMatrix<2>& rotation = RotMatrix<2>().identity())
const;
127 Polygon toParentCoords(
const AxisBox<2>& coords)
const;
128 Polygon toParentCoords(
const RotBox<2>& coords)
const;
134 Polygon toLocalCoords(
const Point<2>& origin,
135 const RotMatrix<2>& rotation = RotMatrix<2>().identity())
const;
136 Polygon toLocalCoords(
const AxisBox<2>& coords)
const;
137 Polygon toLocalCoords(
const RotBox<2>& coords)
const;
139 friend bool Intersect<2>(
const Polygon& r,
const Point<2>& p,
bool proper);
140 friend bool Contains<2>(
const Point<2>& p,
const Polygon& r,
bool proper);
142 friend bool Intersect<2>(
const Polygon& p,
const AxisBox<2>& b,
bool proper);
143 friend bool Contains<2>(
const Polygon& p,
const AxisBox<2>& b,
bool proper);
144 friend bool Contains<2>(
const AxisBox<2>& b,
const Polygon& p,
bool proper);
146 friend bool Intersect<2>(
const Polygon& p,
const Ball<2>& b,
bool proper);
147 friend bool Contains<2>(
const Polygon& p,
const Ball<2>& b,
bool proper);
148 friend bool Contains<2>(
const Ball<2>& b,
const Polygon& p,
bool proper);
150 friend bool Intersect<2>(
const Polygon& r,
const Segment<2>& s,
bool proper);
151 friend bool Contains<2>(
const Polygon& p,
const Segment<2>& s,
bool proper);
152 friend bool Contains<2>(
const Segment<2>& s,
const Polygon& p,
bool proper);
154 friend bool Intersect<2>(
const Polygon& p,
const RotBox<2>& r,
bool proper);
155 friend bool Contains<2>(
const Polygon& p,
const RotBox<2>& r,
bool proper);
156 friend bool Contains<2>(
const RotBox<2>& r,
const Polygon& p,
bool proper);
158 friend bool Intersect<2>(
const Polygon& p1,
const Polygon& p2,
bool proper);
159 friend bool Contains<2>(
const Polygon& outer,
const Polygon& inner,
bool proper);
162 std::vector<Point<2> > m_points;
163 typedef std::vector<Point<2> >::iterator theIter;
164 typedef std::vector<Point<2> >::const_iterator theConstIter;
172 _WFMATH_POLY2REORIENT_NONE,
173 _WFMATH_POLY2REORIENT_CLEAR_AXIS2,
174 _WFMATH_POLY2REORIENT_CLEAR_BOTH_AXES,
175 _WFMATH_POLY2REORIENT_MOVE_AXIS2_TO_AXIS1,
176 _WFMATH_POLY2REORIENT_SCALE1_CLEAR2
177 } _Poly2ReorientType;
184 _Poly2Reorient(_Poly2ReorientType type,
CoordType scale = 0.0)
185 : m_type(type), m_scale(scale) {}
188 void reorient(Polygon<2>& poly,
size_t skip = std::numeric_limits<size_t>::max())
const;
191 _Poly2ReorientType m_type;
195 template<
int dim>
class _Poly2Orient;
197 struct _Poly2OrientIntersectData {
200 Vector<2> v1, v2, off;
201 bool o1_is_line, o2_is_line;
209 int _Intersect(
const _Poly2Orient<dim> &,
const _Poly2Orient<dim> &,
210 _Poly2OrientIntersectData &);
217 _Poly2Orient() : m_origin() {}
218 _Poly2Orient(
const _Poly2Orient& p) : m_origin() {operator=(p);}
221 _Poly2Orient& operator=(
const _Poly2Orient& p);
224 Point<dim> convert(
const Point<2>& p)
const;
229 bool expand(
const Point<dim>& pd, Point<2>& p2,
CoordType epsilon = numeric_constants<CoordType>::epsilon());
234 _Poly2Reorient reduce(
const Polygon<2>& poly,
size_t skip = std::numeric_limits<size_t>::max());
236 void shift(
const Vector<dim>& v) {
if(m_origin.isValid()) m_origin += v;}
237 void rotate(
const RotMatrix<dim>& m,
const Point<dim>& p);
239 void rotate2(
const RotMatrix<dim>& m,
const Point<2>& p);
242 void rotate(
const Quaternion& q,
const Point<3>& p);
244 void rotate2(
const Quaternion& q,
const Point<2>& p);
246 _Poly2Orient toParentCoords(
const Point<dim>& origin,
247 const RotMatrix<dim>& rotation = RotMatrix<dim>().identity())
const 248 {_Poly2Orient p(*
this); p.m_origin = m_origin.toParentCoords(origin, rotation);
249 p.m_axes[0].rotate(rotation); p.m_axes[1].rotate(rotation);
return p;}
250 _Poly2Orient toParentCoords(
const AxisBox<dim>& coords)
const 251 {_Poly2Orient p(*
this); p.m_origin = m_origin.toParentCoords(coords);
return p;}
252 _Poly2Orient toParentCoords(
const RotBox<dim>& coords)
const 253 {_Poly2Orient p(*
this); p.m_origin = m_origin.toParentCoords(coords);
254 p.m_axes[0].rotate(coords.orientation());
255 p.m_axes[1].rotate(coords.orientation());
return p;}
261 _Poly2Orient toLocalCoords(
const Point<dim>& origin,
262 const RotMatrix<dim>& rotation = RotMatrix<dim>().identity())
const 263 {_Poly2Orient p(*
this); p.m_origin = m_origin.toLocalCoords(origin, rotation);
264 p.m_axes[0] = rotation * p.m_axes[0];
265 p.m_axes[1] = rotation * p.m_axes[1];
return p;}
266 _Poly2Orient toLocalCoords(
const AxisBox<dim>& coords)
const 267 {_Poly2Orient p(*
this); p.m_origin = m_origin.toLocalCoords(coords);
return p;}
268 _Poly2Orient toLocalCoords(
const RotBox<dim>& coords)
const 269 {_Poly2Orient p(*
this); p.m_origin = m_origin.toLocalCoords(coords);
270 p.m_axes[0] = coords.orientation() * p.m_axes[0];
271 p.m_axes[1] = coords.orientation() * p.m_axes[1];
return p;}
274 _Poly2Orient<3> toParentCoords(
const Point<3>& origin,
const Quaternion& rotation)
const 275 {_Poly2Orient p(*
this); p.m_origin = m_origin.toParentCoords(origin, rotation);
276 p.m_axes[0].rotate(rotation); p.m_axes[0].rotate(rotation);
return p;}
277 _Poly2Orient<3> toLocalCoords(
const Point<3>& origin,
const Quaternion& rotation)
const 278 {_Poly2Orient p(*
this); p.m_origin = m_origin.toLocalCoords(origin, rotation);
279 p.m_axes[0].rotate(rotation.inverse());
280 p.m_axes[0].rotate(rotation.inverse());
return p;}
284 Vector<dim> offset(
const Point<dim>& pd, Point<2>& p2)
const;
287 bool checkContained(
const Point<dim>& pd, Point<2> & p2)
const;
291 bool checkIntersect(
const AxisBox<dim>& b, Point<2>& p2,
bool proper)
const;
293 friend int _Intersect<dim>(
const _Poly2Orient<dim> &,
const _Poly2Orient<dim> &,
294 _Poly2OrientIntersectData &);
298 bool checkIntersectPlane(
const AxisBox<dim>& b, Point<2>& p2,
bool proper)
const;
301 Vector<dim> m_axes[2];
305 template<
int dim = 3>
309 Polygon() : m_orient(), m_poly() {}
310 Polygon(
const Polygon& p) : m_orient(p.m_orient), m_poly(p.m_poly) {}
314 friend std::ostream& operator<< <dim>(std::ostream& os,
const Polygon& p);
315 friend std::istream&
operator>> <dim>(std::istream& is, Polygon& p);
317 Polygon& operator=(
const Polygon& p)
318 {m_orient = p.m_orient; m_poly = p.m_poly;
return *
this;}
320 bool isEqualTo(
const Polygon& p2,
CoordType epsilon = numeric_constants<CoordType>::epsilon())
const;
322 bool operator==(
const Polygon& p)
const {
return isEqualTo(p);}
323 bool operator!=(
const Polygon& p)
const {
return !isEqualTo(p);}
325 bool isValid()
const {
return m_poly.isValid();}
329 size_t numCorners()
const {
return m_poly.numCorners();}
330 Point<dim> getCorner(
size_t i)
const {
return m_orient.convert(m_poly[i]);}
331 Point<dim> getCenter()
const {
return m_orient.convert(m_poly.getCenter());}
338 bool addCorner(
size_t i,
const Point<dim>& p,
CoordType epsilon = numeric_constants<CoordType>::epsilon());
341 void removeCorner(
size_t i);
347 bool moveCorner(
size_t i,
const Point<dim>& p,
CoordType epsilon = numeric_constants<CoordType>::epsilon());
350 void clear() {m_poly.clear(); m_orient = _Poly2Orient<dim>();}
354 Polygon& shift(
const Vector<dim>& v)
355 {m_orient.shift(v);
return *
this;}
356 Polygon& moveCornerTo(
const Point<dim>& p,
size_t corner)
357 {
return shift(p - getCorner(corner));}
358 Polygon& moveCenterTo(
const Point<dim>& p)
359 {
return shift(p - getCenter());}
361 Polygon& rotateCorner(
const RotMatrix<dim>& m,
size_t corner)
362 {m_orient.rotate2(m, m_poly[corner]);
return *
this;}
363 Polygon& rotateCenter(
const RotMatrix<dim>& m)
364 {
if(m_poly.numCorners() > 0)
365 m_orient.rotate2(m, m_poly.getCenter());
367 Polygon& rotatePoint(
const RotMatrix<dim>& m,
const Point<dim>& p)
368 {m_orient.rotate(m, p);
return *
this;}
371 Polygon<3>& rotateCorner(
const Quaternion& q,
size_t corner)
372 {m_orient.rotate2(q, m_poly[corner]);
return *
this;}
373 Polygon<3>& rotateCenter(
const Quaternion& q)
374 {
if(m_poly.numCorners() > 0)
375 m_orient.rotate2(q, m_poly.getCenter());
377 Polygon<3>& rotatePoint(
const Quaternion& q,
const Point<3>& p)
378 {m_orient.rotate(q, p);
return *
this;}
382 AxisBox<dim> boundingBox()
const;
383 Ball<dim> boundingSphere()
const;
384 Ball<dim> boundingSphereSloppy()
const;
386 Polygon toParentCoords(
const Point<dim>& origin,
387 const RotMatrix<dim>& rotation = RotMatrix<dim>().identity())
const 388 {Polygon p(*
this); p.m_orient = m_orient.toParentCoords(origin, rotation);
return p;}
389 Polygon toParentCoords(
const AxisBox<dim>& coords)
const 390 {Polygon p(*
this); p.m_orient = m_orient.toParentCoords(coords);
return p;}
391 Polygon toParentCoords(
const RotBox<dim>& coords)
const 392 {Polygon p(*
this); p.m_orient = m_orient.toParentCoords(coords);
return p;}
398 Polygon toLocalCoords(
const Point<dim>& origin,
399 const RotMatrix<dim>& rotation = RotMatrix<dim>().identity())
const 400 {Polygon p(*
this); p.m_orient = m_orient.toLocalCoords(origin, rotation);
return p;}
401 Polygon toLocalCoords(
const AxisBox<dim>& coords)
const 402 {Polygon p(*
this); p.m_orient = m_orient.toLocalCoords(coords);
return p;}
403 Polygon toLocalCoords(
const RotBox<dim>& coords)
const 404 {Polygon p(*
this); p.m_orient = m_orient.toLocalCoords(coords);
return p;}
407 Polygon<3> toParentCoords(
const Point<3>& origin,
const Quaternion& rotation)
const 408 {Polygon<3> p(*
this); p.m_orient = m_orient.toParentCoords(origin, rotation);
return p;}
409 Polygon<3> toLocalCoords(
const Point<3>& origin,
const Quaternion& rotation)
const 410 {Polygon<3> p(*
this); p.m_orient = m_orient.toLocalCoords(origin, rotation);
return p;}
412 friend bool Intersect<dim>(
const Polygon& r,
const Point<dim>& p,
bool proper);
413 friend bool Contains<dim>(
const Point<dim>& p,
const Polygon& r,
bool proper);
415 friend bool Intersect<dim>(
const Polygon& p,
const AxisBox<dim>& b,
bool proper);
416 friend bool Contains<dim>(
const Polygon& p,
const AxisBox<dim>& b,
bool proper);
417 friend bool Contains<dim>(
const AxisBox<dim>& b,
const Polygon& p,
bool proper);
419 friend bool Intersect<dim>(
const Polygon& p,
const Ball<dim>& b,
bool proper);
420 friend bool Contains<dim>(
const Polygon& p,
const Ball<dim>& b,
bool proper);
421 friend bool Contains<dim>(
const Ball<dim>& b,
const Polygon& p,
bool proper);
423 friend bool Intersect<dim>(
const Polygon& r,
const Segment<dim>& s,
bool proper);
424 friend bool Contains<dim>(
const Polygon& p,
const Segment<dim>& s,
bool proper);
425 friend bool Contains<dim>(
const Segment<dim>& s,
const Polygon& p,
bool proper);
427 friend bool Intersect<dim>(
const Polygon& p,
const RotBox<dim>& r,
bool proper);
428 friend bool Contains<dim>(
const Polygon& p,
const RotBox<dim>& r,
bool proper);
429 friend bool Contains<dim>(
const RotBox<dim>& r,
const Polygon& p,
bool proper);
431 friend bool Intersect<dim>(
const Polygon& p1,
const Polygon& p2,
bool proper);
432 friend bool Contains<dim>(
const Polygon& outer,
const Polygon& inner,
bool proper);
436 _Poly2Orient<dim> m_orient;
441 inline bool Polygon<dim>::addCorner(
size_t i,
const Point<dim>& p,
CoordType epsilon)
444 bool succ = m_orient.expand(p, p2, epsilon);
446 m_poly.addCorner(i, p2, epsilon);
451 inline void Polygon<dim>::removeCorner(
size_t i)
453 m_poly.removeCorner(i);
454 _Poly2Reorient r = m_orient.reduce(m_poly);
459 inline bool Polygon<dim>::moveCorner(
size_t i,
const Point<dim>& p,
CoordType epsilon)
461 _Poly2Orient<dim> try_orient = m_orient;
462 _Poly2Reorient r = try_orient.reduce(m_poly, i);
465 if(!try_orient.expand(p, p2, epsilon))
468 r.reorient(m_poly, i);
470 m_orient = try_orient;
477 #endif // WFMATH_POLYGON_H Generic library namespace.
Definition: atlasconv.h:45
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:92
Polygon(const AtlasInType &a)
Construct a polygon from an object passed by Atlas.
Definition: polygon.h:53
float CoordType
Basic floating point type.
Definition: const.h:140
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
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:207
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