21 #ifndef GEOMETRY__CONVEX_HULL_HPP_
22 #define GEOMETRY__CONVEX_HULL_HPP_
52 template<
typename Po
intT,
typename HullT>
55 auto hull_it = hull.cbegin();
56 auto point_it = points.cbegin();
58 const auto iters = points.size();
59 for (
auto idx = decltype(iters) {0}; idx < iters; ++idx) {
62 while ((hull.cbegin() != hull_it) && is_ccw) {
63 const auto current_hull_it = hull_it;
65 is_ccw =
ccw(*hull_it, *current_hull_it, *point_it);
67 hull_it = current_hull_it;
71 points.splice(points.end(), hull, current_hull_it);
73 const auto last_point_it = point_it;
76 hull.splice(hull.end(), points, last_point_it);
78 hull_it = last_point_it;
90 template<
typename Po
intT,
typename HullT>
94 auto hull_it = hull.cend();
96 const auto lower_hull_end = hull_it;
97 auto point_it = points.cend();
100 const auto iters = points.size();
101 for (
auto idx = decltype(iters) {0}; idx < iters; ++idx) {
104 while ((lower_hull_end != hull_it) && is_ccw) {
105 const auto current_hull_it = hull_it;
107 is_ccw =
ccw(*hull_it, *current_hull_it, *point_it);
109 hull_it = current_hull_it;
112 points.splice(points.begin(), hull, current_hull_it);
114 const auto last_point_it = point_it;
117 hull.splice(hull.end(), points, last_point_it);
118 hull_it = last_point_it;
132 template<
typename Po
intT>
136 const auto lexical_comparator = [](
const PointT & a,
const PointT & b) ->
bool8_t
140 constexpr
auto FEPS = std::numeric_limits<float32_t>::epsilon();
141 return (fabsf(
x_(a) -
x_(b)) > FEPS) ?
144 list.sort(lexical_comparator);
147 std::list<PointT> tmp_hull_list{list.get_allocator()};
153 list.sort(lexical_comparator);
157 list.splice(list.begin(), tmp_hull_list, tmp_hull_list.begin());
162 const auto ret = list.begin();
164 auto tmp_it = tmp_hull_list.end();
166 list.splice(list.begin(), tmp_hull_list, tmp_it);
168 list.splice(ret, tmp_hull_list);
184 template<
typename Po
intT>
185 typename std::list<PointT>::const_iterator
convex_hull(std::list<PointT> & list)
194 #endif // GEOMETRY__CONVEX_HULL_HPP_