36 #ifndef VIGRA_POLYGON_HXX
37 #define VIGRA_POLYGON_HXX
45 #include "array_vector.hxx"
55 template <
class Po
int >
56 bool sortPoints(Point
const & p1, Point
const & p2)
58 return (p1[0]<p2[0]) || (p1[0] == p2[0] && p1[1] < p2[1]);
61 template <
class Po
int >
62 bool orderedClockwise(
const Point &O,
const Point &A,
const Point &B)
64 return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]) <= 0;
82 template<
class Po
intArray1,
class Po
intArray2>
83 void convexHull(
const PointArray1 &points, PointArray2 & convex_hull)
85 vigra_precondition(points.size() >= 2,
86 "convexHull(): at least two input points are needed.");
87 vigra_precondition(points[0].size() == 2,
88 "convexHull(): 2-dimensional points required.");
90 typedef typename PointArray1::value_type Point;
93 std::sort(ordered.begin(), ordered.end(), detail::sortPoints<Point>);
97 int n = points.
size(), k=0;
100 for (
int i = 0; i < n; i++)
102 while (k >= 2 && detail::orderedClockwise(H[k-2], H[k-1], ordered[i]))
107 H.push_back(ordered[i]);
112 for (
int i = n-2, t = k+1; i >= 0; i--)
114 while (k >= t && detail::orderedClockwise(H[k-2], H[k-1], ordered[i]))
119 H.push_back(ordered[i]);
123 std::copy(H.
begin(), H.
begin()+k, std::back_inserter(convex_hull));
const_iterator begin() const
Definition: array_vector.hxx:223
Definition: array_vector.hxx:58
size_type size() const
Definition: array_vector.hxx:330
void convexHull(const PointArray1 &points, PointArray2 &convex_hull)
Compute convex hull of a 2D polygon.
Definition: polygon.hxx:83