iLab Neuromorphic Robotics Toolkit  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Polygon.H
Go to the documentation of this file.
1 /*! @file
2  @author Randolph Voorhies
3  @copyright GNU Public License (GPL v3)
4  @section License
5  @verbatim
6  // ////////////////////////////////////////////////////////////////////////
7  // The iLab Neuromorphic Robotics Toolkit (NRT) //
8  // Copyright 2010-2012 by the University of Southern California (USC) //
9  // and the iLab at USC. //
10  // //
11  // iLab - University of Southern California //
12  // Hedco Neurociences Building, Room HNB-10 //
13  // Los Angeles, Ca 90089-2520 - USA //
14  // //
15  // See http://ilab.usc.edu for information about this project. //
16  // ////////////////////////////////////////////////////////////////////////
17  // This file is part of The iLab Neuromorphic Robotics Toolkit. //
18  // //
19  // The iLab Neuromorphic Robotics Toolkit is free software: you can //
20  // redistribute it and/or modify it under the terms of the GNU General //
21  // Public License as published by the Free Software Foundation, either //
22  // version 3 of the License, or (at your option) any later version. //
23  // //
24  // The iLab Neuromorphic Robotics Toolkit is distributed in the hope //
25  // that it will be useful, but WITHOUT ANY WARRANTY; without even the //
26  // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR //
27  // PURPOSE. See the GNU General Public License for more details. //
28  // //
29  // You should have received a copy of the GNU General Public License //
30  // along with The iLab Neuromorphic Robotics Toolkit. If not, see //
31  // <http://www.gnu.org/licenses/>. //
32  // ////////////////////////////////////////////////////////////////////////
33  @endverbatim */
34 
35 
36 #ifndef INCLUDE_NRT_CORE_GEOMETRY_POLYGON_H
37 #define INCLUDE_NRT_CORE_GEOMETRY_POLYGON_H
38 
42 #include <nrt/External/cereal/types/vector.hpp>
43 
44 #include <deque>
45 #include <algorithm>
46 
47 namespace nrt
48 {
49  //! A 2D polygon representation
50  /*! \ingroup geometry */
51  template<class T>
52  class Polygon
53  {
54  public:
55  //! Default constructor - creates an empty polygon
56  Polygon();
57 
58  //! Create a polygon with the given vertices
59  explicit Polygon(std::vector<Point2D<T> > const & vertices);
60 
61  //! Create a polygon from a list of vertices
62  explicit Polygon(std::initializer_list<Point2D<T> > list);
63 
64  //! Create a polygon with the given vertices of a different datatype
65  /*! This internally will use nrt::clamped_convert<T,U> on each vertex */
66  template <class U>
67  Polygon(std::vector<Point2D<U> > const & vertices);
68 
69  //! Copy constructor
70  Polygon(Polygon<T> const & other);
71 
72  //! Move constructor
73  Polygon(Polygon<T> && other);
74 
75  Polygon<T> & operator=(Polygon<T> const & other);
76 
77  //! Create a polygon with the given vertices of a different datatype
78  /*! This internally will use nrt::clamped_convert<T,U> on each vertex */
79  template <class U>
80  explicit Polygon(Polygon<U> const & other);
81 
82  //! Get a copy the vertices
83  std::vector<Point2D<T> > const & vertices() const;
84 
85  //! Get the size (number of vertices)
86  size_t size() const;
87 
88  //! Access one vertex, read/write version
89  Point2D<T> & vertex(size_t index);
90 
91  //! Access one vertex, read-only version
92  Point2D<T> const & vertex(size_t index) const;
93 
94  //! Access the beginning of the underlying vector of vertices
95  typename std::vector<Point2D<T> >::iterator begin();
96 
97  //! Access the end of the underlying vector of vertices
98  typename std::vector<Point2D<T> >::iterator end();
99 
100  //! Access the beginning of the underlying vector of vertices - const version
101  typename std::vector<Point2D<T> >::const_iterator begin() const;
102 
103  //! Access the end of the underlying vector of vertices - const version
104  typename std::vector<Point2D<T> >::const_iterator end() const;
105 
106  //! Get the location of the center of the polygon's vertices
107  /*! @tparam promo defines how the coordinates get promoted over type T internally during our computations. If T is
108  a floating point type, then promo = void is fine, unless you need more precision (e.g., promo is double if
109  T is float). If T is an integer type, you should typically choose float or double for promo, like this:
110 
111  @code
112  nrt::Polygon<int> poly { ...initialization values... };
113  nrt::Point2D<double> c = poly.center<double>();
114  nrt::Point2D<int> ci(c); // convert coordinates back to integer and round (if needed)
115  @endcode */
116  template <typename promo>
118 
119  //! Get the location of the centroid of the polygon
120  /*! @tparam promo defines how the coordinates get promoted over type T internally during our computations. If T is
121  a floating point type, then promo = void is fine, unless you need more precision (e.g., promo is double if
122  T is float). If T is an integer type, you should typically choose float or double for promo, like this:
123 
124  @code
125  nrt::Polygon<int> poly { ...initialization values... };
126  nrt::Point2D<double> c = poly.centroid<double>();
127  nrt::Point2D<int> ci(c); // convert coordinates back to integer and round (if needed)
128  @endcode */
129  template <typename promo>
131 
132  //! Get the area of the polygon
133  /*! \pre The polygon must be simple (non-self-intersecting) */
134  double area(const bool getsigned = false) const;
135 
136  //! Detect whether the given point lies inside the polygon
137  template <class U>
138  bool contains(Point2D<U> const & point) const;
139 
140  //! Compute the bounding Rectangle around this Polygon
141  Rectangle<T> boundingRect() const;
142 
143  //! Compute convex hull of this polygon
144  /*! This algorithm is taken from Melkman, et al. 1985. Online Construction of the convex hull of a simple
145  polyline
146 
147  \pre The polygon must be non-intersecting for this method to work correctly. If you do not know whether or
148  not your polygon is non-intersecting or not, you should use Polygon<T>::convexHull instead. */
149  Polygon<T> toConvex() const;
150 
151  //! Compute the convex hull around an unsorted collection of points
152  /*! This is an implementation of the method described in "Another Efficient Algorithm for Convex Hulls in Two
153  Dimensions" Andrew, 1979.
154 
155  This method is fairly fast, as it's runtime is generally bounded by the time needed
156  to sort the given points in increasing x then y coordinates, which is O(n logn).
157 
158  \param points An unsorted collection of points around which to find an exact convex hull
159 
160  \copyright Copyright 2001, softSurfer (www.softsurfer.com) This code may be freely used and modified for any
161  purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this
162  code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code
163  must verify correctness for their application. */
164  static Polygon<T> convexHull(std::vector<Point2D<T> > const & points);
165 
166  //! Compute the approximate convex hull around an unsorted collection of points
167  /*! This is an implementation of the method described in "Approximation Algorithms for Convex Hulls" Bently,
168  Faust & Preparata 1982.
169 
170  This method is very fast, as it's runtime is O(n). The algorithm works by breaking the point group
171  into vertical strips, computing the extrema points in each strip, and then finding the convex hull
172  around those extrema points.
173 
174  \param points An unsorted collection of points around which to find an approximate convex hull
175  \param accuracy The number of vertical strips to break the point group into. The more strips,
176  the closer the approximation is to a true convex hull.
177 
178  \copyright Copyright 2001, softSurfer (www.softsurfer.com) This code may be freely used and modified for any
179  purpose providing that this copyright notice is included with it. SoftSurfer makes no warranty for this
180  code, and cannot be held liable for any real or imagined damage resulting from its use. Users of this code
181  must verify correctness for their application. */
182  static Polygon<T> approximateConvexHull(std::vector<Point2D<T> > const & points, int accuracy = 30);
183 
184  protected:
185  friend class cereal::access;
186 
187  //! Serialization
188  template <class Archive>
189  void serialize(Archive & ar)
190  {
191  ar( itsVertices );
192  }
193 
194  private:
195  std::vector<Point2D<T> > itsVertices;
196  };
197 
198  // ######################################################################
199  // Free functions for Polygon<T>
200  // ######################################################################
201 
202  //! Human-readable output to a stream: outputs {(x1,y1)(x2,y2)...(xN,yN)}
203  /*! \relates Polygon */
204  template <class T>
205  std::ostream& operator<<(std::ostream &out, Polygon<T> const& poly);
206 
207  //! Return a scaled version of the source object
208  /*! \note This does \e not have the same effect as the multiplication or division operators, which scale everything,
209  while here we only scale the object size without scaling its center coordinates.
210  \relates Polygon */
211  template <class T>
212  Polygon<T> scale(Polygon<T> const & src, double const factor);
213 
214  //! Return a rotated version of the source object, about its center by a given angle in radians
215  /*! \relates Polygon */
216  template <class T>
217  Polygon<T> rotate(Polygon<T> const & src, double const angle);
218 
219  //! Return a rotated version of the source object, about the given point and by a given angle in radians
220  /*! \relates Polygon */
221  template <class T>
222  Polygon<T> rotateAbout(Polygon<T> const & src, Point2D<T> const & p, double const angle);
223 
224  //! Operator overload for Polygon<T> == Polygon<T>
225  /*! \relates Polygon */
226  template <class T>
227  bool operator==(Polygon<T> const & lhs, Polygon<T> const & rhs);
228 
229  //! Operator overload for Polygon<T> != Polygon<T>
230  /*! \relates Polygon */
231  template <class T>
232  bool operator!=(Polygon<T> const & lhs, Polygon<T> const & rhs);
233 
234  //! Operator overload for Polygon<T> + Point2D<T>
235  /*! \relates Polygon */
236  template <class T>
237  Polygon<T> operator+(Polygon<T> const & lhs, Point2D<T> const & rhs);
238 
239  //! Operator overload for Point2D<T> + Polygon<T>
240  /*! \relates Polygon */
241  template <class T>
242  Polygon<T> operator+(Point2D<T> const & lhs, Polygon<T> const & rhs);
243 
244  //! Operator overload for Polygon<T> - Point2D<T>
245  /*! \relates Polygon */
246  template <class T>
247  Polygon<T> operator-(Polygon<T> const & lhs, nrt::Point2D<T> const & rhs);
248 
249  //! Operator overload for Point2D<T> - Polygon<T>
250  /*! \relates Polygon */
251  template <class T>
252  Polygon<T> operator-(Point2D<T> const & lhs, Polygon<T> const & rhs);
253 
254  //! Operator overload for Polygon<T> * double
255  /*! \relates Polygon */
256  template <class T>
257  Polygon<T> operator*(Polygon<T> const & lhs, double const rhs);
258 
259  //! Operator overload for double * Polygon<T>
260  /*! \relates Polygon */
261  template <class T>
262  Polygon<T> operator*(double const lhs, Polygon<T> const & rhs);
263 
264  //! Operator overload for Polygon<T> / double
265  /*! \relates Polygon */
266  template <class T>
267  Polygon<T> operator/(Polygon<T> const & lhs, double const rhs);
268 
269  //! Operator overload for Polygon<T> *= double
270  /*! \relates Polygon */
271  template <class T>
272  Polygon<T> & operator*=(Polygon<T> & lhs, double const rhs);
273 
274  //! Operator overload for Polygon<T> /= double
275  /*! \relates Polygon */
276  template <class T>
277  Polygon<T> & operator/=(Polygon<T> & lhs, double const rhs);
278 
279  //! Operator overload for Polygon<T> += Point2D<T>
280  /*! \relates Polygon */
281  template <class T>
282  Polygon<T> & operator+=(Polygon<T> & lhs, Point2D<T> const & rhs);
283 
284  //! Operator overload for Polygon<T> -= Point2D<T>
285  /*! \relates Polygon */
286  template <class T>
287  Polygon<T> & operator-=(Polygon<T> & lhs, Point2D<T> const & rhs);
288 }
289 
290 // Include inlined implementation details that are of no interest to the end user
292 
293 // Include explicit instantiations that are of no interest to the end user
295 
296 #endif // INCLUDE_NRT_CORE_GEOMETRY_POLYGON_H
297