1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#pragma once


#include <vector><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <iterator><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <ranges><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.


#include "internal/dev_env.hpp"

#include "geometry/point.hpp"
#include "geometry/polygon.hpp"



namespace uni {


template<class Point, class Container>
template<bool ALLOW_LINE, bool LEAVE_MARGIN>
auto polygon<Point, Container>::convex_hull() noexcept(NO_EXCEPT) {
    auto remove = [&](const point_type& p, const point_type& q, const point_type& r) -> bool {
        if constexpr(ALLOW_LINE) {
            return compare(cross(p, q, r)) < 0;
        }
        else {
            return compare(cross(p, q, r)) <= 0;
        }
    };

    std::vector<point_type> points(ALL(*this));

    const auto n = std::ranges::ssize(points);
    using ssize_type = std::remove_const_t<decltype(n)>;

    std::ranges::sort(points);

    polygon res(2 * n);
    ssize_type k = 0;

    for(ssize_type i = 0; i < n; res[k++] = points[i++]) {
        while(k >= 2 && remove(points[i], res[k - 2], res[k - 1])) --k;
    }
    for(auto i = n - 2, t = k + 1; i >= 0; res[k++] = points[i--]) {
        while(k >= t && remove(points[i], res[k - 2], res[k - 1])) --k;
    }

    if constexpr(LEAVE_MARGIN) res.resize(k);
    else res.resize(k - 1);

    return res;
}


} // namespace uni