polygon.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <span>
#include <vector>
 
#include "point.hpp"
 
namespace recti {
 
    template <typename T> class Polygon {
      private:
        Point<T> _origin{};
        std::vector<Vector2<T>> _vecs{};
 
      public:
        constexpr Polygon() = default;
 
        constexpr Polygon(Point<T> origin, std::vector<Vector2<T>> vecs)
            : _origin{std::move(origin)}, _vecs{std::move(vecs)} {}
 
        explicit constexpr Polygon(std::span<const Point<T>> pointset) : _origin{pointset.front()} {
            if (pointset.size() <= 1) return;
            _vecs.reserve(pointset.size() - 1);
            for (auto it = pointset.begin() + 1; it != pointset.end(); ++it) {
                _vecs.emplace_back(*it - _origin);
            }
        }
 
        constexpr bool operator==(const Polygon& rhs) const {
            return _origin == rhs._origin && _vecs == rhs._vecs;
        }
 
        constexpr bool operator!=(const Polygon& rhs) const { return !(*this == rhs); }
 
        constexpr auto operator+=(const Vector2<T>& rhs) -> Polygon& {
            this->_origin += rhs;
            return *this;
        }
 
        constexpr auto operator-=(const Vector2<T>& rhs) -> Polygon& {
            this->_origin -= rhs;
            return *this;
        }
 
        constexpr auto signed_area_x2() const -> T {
            if (_vecs.size() < 2) return T{0};
 
            T res = _vecs[0].x() * _vecs[1].y() - _vecs.back().x() * _vecs[_vecs.size() - 2].y();
            for (size_t i = 1; i < _vecs.size() - 1; ++i) {
                res += _vecs[i].x() * (_vecs[i + 1].y() - _vecs[i - 1].y());
            }
            return res;
        }
 
        constexpr const Point<T>& origin() const { return _origin; }
 
        constexpr const std::vector<Vector2<T>>& vectors() const { return _vecs; }
 
        constexpr auto vertices() const -> std::vector<Point<T>> {
            std::vector<Point<T>> result;
            result.reserve(_vecs.size() + 1);
            result.emplace_back(_origin);
            for (const auto& vec : _vecs) {
                result.emplace_back(_origin + vec);
            }
            return result;
        }
 
        constexpr auto is_rectilinear() const -> bool {
            if (_vecs.empty()) return true;
 
            // Check from origin (0,0) to first vec
            if (_vecs[0].x() != 0 && _vecs[0].y() != 0) return false;
 
            // Check consecutive vecs directly (no vector allocation)
            for (size_t i = 0; i < _vecs.size() - 1; ++i) {
                if (_vecs[i].x() != _vecs[i + 1].x() && _vecs[i].y() != _vecs[i + 1].y()) {
                    return false;
                }
            }
 
            // Check closing: last vec back to origin (0,0)
            if (_vecs.back().x() != 0 && _vecs.back().y() != 0) return false;
 
            return true;
        }
 
        constexpr auto is_convex() const -> bool {
            if (_vecs.size() < 2) return false;
            if (_vecs.size() == 2) return true;
 
            // pointset[i] maps to: _vecs[i-1] for i>0, or (0,0) for i=0
            // cross_product_sign uses _vecs[N-2] and _vecs[0]
            T cross_product_sign = -_vecs[_vecs.size() - 2].x() * _vecs[0].y()
                                   + _vecs[_vecs.size() - 2].y() * _vecs[0].x();
 
            for (size_t i = 0; i < _vecs.size() - 1; ++i) {
                auto v0 = (i == 0) ? Vector2<T>(0, 0) : _vecs[i - 1];
                const auto& v1 = _vecs[i];
                const auto& v2 = _vecs[i + 1];
 
                T current_cross
                    = (v1.x() - v0.x()) * (v2.y() - v1.y()) - (v1.y() - v0.y()) * (v2.x() - v1.x());
 
                if ((cross_product_sign > 0) != (current_cross > 0)) {
                    return false;
                }
            }
 
            return true;
        }
    };
 
    template <typename FwIter> auto create_xmono_polygon(FwIter first, FwIter last) -> void;
 
    template <typename FwIter> auto create_ymono_polygon(FwIter first, FwIter last) -> void;
 
    template <typename T, typename DirFunc>
    auto polygon_is_monotone(std::span<const Point<T>> pointset, const DirFunc& dir) -> bool;
 
    template <typename T> auto polygon_is_xmonotone(std::span<const Point<T>> pointset) -> bool;
 
    template <typename T> auto polygon_is_ymonotone(std::span<const Point<T>> pointset) -> bool;
 
    template <typename T>
    auto point_in_polygon(std::span<const Point<T>> pointset, const Point<T>& ptq) -> bool;
 
    template <typename T> auto polygon_is_anticlockwise(std::span<const Point<T>> pointset) -> bool;
}  // namespace recti