• Main Page
  • Namespaces
  • Classes
  • Files
  • File List

polygon.h

00001 // polygon.h (A 2D polygon embeded in a <dim> dimensional space)
00002 //
00003 //  The WorldForge Project
00004 //  Copyright (C) 2002  The WorldForge Project
00005 //
00006 //  This program is free software; you can redistribute it and/or modify
00007 //  it under the terms of the GNU General Public License as published by
00008 //  the Free Software Foundation; either version 2 of the License, or
00009 //  (at your option) any later version.
00010 //
00011 //  This program is distributed in the hope that it will be useful,
00012 //  but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 //  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 //  GNU General Public License for more details.
00015 //
00016 //  You should have received a copy of the GNU General Public License
00017 //  along with this program; if not, write to the Free Software
00018 //  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00019 //
00020 //  For information about WorldForge and its authors, please contact
00021 //  the Worldforge Web Site at http://www.worldforge.org.
00022 //
00023 
00024 // Author: Ron Steinke
00025 
00026 #ifndef WFMATH_POLYGON_H
00027 #define WFMATH_POLYGON_H
00028 
00029 #include <wfmath/const.h>
00030 #include <wfmath/vector.h>
00031 #include <wfmath/point.h>
00032 #include <wfmath/rotmatrix.h>
00033 #include <wfmath/axisbox.h>
00034 #include <wfmath/rotbox.h>
00035 #include <wfmath/ball.h>
00036 #include <wfmath/intersect_decls.h>
00037 
00038 #include <vector>
00039 
00040 namespace WFMath {
00041 
00042 template<const int dim> class Polygon;
00043 
00044 template<const int dim>
00045 std::ostream& operator<<(std::ostream& os, const Polygon<dim>& r);
00046 template<const int dim>
00047 std::istream& operator>>(std::istream& is, Polygon<dim>& r);
00048 
00050 template<>
00051 class Polygon<2>
00052 {
00053  public:
00054   Polygon() {}
00055   Polygon(const Polygon& p) : m_points(p.m_points) {}
00057   explicit Polygon(const AtlasInType& a) {fromAtlas(a);}
00058 
00059   ~Polygon() {}
00060 #ifndef WFMATH_NO_CLASS_FUNCTION_SPECIALIZATION
00061   friend std::ostream& operator<< <2>(std::ostream& os, const Polygon& p);
00062   friend std::istream& operator>> <2>(std::istream& is, Polygon& p);
00063 #endif
00064   
00066   AtlasOutType toAtlas() const;
00068   void fromAtlas(const AtlasInType& a);
00069   
00070   Polygon& operator=(const Polygon& p)
00071   {m_points = p.m_points; return *this;}
00072 
00073   bool isEqualTo(const Polygon& p, double epsilon = WFMATH_EPSILON) const;
00074 
00075   bool operator==(const Polygon& p) const       {return isEqualTo(p);}
00076   bool operator!=(const Polygon& p) const       {return !isEqualTo(p);}
00077 
00078   bool isValid() const;
00079 
00080   // Descriptive characteristics
00081 
00082   int numCorners() const {return m_points.size();}
00083   Point<2> getCorner(int i) const
00084   {assert(i >= 0 && ((unsigned int) i) < m_points.size()); return m_points[i];}
00085 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00086   Point<2> getCenter() const {return Barycenter(m_points);}
00087 #endif
00088 
00089   // For a Polygon<2>, addCorner() and moveCorner() always succeed.
00090   // The return values are present for the sake of a unified template
00091   // interface, and the epsilon argument is ignored
00092 
00093   // Add before i'th corner, zero is beginning, numCorners() is end
00094   bool addCorner(int i, const Point<2>& p, double epsilon = WFMATH_EPSILON)
00095   {m_points.insert(m_points.begin() + i, p); return true;}
00096 
00097   // Remove the i'th corner
00098   void removeCorner(int i) {m_points.erase(m_points.begin() + i);}
00099 
00100   // Move the i'th corner to p
00101   bool moveCorner(int i, const Point<2>& p, double epsilon = WFMATH_EPSILON)
00102   {m_points[i] = p; return true;}
00103 
00104   // Remove all points
00105   void clear()  {m_points.clear();}
00106 
00107   const Point<2>& operator[](int i) const {return m_points[i];}
00108   Point<2>& operator[](int i)             {return m_points[i];}
00109 
00110   void resize(unsigned int size) {m_points.resize(size);}
00111 
00112   // Movement functions
00113 
00114   Polygon& shift(const Vector<2>& v);
00115   Polygon& moveCornerTo(const Point<2>& p, int corner)
00116   {return shift(p - getCorner(corner));}
00117 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00118   Polygon& moveCenterTo(const Point<2>& p)
00119   {return shift(p - getCenter());}
00120 #endif
00121 
00122   Polygon& rotateCorner(const RotMatrix<2>& m, int corner)
00123   {rotatePoint(m, getCorner(corner)); return *this;}
00124 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00125   Polygon& rotateCenter(const RotMatrix<2>& m)
00126   {rotatePoint(m, getCenter()); return *this;}
00127 #endif
00128   Polygon& rotatePoint(const RotMatrix<2>& m, const Point<2>& p);
00129 
00130   // Intersection functions
00131 
00132 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00133   AxisBox<2> boundingBox() const {return BoundingBox(m_points);}
00134   Ball<2> boundingSphere() const {return BoundingSphere(m_points);}
00135   Ball<2> boundingSphereSloppy() const {return BoundingSphereSloppy(m_points);}
00136 #endif
00137 
00138   Polygon toParentCoords(const Point<2>& origin,
00139       const RotMatrix<2>& rotation = RotMatrix<2>().identity()) const;
00140   Polygon toParentCoords(const AxisBox<2>& coords) const;
00141   Polygon toParentCoords(const RotBox<2>& coords) const;
00142 
00143   // toLocal is just like toParent, expect we reverse the order of
00144   // translation and rotation and use the opposite sense of the rotation
00145   // matrix
00146 
00147   Polygon toLocalCoords(const Point<2>& origin,
00148       const RotMatrix<2>& rotation = RotMatrix<2>().identity()) const;
00149   Polygon toLocalCoords(const AxisBox<2>& coords) const;
00150   Polygon toLocalCoords(const RotBox<2>& coords) const;
00151 
00152   friend bool Intersect<2>(const Polygon& r, const Point<2>& p, bool proper);
00153   friend bool Contains<2>(const Point<2>& p, const Polygon& r, bool proper);
00154 
00155   friend bool Intersect<2>(const Polygon& p, const AxisBox<2>& b, bool proper);
00156   friend bool Contains<2>(const Polygon& p, const AxisBox<2>& b, bool proper);
00157   friend bool Contains<2>(const AxisBox<2>& b, const Polygon& p, bool proper);
00158 
00159   friend bool Intersect<2>(const Polygon& p, const Ball<2>& b, bool proper);
00160   friend bool Contains<2>(const Polygon& p, const Ball<2>& b, bool proper);
00161   friend bool Contains<2>(const Ball<2>& b, const Polygon& p, bool proper);
00162 
00163   friend bool Intersect<2>(const Polygon& r, const Segment<2>& s, bool proper);
00164   friend bool Contains<2>(const Polygon& p, const Segment<2>& s, bool proper);
00165   friend bool Contains<2>(const Segment<2>& s, const Polygon& p, bool proper);
00166 
00167   friend bool Intersect<2>(const Polygon& p, const RotBox<2>& r, bool proper);
00168   friend bool Contains<2>(const Polygon& p, const RotBox<2>& r, bool proper);
00169   friend bool Contains<2>(const RotBox<2>& r, const Polygon& p, bool proper);
00170 
00171   friend bool Intersect<2>(const Polygon& p1, const Polygon& p2, bool proper);
00172   friend bool Contains<2>(const Polygon& outer, const Polygon& inner, bool proper);
00173 
00174 private:
00175   std::vector<Point<2> > m_points;
00176   typedef std::vector<Point<2> >::iterator theIter;
00177   typedef std::vector<Point<2> >::const_iterator theConstIter;
00178 
00179 };
00180 
00181 // Helper classes, to keep track of the orientation of
00182 // a 2D polygon in dim dimensions
00183 
00184 typedef enum {
00185   _WFMATH_POLY2REORIENT_NONE,
00186   _WFMATH_POLY2REORIENT_CLEAR_AXIS2,
00187   _WFMATH_POLY2REORIENT_CLEAR_BOTH_AXES,
00188   _WFMATH_POLY2REORIENT_MOVE_AXIS2_TO_AXIS1,
00189   _WFMATH_POLY2REORIENT_SCALE1_CLEAR2
00190 } _Poly2ReorientType;
00191 
00192 // Reorient a 2D polygon to match a change in the basis
00193 // used by _Poly2Orient
00194 class _Poly2Reorient
00195 {
00196 public:
00197   _Poly2Reorient(_Poly2ReorientType type, CoordType scale = 0.0)
00198   : m_type(type), m_scale(scale) {}
00199   ~_Poly2Reorient() {}
00200 
00201   void reorient(Polygon<2>& poly, int skip = -1) const;
00202 
00203 private:
00204   _Poly2ReorientType m_type;
00205   CoordType m_scale;
00206 };
00207 
00208 template<const int dim> class _Poly2Orient;
00209 
00210 struct _Poly2OrientIntersectData {
00211   int dim;
00212   Point<2> p1, p2;
00213   Vector<2> v1, v2, off;
00214   bool o1_is_line, o2_is_line;
00215 };
00216 
00217 // Finds the intersection of the two planes, returns the
00218 // dimension of the intersection space, the rest of the arguments
00219 // are various information returned depending on the dimension of
00220 // the intersection
00221 template<const int dim>
00222 int  _Intersect(const _Poly2Orient<dim> &, const _Poly2Orient<dim> &,
00223     _Poly2OrientIntersectData &);
00224 
00225 // Keep track of the orientation of a 2D polygon in dim dimensions
00226 template<const int dim>
00227 class _Poly2Orient
00228 {
00229 public:
00230   _Poly2Orient() {}
00231   _Poly2Orient(const _Poly2Orient& p)   {operator=(p);}
00232   ~_Poly2Orient() {}
00233 
00234   _Poly2Orient& operator=(const _Poly2Orient& p);
00235 
00236   // Convert a point in the 2D polygon to a point in dim dimensional space
00237   Point<dim> convert(const Point<2>& p) const;
00238 
00239   // Try to convert a point from dim dimensions into 2D, expanding the
00240   // basis if necessary. Returns true on success. On failure, the
00241   // basis is unchanged.
00242   bool expand(const Point<dim>& pd, Point<2>& p2, double epsilon = WFMATH_EPSILON);
00243 
00244   // Reduce the basis to the minimum necessary to span the points in
00245   // poly (with the exception of skip). Returns _Poly2Reorient, which needs
00246   // to be used to reorient the points to match the new basis.
00247   _Poly2Reorient reduce(const Polygon<2>& poly, int skip = -1);
00248 
00249   void shift(const Vector<dim>& v) {if(m_origin.isValid()) m_origin += v;}
00250   void rotate(const RotMatrix<dim>& m, const Point<dim>& p);
00251   // Rotates about the point which corresponds to "p" in the oriented plane
00252   void rotate2(const RotMatrix<dim>& m, const Point<2>& p);
00253 
00254 //3D only
00255   void rotate(const Quaternion& q, const Point<3>& p);
00256   // Rotates about the point which corresponds to "p" in the oriented plane
00257   void rotate2(const Quaternion& q, const Point<2>& p);
00258 
00259   _Poly2Orient toParentCoords(const Point<dim>& origin,
00260       const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
00261   {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(origin, rotation);
00262     p.m_axes[0] *= rotation; p.m_axes[1] *= rotation; return p;}
00263   _Poly2Orient toParentCoords(const AxisBox<dim>& coords) const
00264   {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(coords); return p;}
00265   _Poly2Orient toParentCoords(const RotBox<dim>& coords) const
00266   {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(coords);
00267     p.m_axes[0] *= coords.orientation();
00268     p.m_axes[1] *= coords.orientation(); return p;}
00269 
00270   // toLocal is just like toParent, expect we reverse the order of
00271   // translation and rotation and use the opposite sense of the rotation
00272   // matrix
00273 
00274   _Poly2Orient toLocalCoords(const Point<dim>& origin,
00275       const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
00276   {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(origin, rotation);
00277     p.m_axes[0] = rotation * p.m_axes[0];
00278     p.m_axes[1] = rotation * p.m_axes[1]; return p;}
00279   _Poly2Orient toLocalCoords(const AxisBox<dim>& coords) const
00280   {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(coords); return p;}
00281   _Poly2Orient toLocalCoords(const RotBox<dim>& coords) const
00282   {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(coords);
00283     p.m_axes[0] = coords.orientation() * p.m_axes[0];
00284     p.m_axes[1] = coords.orientation() * p.m_axes[1]; return p;}
00285 
00286   // 3D only
00287   _Poly2Orient<3> toParentCoords(const Point<3>& origin, const Quaternion& rotation) const
00288   {_Poly2Orient p(*this); p.m_origin = m_origin.toParentCoords(origin, rotation);
00289     p.m_axes[0].rotate(rotation); p.m_axes[0].rotate(rotation); return p;}
00290   _Poly2Orient<3> toLocalCoords(const Point<3>& origin, const Quaternion& rotation) const
00291   {_Poly2Orient p(*this); p.m_origin = m_origin.toLocalCoords(origin, rotation);
00292     p.m_axes[0].rotate(rotation.inverse());
00293     p.m_axes[0].rotate(rotation.inverse()); return p;}
00294 
00295   // Gives the offset from pd to the space spanned by
00296   // the basis, and puts the nearest point in p2.
00297   Vector<dim> offset(const Point<dim>& pd, Point<2>& p2) const;
00298 
00299   // Like offset, but returns true if the point is in the plane
00300   bool checkContained(const Point<dim>& pd, Point<2> & p2) const;
00301 
00302   // Check if the AxisBox intersects the spanned space, and if so
00303   // return a point in the intersection.
00304   bool checkIntersect(const AxisBox<dim>& b, Point<2>& p2, bool proper) const;
00305 
00306   friend int  _Intersect<dim>(const _Poly2Orient<dim> &, const _Poly2Orient<dim> &,
00307             _Poly2OrientIntersectData &);
00308 
00309 private:
00310   // special case of the above when both axes are valid
00311   bool checkIntersectPlane(const AxisBox<dim>& b, Point<2>& p2, bool proper) const;
00312 
00313   Point<dim> m_origin;
00314   Vector<dim> m_axes[2]; // Normalized to unit length
00315 };
00316 
00318 template<const int dim>
00319 class Polygon
00320 {
00321 public:
00322   Polygon() {}
00323   Polygon(const Polygon& p) : m_orient(p.m_orient), m_poly(p.m_poly) {}
00324 
00325   ~Polygon() {}
00326 
00327   friend std::ostream& operator<< <dim>(std::ostream& os, const Polygon& p);
00328   friend std::istream& operator>> <dim>(std::istream& is, Polygon& p);
00329 
00330   Polygon& operator=(const Polygon& p)
00331   {m_orient = p.m_orient; m_poly = p.m_poly; return *this;}
00332 
00333   bool isEqualTo(const Polygon& p2, double epsilon = WFMATH_EPSILON) const;
00334 
00335   bool operator==(const Polygon& p) const       {return isEqualTo(p);}
00336   bool operator!=(const Polygon& p) const       {return !isEqualTo(p);}
00337 
00338   bool isValid() const {return m_poly.isValid();}
00339 
00340   // Descriptive characteristics
00341 
00342   int numCorners() const {return m_poly.numCorners();}
00343   Point<dim> getCorner(int i) const
00344   {assert(i >= 0 && i < m_poly.numCorners()); return m_orient.convert(m_poly[i]);}
00345   Point<dim> getCenter() const {return m_orient.convert(m_poly.getCenter());}
00346 
00347   // The failure of the following functions does not invalidate the
00348   // polygon, but merely leaves it unchaged.
00349 
00350   // Add before i'th corner, zero is beginning, numCorners() is end
00351   // Only succeeds if p lies in a plane with all current points
00352   bool addCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
00353 
00354   // Remove the i'th corner
00355   void removeCorner(int i);
00356 
00357   // Move the i'th corner to p, only succeeds if new location
00358   // lies in the same plane as all the other points. Note that,
00359   // under certain circumstances, this plane may not contain the
00360   // original location of the point.
00361   bool moveCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
00362 
00363   // Remove all points
00364   void clear()  {m_poly.clear(); m_orient = _Poly2Orient<dim>();}
00365 
00366   // Movement functions
00367 
00368   Polygon& shift(const Vector<dim>& v)
00369   {m_orient.shift(v); return *this;}
00370   Polygon& moveCornerTo(const Point<dim>& p, int corner)
00371   {return shift(p - getCorner(corner));}
00372   Polygon& moveCenterTo(const Point<dim>& p)
00373   {return shift(p - getCenter());}
00374 
00375   Polygon& rotateCorner(const RotMatrix<dim>& m, int corner)
00376   {m_orient.rotate2(m, m_poly[corner]); return *this;}
00377   Polygon& rotateCenter(const RotMatrix<dim>& m)
00378   {if(m_poly.numCorners() > 0)
00379     m_orient.rotate2(m, m_poly.getCenter());
00380   return *this;}
00381   Polygon& rotatePoint(const RotMatrix<dim>& m, const Point<dim>& p)
00382   {m_orient.rotate(m, p); return *this;}
00383 
00384   // 3D rotation functions
00385   Polygon<3>& rotateCorner(const Quaternion& q, int corner)
00386   {m_orient.rotate2(q, m_poly[corner]); return *this;}
00387   Polygon<3>& rotateCenter(const Quaternion& q)
00388   {if(m_poly.numCorners() > 0)
00389     m_orient.rotate2(q, m_poly.getCenter());
00390   return *this;}
00391   Polygon<3>& rotatePoint(const Quaternion& q, const Point<3>& p)
00392   {m_orient.rotate(q, p); return *this;}
00393 
00394   // Intersection functions
00395 
00396   AxisBox<dim> boundingBox() const;
00397   Ball<dim> boundingSphere() const;
00398   Ball<dim> boundingSphereSloppy() const;
00399 
00400   Polygon toParentCoords(const Point<dim>& origin,
00401       const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
00402         {Polygon p(*this); p.m_orient = m_orient.toParentCoords(origin, rotation); return p;}
00403   Polygon toParentCoords(const AxisBox<dim>& coords) const
00404         {Polygon p(*this); p.m_orient = m_orient.toParentCoords(coords); return p;}
00405   Polygon toParentCoords(const RotBox<dim>& coords) const
00406         {Polygon p(*this); p.m_orient = m_orient.toParentCoords(coords); return p;}
00407 
00408   // toLocal is just like toParent, expect we reverse the order of
00409   // translation and rotation and use the opposite sense of the rotation
00410   // matrix
00411 
00412   Polygon toLocalCoords(const Point<dim>& origin,
00413       const RotMatrix<dim>& rotation = RotMatrix<dim>().identity()) const
00414         {Polygon p(*this); p.m_orient = m_orient.toLocalCoords(origin, rotation); return p;}
00415   Polygon toLocalCoords(const AxisBox<dim>& coords) const
00416         {Polygon p(*this); p.m_orient = m_orient.toLocalCoords(coords); return p;}
00417   Polygon toLocalCoords(const RotBox<dim>& coords) const
00418         {Polygon p(*this); p.m_orient = m_orient.toLocalCoords(coords); return p;}
00419 
00420   // 3D only
00421   Polygon<3> toParentCoords(const Point<3>& origin, const Quaternion& rotation) const
00422         {Polygon<3> p(*this); p.m_orient = m_orient.toParentCoords(origin, rotation); return p;}
00423   Polygon<3> toLocalCoords(const Point<3>& origin, const Quaternion& rotation) const
00424         {Polygon<3> p(*this); p.m_orient = m_orient.toLocalCoords(origin, rotation); return p;}
00425 
00426   friend bool Intersect<dim>(const Polygon& r, const Point<dim>& p, bool proper);
00427   friend bool Contains<dim>(const Point<dim>& p, const Polygon& r, bool proper);
00428 
00429   friend bool Intersect<dim>(const Polygon& p, const AxisBox<dim>& b, bool proper);
00430   friend bool Contains<dim>(const Polygon& p, const AxisBox<dim>& b, bool proper);
00431   friend bool Contains<dim>(const AxisBox<dim>& b, const Polygon& p, bool proper);
00432 
00433   friend bool Intersect<dim>(const Polygon& p, const Ball<dim>& b, bool proper);
00434   friend bool Contains<dim>(const Polygon& p, const Ball<dim>& b, bool proper);
00435   friend bool Contains<dim>(const Ball<dim>& b, const Polygon& p, bool proper);
00436 
00437   friend bool Intersect<dim>(const Polygon& r, const Segment<dim>& s, bool proper);
00438   friend bool Contains<dim>(const Polygon& p, const Segment<dim>& s, bool proper);
00439   friend bool Contains<dim>(const Segment<dim>& s, const Polygon& p, bool proper);
00440 
00441   friend bool Intersect<dim>(const Polygon& p, const RotBox<dim>& r, bool proper);
00442   friend bool Contains<dim>(const Polygon& p, const RotBox<dim>& r, bool proper);
00443   friend bool Contains<dim>(const RotBox<dim>& r, const Polygon& p, bool proper);
00444 
00445   friend bool Intersect<dim>(const Polygon& p1, const Polygon& p2, bool proper);
00446   friend bool Contains<dim>(const Polygon& outer, const Polygon& inner, bool proper);
00447 
00448  private:
00449 
00450   _Poly2Orient<dim> m_orient;
00451   Polygon<2> m_poly;
00452 };
00453 
00454 } // namespace WFMath
00455 
00456 #include <wfmath/polygon_funcs.h>
00457 
00458 #endif  // WFMATH_POLYGON_H

Generated for WFMath by  doxygen 1.7.1