36 #ifndef VIGRA_POLYGON_HXX
37 #define VIGRA_POLYGON_HXX
45 #include "array_vector.hxx"
59 CCWCompare(
const Point &p0)
63 bool operator()(
const Point &a,
const Point &b)
const
65 return (a[1]-p0_[1])*(b[0]-p0_[0]) - (a[0]-p0_[0])*(b[1]-p0_[1]) < 0;
84 template<
class Po
intArray1,
class Po
intArray2>
86 const PointArray1 &points, PointArray2 &convex_hull)
88 vigra_precondition(points.size() >= 2,
89 "convexHull(): at least two input points are needed.");
90 vigra_precondition(points[0].size() == 2,
91 "convexHull(): 2-dimensional points required.");
93 typedef typename PointArray1::value_type Point;
94 typedef typename Point::value_type Coordinate;
99 for(
unsigned int i = 1; i < points.size(); ++i)
101 Coordinate xDiff = points[i][0] - p0[0];
102 if(xDiff < 0 || (xDiff == 0 && points[i][1] < p0[1]))
111 other.insert(other.end(), points.begin()+i0+1, points.end());
116 std::sort(other.begin(), other.end(), detail::CCWCompare<Point>(p0));
120 result[1] = other[0];
122 typename ArrayVector<Point>::iterator currentEnd = result.
begin() + 1;
125 Point endSegment = *currentEnd - currentEnd[-1];
127 for(
unsigned int i = 1; i < other.size(); ++i)
129 if(other[i] == other[i-1] || other[i] == p0)
133 Point diff = other[i] - currentEnd[-1];
134 sa2 = diff[0]*endSegment[1] - endSegment[0]*diff[1];
138 *(++currentEnd) = other[i];
139 endSegment = other[i] - currentEnd[-1];
144 if(diff.squaredMagnitude() > endSegment.squaredMagnitude())
146 *currentEnd = other[i];
154 endSegment = *currentEnd - currentEnd[-1];
161 *(++currentEnd) = p0;
163 std::copy(result.
begin(), currentEnd, std::back_inserter(convex_hull));