00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
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
00072
00073 bool operator< (const Polygon& p) const;
00074
00075
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
00085
00086
00087
00088
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
00093 void removeCorner(int i) {m_points.erase(m_points.begin() + i);}
00094
00095
00096 bool moveCorner(int i, const Point<2>& p, double epsilon = WFMATH_EPSILON)
00097 {m_points[i] = p; return true;}
00098
00099
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
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
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
00163
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
00174
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
00199
00200
00201
00202 template<const int dim>
00203 int _Intersect(const _Poly2Orient<dim> &, const _Poly2Orient<dim> &,
00204 _Poly2OrientIntersectData &);
00205
00206
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
00218 Point<dim> convert(const Point<2>& p) const;
00219
00220
00221
00222
00223 bool expand(const Point<dim>& pd, Point<2>& p2, double epsilon = WFMATH_EPSILON);
00224
00225
00226
00227
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
00233 void rotate2(const RotMatrix<dim>& m, const Point<2>& p);
00234
00235
00236
00237 Vector<dim> offset(const Point<dim>& pd, Point<2>& p2) const;
00238
00239
00240 bool checkContained(const Point<dim>& pd, Point<2> & p2) const;
00241
00242
00243
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
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];
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
00281
00282 bool operator< (const Polygon& p) const;
00283
00284
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
00292
00293
00294
00295
00296 bool addCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
00297
00298
00299 void removeCorner(int i);
00300
00301
00302
00303
00304
00305 bool moveCorner(int i, const Point<dim>& p, double epsilon = WFMATH_EPSILON);
00306
00307
00308 void clear() {m_poly.clear(); m_orient = _Poly2Orient<dim>();}
00309
00310
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
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 }
00363
00364 #include <wfmath/polygon_funcs.h>
00365
00366 #endif // WFMATH_POLYGON_H