[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
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 struct CCWCompare 00057 { 00058 Point p0_; 00059 CCWCompare(const Point &p0) 00060 : p0_(p0) 00061 {} 00062 00063 bool operator()(const Point &a, const Point &b) const 00064 { 00065 return (a[1]-p0_[1])*(b[0]-p0_[0]) - (a[0]-p0_[0])*(b[1]-p0_[1]) < 0; 00066 } 00067 }; 00068 00069 } // namespace detail 00070 00071 00072 /** \brief Compute convex hull of a 2D polygon. 00073 00074 The input array \a points contains a (not necessarily ordered) set of 2D points 00075 whose convex hull is to be computed. The array's <tt>value_type</tt> (i.e. the point type) 00076 must be compatible with std::vector (in particular, it must support indexing, 00077 copying, and have <tt>size() == 2</tt>). The points of the convex hull will be appended 00078 to the output array \a convex_hull (which must support <tt>std::back_inserter(convex_hull)</tt>). 00079 Since the convex hull is a closed polygon, the first and last point of the output will 00080 be the same (i.e. the first point will simply be inserted at the end again). The points 00081 of the convex hull will be ordered counter-clockwise, starting with the leftmost point 00082 of the imput. 00083 */ 00084 template<class PointArray1, class PointArray2> 00085 void convexHull( 00086 const PointArray1 &points, PointArray2 &convex_hull) 00087 { 00088 vigra_precondition(points.size() >= 2, 00089 "convexHull(): at least two input points are needed."); 00090 vigra_precondition(points[0].size() == 2, 00091 "convexHull(): 2-dimensional points required."); 00092 00093 typedef typename PointArray1::value_type Point; 00094 typedef typename Point::value_type Coordinate; 00095 00096 // find extremal point (min. x, then min. y): 00097 unsigned int i0 = 0; 00098 Point p0 = points[0]; 00099 for(unsigned int i = 1; i < points.size(); ++i) 00100 { 00101 Coordinate xDiff = points[i][0] - p0[0]; 00102 if(xDiff < 0 || (xDiff == 0 && points[i][1] < p0[1])) 00103 { 00104 p0 = points[i]; 00105 i0 = i; 00106 } 00107 } 00108 00109 // sort other points by angle from p0: 00110 ArrayVector<Point> other(points.begin(), points.begin() + i0); 00111 other.insert(other.end(), points.begin()+i0+1, points.end()); 00112 00113 // the current definition of CCWCompare ensures that points identical to p0 00114 // end up at the end of the list => those duplicates will be removed during 00115 // Graham scan 00116 std::sort(other.begin(), other.end(), detail::CCWCompare<Point>(p0)); 00117 00118 ArrayVector<Point> result(points.size()+1); 00119 result[0] = p0; 00120 result[1] = other[0]; 00121 00122 typename ArrayVector<Point>::iterator currentEnd = result.begin() + 1; 00123 00124 // Graham's scan: 00125 Point endSegment = *currentEnd - currentEnd[-1]; 00126 Coordinate sa2; 00127 for(unsigned int i = 1; i < other.size(); ++i) 00128 { 00129 if(other[i] == other[i-1] || other[i] == p0) // skip duplicate points 00130 continue; 00131 do 00132 { 00133 Point diff = other[i] - currentEnd[-1]; 00134 sa2 = diff[0]*endSegment[1] - endSegment[0]*diff[1]; 00135 if(sa2 < 0) 00136 { 00137 // point is to the left, add to convex hull: 00138 *(++currentEnd) = other[i]; 00139 endSegment = other[i] - currentEnd[-1]; 00140 } 00141 else if(sa2 == 0) 00142 { 00143 // points are collinear, keep far one: 00144 if(diff.squaredMagnitude() > endSegment.squaredMagnitude()) 00145 { 00146 *currentEnd = other[i]; 00147 endSegment = diff; 00148 } 00149 } 00150 else 00151 { 00152 // point is to the right, backtracking needed: 00153 --currentEnd; 00154 endSegment = *currentEnd - currentEnd[-1]; 00155 } 00156 } 00157 while(sa2 > 0); 00158 } 00159 00160 // return closed Polygon: 00161 *(++currentEnd) = p0; 00162 ++currentEnd; 00163 std::copy(result.begin(), currentEnd, std::back_inserter(convex_hull)); 00164 } 00165 00166 //@} 00167 00168 } // namespace vigra 00169 00170 #endif /* VIGRA_POLYGON_HXX */
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|