Main Page   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members  

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/ball.h>
00035 #include <wfmath/intersect_decls.h>
00036 
00037 #include <vector>
00038 
00039 namespace WFMath {
00040 
00041 template<const int dim> class Polygon;
00042 
00043 template<const int dim>
00044 std::ostream& operator<<(std::ostream& os, const Polygon<dim>& r);
00045 template<const int dim>
00046 std::istream& operator>>(std::istream& is, Polygon<dim>& r);
00047 
00049 template<>
00050 class Polygon<2>
00051 {
00052  public:
00053   Polygon() {}
00054   Polygon(const Polygon& p) : m_points(p.m_points) {}
00055 
00056   ~Polygon() {}
00057 #ifndef WFMATH_NO_CLASS_FUNCTION_SPECIALIZATION
00058   friend std::ostream& operator<< <2>(std::ostream& os, const Polygon& p);
00059   friend std::istream& operator>> <2>(std::istream& is, Polygon& p);
00060 #endif
00061   Polygon& operator=(const Polygon& p)
00062         {m_points = p.m_points; return *this;}
00063 
00064   bool isEqualTo(const Polygon& p, double epsilon = WFMATH_EPSILON) const;
00065 
00066   bool operator==(const Polygon& p) const       {return isEqualTo(p);}
00067   bool operator!=(const Polygon& p) const       {return !isEqualTo(p);}
00068 
00069   bool isValid() const;
00070 
00071   // WARNING! This operator is for sorting only. It does not
00072   // reflect any property of the polygon.
00073   bool operator< (const Polygon& p) const;
00074 
00075   // Descriptive characteristics
00076 
00077   int numCorners() const {return m_points.size();}
00078   Point<2> getCorner(int i) const
00079         {assert(i >= 0 && ((unsigned int) i) < m_points.size()); return m_points[i];}
00080 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00081   Point<2> getCenter() const {return Barycenter(m_points);}
00082 #endif
00083 
00084   // For a Polygon<2>, addCorner() and moveCorner() always succeed.
00085   // The return values are present for the sake of a unified template
00086   // interface, and the epsilon argument is ignored
00087 
00088   // Add before i'th corner, zero is beginning, numCorners() is end
00089   bool addCorner(int i, const Point<2>& p, double epsilon = WFMATH_EPSILON)
00090         {m_points.insert(m_points.begin() + i, p); return true;}
00091 
00092   // Remove the i'th corner
00093   void removeCorner(int i) {m_points.erase(m_points.begin() + i);}
00094 
00095   // Move the i'th corner to p
00096   bool moveCorner(int i, const Point<2>& p, double epsilon = WFMATH_EPSILON)
00097         {m_points[i] = p; return true;}
00098 
00099   // Remove all points
00100   void clear()  {m_points.clear();}
00101 
00102   const Point<2>& operator[](int i) const {return m_points[i];}
00103   Point<2>& operator[](int i)             {return m_points[i];}
00104 
00105   void resize(unsigned int size) {m_points.resize(size);}
00106 
00107   // Movement functions
00108 
00109   Polygon& shift(const Vector<2>& v);
00110   Polygon& moveCornerTo(const Point<2>& p, int corner)
00111         {return shift(p - getCorner(corner));}
00112 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00113   Polygon& moveCenterTo(const Point<2>& p)
00114         {return shift(p - getCenter());}
00115 #endif
00116 
00117   Polygon& rotateCorner(const RotMatrix<2>& m, int corner)
00118         {rotatePoint(m, getCorner(corner)); return *this;}
00119 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00120   Polygon& rotateCenter(const RotMatrix<2>& m)
00121         {rotatePoint(m, getCenter()); return *this;}
00122 #endif
00123   Polygon& rotatePoint(const RotMatrix<2>& m, const Point<2>& p);
00124 
00125   // Intersection functions
00126 
00127 #ifndef WFMATH_NO_TEMPLATES_AS_TEMPLATE_PARAMETERS
00128   AxisBox<2> boundingBox() const {return BoundingBox(m_points);}
00129   Ball<2> boundingSphere() const {return BoundingSphere(m_points);}
00130   Ball<2> boundingSphereSloppy() const {return BoundingSphereSloppy(m_points);}
00131 #endif
00132 
00133   friend bool Intersect<2>(const Polygon& r, const Point<2>& p, bool proper);
00134   friend bool Contains<2>(const Point<2>& p, const Polygon& r, bool proper);
00135 
00136   friend bool Intersect<2>(const Polygon& p, const AxisBox<2>& b, bool proper);
00137   friend bool Contains<2>(const Polygon& p, const AxisBox<2>& b, bool proper);
00138   friend bool Contains<2>(const AxisBox<2>& b, const Polygon& p, bool proper);
00139 
00140   friend bool Intersect<2>(const Polygon& p, const Ball<2>& b, bool proper);
00141   friend bool Contains<2>(const Polygon& p, const Ball<2>& b, bool proper);
00142   friend bool Contains<2>(const Ball<2>& b, const Polygon& p, bool proper);
00143 
00144   friend bool Intersect<2>(const Polygon& r, const Segment<2>& s, bool proper);
00145   friend bool Contains<2>(const Polygon& p, const Segment<2>& s, bool proper);
00146   friend bool Contains<2>(const Segment<2>& s, const Polygon& p, bool proper);
00147 
00148   friend bool Intersect<2>(const Polygon& p, const RotBox<2>& r, bool proper);
00149   friend bool Contains<2>(const Polygon& p, const RotBox<2>& r, bool proper);
00150   friend bool Contains<2>(const RotBox<2>& r, const Polygon& p, bool proper);
00151 
00152   friend bool Intersect<2>(const Polygon& p1, const Polygon& p2, bool proper);
00153   friend bool Contains<2>(const Polygon& outer, const Polygon& inner, bool proper);
00154 
00155  private:
00156   std::vector<Point<2> > m_points;
00157   typedef std::vector<Point<2> >::iterator theIter;
00158   typedef std::vector<Point<2> >::const_iterator theConstIter;
00159 
00160 };
00161 
00162 // Helper classes, to keep track of the orientation of
00163 // a 2D polygon in dim dimensions
00164 
00165 typedef enum {
00166   _WFMATH_POLY2REORIENT_NONE,
00167   _WFMATH_POLY2REORIENT_CLEAR_AXIS2,
00168   _WFMATH_POLY2REORIENT_CLEAR_BOTH_AXES,
00169   _WFMATH_POLY2REORIENT_MOVE_AXIS2_TO_AXIS1,
00170   _WFMATH_POLY2REORIENT_SCALE1_CLEAR2
00171 } _Poly2ReorientType;
00172 
00173 // Reorient a 2D polygon to match a change in the basis
00174 // used by _Poly2Orient
00175 class _Poly2Reorient
00176 {
00177  public:
00178   _Poly2Reorient(_Poly2ReorientType type, CoordType scale = 0.0)
00179         : m_type(type), m_scale(scale) {}
00180   ~_Poly2Reorient() {}
00181 
00182   void reorient(Polygon<2>& poly, int skip = -1) const;
00183 
00184  private:
00185   _Poly2ReorientType m_type;
00186   CoordType m_scale;
00187 };
00188 
00189 template<const int dim> class _Poly2Orient;
00190 
00191 struct _Poly2OrientIntersectData {
00192   int dim;
00193   Point<2> p1, p2;
00194   Vector<2> v1, v2, off;
00195   bool o1_is_line, o2_is_line;
00196 };
00197 
00198 // Finds the intersection of the two planes, returns the
00199 // dimension of the intersection space, the rest of the arguments
00200 // are various information returned depending on the dimension of
00201 // the intersection
00202 template<const int dim>
00203 int  _Intersect(const _Poly2Orient<dim> &, const _Poly2Orient<dim> &,
00204                 _Poly2OrientIntersectData &);
00205 
00206 // Keep track of the orientation of a 2D polygon in dim dimensions
00207 template<const int dim>
00208 class _Poly2Orient
00209 {
00210  public:
00211   _Poly2Orient() {}
00212   _Poly2Orient(const _Poly2Orient& p)   {operator=(p);}
00213   ~_Poly2Orient() {}
00214 
00215   _Poly2Orient& operator=(const _Poly2Orient& p);
00216 
00217   // Convert a point in the 2D polygon to a point in dim dimensional space
00218   Point<dim> convert(const Point<2>& p) const;
00219 
00220   // Try to convert a point from dim dimensions into 2D, expanding the
00221   // basis if necessary. Returns true on success. On failure, the
00222   // basis is unchanged.
00223   bool expand(const Point<dim>& pd, Point<2>& p2, double epsilon = WFMATH_EPSILON);
00224 
00225   // Reduce the basis to the minimum necessary to span the points in
00226   // poly (with the exception of skip). Returns _Poly2Reorient, which needs
00227   // to be used to reorient the points to match the new basis.
00228   _Poly2Reorient reduce(const Polygon<2>& poly, int skip = -1);
00229 
00230   void shift(const Vector<dim>& v) {if(m_origin.isValid()) m_origin += v;}
00231   void rotate(const RotMatrix<dim>& m, const Point<dim>& p);
00232   // Rotates about the point which corresponds to "p" in the oriented plane
00233   void rotate2(const RotMatrix<dim>& m, const Point<2>& p);
00234 
00235   // Gives the offset from pd to the space spanned by
00236   // the basis, and puts the nearest point in p2.
00237   Vector<dim> offset(const Point<dim>& pd, Point<2>& p2) const;
00238 
00239   // Like offset, but returns true if the point is in the plane
00240   bool checkContained(const Point<dim>& pd, Point<2> & p2) const;
00241 
00242   // Check if the AxisBox intersects the spanned space, and if so
00243   // return a point in the intersection.
00244   bool checkIntersect(const AxisBox<dim>& b, Point<2>& p2, bool proper) const;
00245 
00246   friend int  _Intersect<dim>(const _Poly2Orient<dim> &, const _Poly2Orient<dim> &,
00247                               _Poly2OrientIntersectData &);
00248 
00249  private:
00250   // special case of the above when both axes are valid
00251   bool checkIntersectPlane(const AxisBox<dim>& b, Point<2>& p2, bool proper) const;
00252 
00253   Point<dim> m_origin;
00254   Vector<dim> m_axes[2]; // Normalized to unit length
00255 };
00256 
00258 template<const int dim>
00259 class Polygon
00260 {
00261  public:
00262   Polygon() {}
00263   Polygon(const Polygon& p) : m_orient(p.m_orient), m_poly(p.m_poly) {}
00264 
00265   ~Polygon() {}
00266 
00267   friend std::ostream& operator<< <dim>(std::ostream& os, const Polygon& p);
00268   friend std::istream& operator>> <dim>(std::istream& is, Polygon& p);
00269 
00270   Polygon& operator=(const Polygon& p)
00271         {m_orient = p.m_orient; m_poly = p.m_poly; return *this;}
00272 
00273   bool isEqualTo(const Polygon& p2, double epsilon = WFMATH_EPSILON) const;
00274 
00275   bool operator==(const Polygon& p) const       {return isEqualTo(p);}
00276   bool operator!=(const Polygon& p) const       {return !isEqualTo(p);}
00277 
00278   bool isValid() const {return m_poly.isValid();}
00279 
00280   // WARNING! This operator is for sorting only. It does not
00281   // reflect any property of the polygon.
00282   bool operator< (const Polygon& p) const;
00283 
00284   // Descriptive characteristics
00285 
00286   int numCorners() const {return m_poly.numCorners();}
00287   Point<dim> getCorner(int i) const
00288         {assert(i >= 0 && i < m_poly.numCorners()); return m_orient.convert(m_poly[i]);}
00289   Point<dim> getCenter() const {return m_orient.convert(m_poly.getCenter());}
00290 
00291   // The failure of the following functions does not invalidate the
00292   // polygon, but merely leaves it unchaged.
00293 
00294   // Add before i'th corner, zero is beginning, numCorners() is end
00295   // Only succeeds if p lies in a plane with all current points
00296   bool addCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
00297 
00298   // Remove the i'th corner
00299   void removeCorner(int i);
00300 
00301   // Move the i'th corner to p, only succeeds if new location
00302   // lies in the same plane as all the other points. Note that,
00303   // under certain circumstances, this plane may not contain the
00304   // original location of the point.
00305   bool moveCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
00306 
00307   // Remove all points
00308   void clear()  {m_poly.clear(); m_orient = _Poly2Orient<dim>();}
00309 
00310   // Movement functions
00311 
00312   Polygon& shift(const Vector<dim>& v)
00313         {m_orient.shift(v); return *this;}
00314   Polygon& moveCornerTo(const Point<dim>& p, int corner)
00315         {return shift(p - getCorner(corner));}
00316   Polygon& moveCenterTo(const Point<dim>& p)
00317         {return shift(p - getCenter());}
00318 
00319   Polygon& rotateCorner(const RotMatrix<dim>& m, int corner)
00320         {m_orient.rotate2(m, m_poly[corner]); return *this;}
00321   Polygon& rotateCenter(const RotMatrix<dim>& m)
00322         {if(m_poly.numCorners() > 0)
00323                 m_orient.rotate2(m, m_poly.getCenter());
00324          return *this;}
00325   Polygon& rotatePoint(const RotMatrix<dim>& m, const Point<dim>& p)
00326         {m_orient.rotate(m, p); return *this;}
00327 
00328   // Intersection functions
00329 
00330   AxisBox<dim> boundingBox() const;
00331   Ball<dim> boundingSphere() const;
00332   Ball<dim> boundingSphereSloppy() const;
00333 
00334   friend bool Intersect<dim>(const Polygon& r, const Point<dim>& p, bool proper);
00335   friend bool Contains<dim>(const Point<dim>& p, const Polygon& r, bool proper);
00336 
00337   friend bool Intersect<dim>(const Polygon& p, const AxisBox<dim>& b, bool proper);
00338   friend bool Contains<dim>(const Polygon& p, const AxisBox<dim>& b, bool proper);
00339   friend bool Contains<dim>(const AxisBox<dim>& b, const Polygon& p, bool proper);
00340 
00341   friend bool Intersect<dim>(const Polygon& p, const Ball<dim>& b, bool proper);
00342   friend bool Contains<dim>(const Polygon& p, const Ball<dim>& b, bool proper);
00343   friend bool Contains<dim>(const Ball<dim>& b, const Polygon& p, bool proper);
00344 
00345   friend bool Intersect<dim>(const Polygon& r, const Segment<dim>& s, bool proper);
00346   friend bool Contains<dim>(const Polygon& p, const Segment<dim>& s, bool proper);
00347   friend bool Contains<dim>(const Segment<dim>& s, const Polygon& p, bool proper);
00348 
00349   friend bool Intersect<dim>(const Polygon& p, const RotBox<dim>& r, bool proper);
00350   friend bool Contains<dim>(const Polygon& p, const RotBox<dim>& r, bool proper);
00351   friend bool Contains<dim>(const RotBox<dim>& r, const Polygon& p, bool proper);
00352 
00353   friend bool Intersect<dim>(const Polygon& p1, const Polygon& p2, bool proper);
00354   friend bool Contains<dim>(const Polygon& outer, const Polygon& inner, bool proper);
00355 
00356  private:
00357 
00358   _Poly2Orient<dim> m_orient;
00359   Polygon<2> m_poly;
00360 };
00361 
00362 } // namespace WFMath
00363 
00364 #include <wfmath/polygon_funcs.h>
00365 
00366 #endif  // WFMATH_POLYGON_H

Generated on Wed May 28 09:20:32 2003 for WFMath by doxygen1.3-rc3