[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
vigra/polygon.hxx | ![]() |
00001 /************************************************************************/ 00002 /* */ 00003 /* Copyright 1998-2010 by Ullrich Koethe */ 00004 /* */ 00005 /* This file is part of the VIGRA computer vision library. */ 00006 /* The VIGRA Website is */ 00007 /* http://hci.iwr.uni-heidelberg.de/vigra/ */ 00008 /* Please direct questions, bug reports, and contributions to */ 00009 /* ullrich.koethe@iwr.uni-heidelberg.de or */ 00010 /* vigra@informatik.uni-hamburg.de */ 00011 /* */ 00012 /* Permission is hereby granted, free of charge, to any person */ 00013 /* obtaining a copy of this software and associated documentation */ 00014 /* files (the "Software"), to deal in the Software without */ 00015 /* restriction, including without limitation the rights to use, */ 00016 /* copy, modify, merge, publish, distribute, sublicense, and/or */ 00017 /* sell copies of the Software, and to permit persons to whom the */ 00018 /* Software is furnished to do so, subject to the following */ 00019 /* conditions: */ 00020 /* */ 00021 /* The above copyright notice and this permission notice shall be */ 00022 /* included in all copies or substantial portions of the */ 00023 /* Software. */ 00024 /* */ 00025 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */ 00026 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */ 00027 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */ 00028 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */ 00029 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */ 00030 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */ 00031 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */ 00032 /* OTHER DEALINGS IN THE SOFTWARE. */ 00033 /* */ 00034 /************************************************************************/ 00035 00036 #ifndef VIGRA_POLYGON_HXX 00037 #define VIGRA_POLYGON_HXX 00038 00039 #include <cmath> 00040 #include <cstdlib> 00041 #include <iterator> 00042 #include <algorithm> 00043 #include "config.hxx" 00044 #include "error.hxx" 00045 #include "array_vector.hxx" 00046 00047 namespace vigra { 00048 00049 /** \addtogroup MathFunctions 00050 */ 00051 //@{ 00052 00053 namespace detail { 00054 00055 template < class Point > 00056 bool sortPoints(Point const & p1, Point const & p2) 00057 { 00058 return (p1[0]<p2[0]) || (p1[0] == p2[0] && p1[1] < p2[1]); 00059 } 00060 00061 template < class Point > 00062 bool orderedClockwise(const Point &O, const Point &A, const Point &B) 00063 { 00064 return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]) <= 0; 00065 } 00066 00067 } // namespace detail 00068 00069 00070 /** \brief Compute convex hull of a 2D polygon. 00071 00072 The input array \a points contains a (not necessarily ordered) set of 2D points 00073 whose convex hull is to be computed. The array's <tt>value_type</tt> (i.e. the point type) 00074 must be compatible with std::vector (in particular, it must support indexing, 00075 copying, and have <tt>size() == 2</tt>). The points of the convex hull will be appended 00076 to the output array \a convex_hull (which must support <tt>std::back_inserter(convex_hull)</tt>). 00077 Since the convex hull is a closed polygon, the first and last point of the output will 00078 be the same (i.e. the first point will simply be inserted at the end again). The points 00079 of the convex hull will be ordered counter-clockwise, starting with the leftmost point 00080 of the input. The function implements Andrew's Monotone Chain algorithm. 00081 */ 00082 template<class PointArray1, class PointArray2> 00083 void convexHull(const PointArray1 &points, PointArray2 & convex_hull) 00084 { 00085 vigra_precondition(points.size() >= 2, 00086 "convexHull(): at least two input points are needed."); 00087 vigra_precondition(points[0].size() == 2, 00088 "convexHull(): 2-dimensional points required."); 00089 00090 typedef typename PointArray1::value_type Point; 00091 00092 ArrayVector<Point> ordered(points.begin(), points.end()); 00093 std::sort(ordered.begin(), ordered.end(), detail::sortPoints<Point>); 00094 00095 ArrayVector<Point> H; 00096 00097 int n = points.size(), k=0; 00098 00099 // Build lower hull 00100 for (int i = 0; i < n; i++) 00101 { 00102 while (k >= 2 && detail::orderedClockwise(H[k-2], H[k-1], ordered[i])) 00103 { 00104 H.pop_back(); 00105 --k; 00106 } 00107 H.push_back(ordered[i]); 00108 ++k; 00109 } 00110 00111 // Build upper hull 00112 for (int i = n-2, t = k+1; i >= 0; i--) 00113 { 00114 while (k >= t && detail::orderedClockwise(H[k-2], H[k-1], ordered[i])) 00115 { 00116 H.pop_back(); 00117 --k; 00118 } 00119 H.push_back(ordered[i]); 00120 ++k; 00121 } 00122 00123 std::copy(H.begin(), H.begin()+k, std::back_inserter(convex_hull)); 00124 } 00125 00126 //@} 00127 00128 } // namespace vigra 00129 00130 #endif /* VIGRA_POLYGON_HXX */
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|