cp-algo/geometry/convex_hull.hpp

• View this file on GitHub
• Last update: 2024-06-11 01:57:14+02:00
• Include: #include "cp-algo/geometry/convex_hull.hpp"

Depends on

• cp-algo/geometry/point.hpp
• cp-algo/random/rng.hpp

Verified with

• Static Convex Hull (verify/geometry/hull.test.cpp)

Code

#ifndef CP_ALGO_GEOMETRY_CONVEX_HULL_HPP
#define CP_ALGO_GEOMETRY_CONVEX_HULL_HPP
#include "point.hpp"
#include <algorithm>
#include <utility>
#include <vector>
#include <ranges>
namespace cp_algo::geometry {
    template<typename ftype>
    std::vector<point_t<ftype>> convex_hull(std::vector<point_t<ftype>> r) {
        using point = point_t<ftype>;
        std::ranges::sort(r);
        if(size(r) <= 1 || r[0] == r.back()) {
            return empty(r) ? r : std::vector{r[0]};
        }
        std::vector<point> hull = {r[0]};
        for(int half: {0, 1}) {
            size_t base = size(hull);
            for(auto it: std::views::drop(r, 1)) {
                while(size(hull) >= base + 1) {
                    point a = hull.back();
                    if(point::ccw(it - a, end(hull)[-2] - a)) {
                        break;
                    } else {
                        hull.pop_back();
                    }
                }
                hull.push_back(it);
            }
            std::ranges::reverse(r);
            std::ignore = half;
        }
        hull.pop_back();
        return hull;
    }
}
#endif // CP_ALGO_GEOMETRY_CONVEX_HULL_HPP

#line 1 "cp-algo/geometry/convex_hull.hpp"


#line 1 "cp-algo/geometry/point.hpp"


#line 1 "cp-algo/random/rng.hpp"


#include <chrono>
#include <random>
namespace cp_algo::random {
    uint64_t rng() {
        static std::mt19937_64 rng(
            std::chrono::steady_clock::now().time_since_epoch().count()
        );
        return rng();
    }
}

#line 4 "cp-algo/geometry/point.hpp"
#include <iostream>
#include <complex>
namespace cp_algo::geometry {
    template<typename ftype>
    struct point_t: public std::complex<ftype> {
        using Base = std::complex<ftype>;
        using Base::Base;

        point_t(Base const& t): Base(t) {}
        
        auto operator <=> (point_t const& t) const {
            return std::pair{y(), -x()} <=> std::pair{t.y(), -t.x()};
        }

        ftype x() const {return Base::real();}
        ftype y() const {return Base::imag();}

        point_t cmul(point_t const& t) const {return conj(*this) * t;}
        ftype dot(point_t const& t) const {return cmul(t).x();}
        ftype cross(point_t const& t) const {return cmul(t).y();}

        static constexpr point_t O = {0, 0};

        int half() const {
            return *this < O ? -1 : *this == O ? 0 : 1;
        }

        static bool ccw(point_t const& a, point_t const& b) {
            return a.cross(b) > 0;
        }
        static bool ccw_abs(point_t const& a, point_t const & b) {
            return std::tuple{a.half(), (ftype)0, norm(a)} <
                   std::tuple{b.half(), a.cross(b), norm(b)};
        }
        void read() {
            ftype _x, _y;
            std::cin >> _x >> _y;
            *this = {_x, _y};
        }
        void print() const {
            std::cout << x() << ' ' << y() << "\n";
        }
    };
}

#line 4 "cp-algo/geometry/convex_hull.hpp"
#include <algorithm>
#include <utility>
#include <vector>
#include <ranges>
namespace cp_algo::geometry {
    template<typename ftype>
    std::vector<point_t<ftype>> convex_hull(std::vector<point_t<ftype>> r) {
        using point = point_t<ftype>;
        std::ranges::sort(r);
        if(size(r) <= 1 || r[0] == r.back()) {
            return empty(r) ? r : std::vector{r[0]};
        }
        std::vector<point> hull = {r[0]};
        for(int half: {0, 1}) {
            size_t base = size(hull);
            for(auto it: std::views::drop(r, 1)) {
                while(size(hull) >= base + 1) {
                    point a = hull.back();
                    if(point::ccw(it - a, end(hull)[-2] - a)) {
                        break;
                    } else {
                        hull.pop_back();
                    }
                }
                hull.push_back(it);
            }
            std::ranges::reverse(r);
            std::ignore = half;
        }
        hull.pop_back();
        return hull;
    }
}

Back to top page