poly_ops/base.hpp¶

Concepts¶

template<typename T> concept coordinate¶

Defined as:

detail::arithmetic<T>
&& detail::arithmetic<long_coord_t<T>>
&& detail::arithmetic<real_coord_t<T>>
&& detail::arithmetic_promotes<T,long_coord_t<T>>
&& detail::arithmetic_promotes<T,real_coord_t<T>>
&& std::totally_ordered<T>
&& std::totally_ordered<long_coord_t<T>>
&& std::totally_ordered<real_coord_t<T>>
&& std::convertible_to<T,long_coord_t<T>>
&& std::convertible_to<int,long_coord_t<T>>
&& std::convertible_to<T,real_coord_t<T>>
&& requires(T c,long_coord_t<T> cl,real_coord_t<T> cr) {
    static_cast<long>(c);
    { coord_ops<T>::acos(c) } -> std::same_as<real_coord_t<T>>;
    { coord_ops<T>::acos(cr) } -> std::same_as<real_coord_t<T>>;
    { coord_ops<T>::cos(cr) } -> std::same_as<real_coord_t<T>>;
    { coord_ops<T>::sin(cr) } -> std::same_as<real_coord_t<T>>;
    { coord_ops<T>::sqrt(c) } -> std::same_as<real_coord_t<T>>;
    { coord_ops<T>::sqrt(cr) } -> std::same_as<real_coord_t<T>>;
    { coord_ops<T>::round(cr) } -> std::same_as<T>;
    { coord_ops<T>::ceil(cr) } -> std::same_as<T>;
    { coord_ops<T>::floor(cr) } -> std::same_as<T>;
    { coord_ops<T>::to_coord(cr) } -> std::same_as<T>;
    { coord_ops<T>::pi() } -> std::same_as<real_coord_t<T>>;
    { coord_ops<T>::mul(c,c) } -> std::same_as<long_coord_t<T>>;
    { cr * cr } -> std::convertible_to<real_coord_t<T>>;
    { cr / cr } -> std::convertible_to<real_coord_t<T>>;
    { c * cr } -> std::convertible_to<real_coord_t<T>>;
    { cr * c } -> std::convertible_to<real_coord_t<T>>;
}

where detail::arithmetic<typename T> is:

requires(T x) {
    { x + x } -> std::convertible_to<T>;
    { x - x } -> std::convertible_to<T>;
    { -x } -> std::convertible_to<T>;
}

and detail::arithmetic_promotes<typename Lesser,typename Greater> is:

requires(Lesser a,Greater b) {
    { a + b } -> std::convertible_to<Greater>;
    { b + a } -> std::convertible_to<Greater>;
    { a - b } -> std::convertible_to<Greater>;
    { b - a } -> std::convertible_to<Greater>;
}

template<typename T, typename Coord> concept point_like¶

Defined as:

requires(const T &v) {
    { point_ops<T>::get_x(v) } -> std::convertible_to<Coord>;
    { point_ops<T>::get_y(v) } -> std::convertible_to<Coord>;
}

template<typename T, typename Coord> concept point_range¶

Defined as:

std::ranges::range<T> && point_like<std::ranges::range_value_t<T>,Coord>

template<typename T, typename Coord> concept point_range_range¶

Defined as:

std::ranges::range<T> && point_range<std::ranges::range_value_t<T>,Coord>

template<typename T, typename Coord> concept point_range_or_range_range¶

Defined as:

td::ranges::range<T> && (point_range<std::ranges::range_value_t<T>,Coord>
    || point_like<std::ranges::range_value_t<T>,Coord>)

Types¶

template<typename Coord> using long_coord_t = typename coord_ops<Coord>::long_t¶

template<typename Coord> using real_coord_t = typename coord_ops<Coord>::real_t¶

template<typename T> struct point_ops¶

A struct containing getters for point-like objects. Specializations exist for T[2], std::span<T,2> and point_t<T>. This can be specialized by the user for other types. Static functions get_x and get_y should be defined to get the X and Y coordinates respectively.

Example:

template<> struct poly_ops::point_ops<MyPoint> {
    static int get_x(const MyPoint &p) {
        return static_cast<int>(MyPoint.X * 100.0f);
    }
    static int get_y(const MyPoint &p) {
        return static_cast<int>(MyPoint.Y * 100.0f);
    }
};

template<typename Coord> struct coord_ops¶

Mathematical operations on coordinate types. This struct can be specialized by users of this library. Arithmetic operators should be defined for every permutation of Coord, long_t and real_t. Binary operations with Coord and long_t should return long_t, long_t and real_t should return real_t, and Coord and real_t should return real_t.

Public Types

using long_t = large_ints::sized_int<sizeof(Coord) * 2>¶

Certain operations require multiplying two coordinate values and thus need double the bits of the maximum coordinate value to avoid overflow.

By default, if Coord is a 64 bit type, this is large_ints::compound_int.

This can be specialized as a user-defined type.

using real_t = double¶: The coordinates of generated points are usually not integers. By default, they are represented by double before being rounded back to integers. This type can be specialized to use some custom type for more precision.

Public Static Functions

static inline long_t mul(Coord a, Coord b)¶

Multiply a and b and return the result.

This should be equivalent to static_cast<long_t>(a) * static_cast<long_t>(b), except long_t is not required to support multiplication.

static inline real_t acos(Coord x)¶

Default implementation:

return std::acos(static_cast<real_t>(x));

static inline real_t acos(real_t x)¶

Default implementation:

return static_cast<Coord>(std::acos(x));

static inline real_t cos(real_t x)¶

Default implementation:

return static_cast<Coord>(std::cos(x));

static inline real_t sin(real_t x)¶

Default implementation:

return static_cast<Coord>(std::sin(x));

static inline real_t sqrt(Coord x)¶

Default implementation:

return std::sqrt(static_cast<real_t>(x));

static inline real_t sqrt(real_t x)¶

Default implementation:

return static_cast<Coord>(std::sqrt(x));

static inline Coord round(real_t x)¶

Default implementation:

return static_cast<Coord>(std::lround(x));

static inline Coord floor(real_t x)¶

Default implementation:

return static_cast<Coord>(std::floor(x));

static inline Coord ceil(real_t x)¶

Default implementation:

return static_cast<Coord>(std::ceil(x));

static inline Coord to_coord(real_t x)¶

After determining how many points to use to approximate an arc using real numbers, the value needs to be converted to an integer to use in a loop.

Default implementation:

return static_cast<Coord>(x);

static inline real_t pi()¶

Return the value of pi.

Default implementation:

return std::numbers::pi_v<real_t>;

template<typename T> struct point_t¶

A two-dimensional point or vector

Public Functions

point_t() noexcept = default¶: The default constructor leaves the values uninitialized

inline constexpr point_t(const T &x, const T &y) noexcept(std::is_nothrow_copy_constructible_v<T>)¶

constexpr point_t(const point_t &b) = default¶

template<point_like<T> U> inline constexpr point_t( const U &b, ) noexcept(noexcept(point_t(point_ops::get_x(b), point_ops::get_y(b))))¶: Construct point_t from any point-like object

constexpr point_t &operator=(const point_t &b) noexcept(std::is_nothrow_copy_constructible_v<T>) = default¶

inline constexpr T &operator[](std::size_t i) noexcept¶

inline constexpr const T &operator[](std::size_t i) const noexcept¶

inline constexpr T &x() noexcept¶

inline constexpr const T &x() const noexcept¶

inline constexpr T &y() noexcept¶

inline constexpr const T &y() const noexcept¶

inline constexpr T *begin() noexcept¶

inline constexpr const T *begin() const noexcept¶

inline constexpr T *end() noexcept¶

inline constexpr const T *end() const noexcept¶

inline constexpr std::size_t size() const noexcept¶: Always returns 2

inline constexpr T *data() noexcept¶: Return a pointer to the underlying array

inline constexpr const T *data() const noexcept¶: Return a const pointer to the underlying array

inline constexpr point_t &operator+=(const point_t &b)¶: Element-wise addition.

inline constexpr point_t &operator-=(const point_t &b)¶: Element-wise subtraction.

inline constexpr point_t &operator*=(T b)¶

inline constexpr point_t operator-() const¶

Public Members

T _data[2]¶

Friends

inline friend constexpr void swap(point_t &a, point_t &b) noexcept(std::is_nothrow_swappable_v<T>)¶

template<coordinate Coord> class winding_dir_sink¶

Public Functions

inline winding_dir_sink(point_t<Coord> first)¶

inline void operator()(point_t<Coord> p)¶

inline long_coord_t<Coord> close()¶

Functions¶

template<typename T, typename U> constexpr point_t<std::common_type_t<T, U>> operator+( const point_t<T> &a, const point_t &b, )¶: Element-wise addition.

template<typename T, typename U> constexpr point_t<std::common_type_t<T, U>> operator-( const point_t<T> &a, const point_t &b, )¶: Element-wise subtraction.

template<typename T, typename U> constexpr point_t<std::common_type_t<T, U>> operator*( const point_t<T> &a, const point_t &b, )¶: Element-wise multiplication.

template<typename T, typename U> constexpr point_t<std::common_type_t<T, U>> operator*(const point_t<T> &a, U b)¶: Multiply both elements of a by b and return the result

template<typename T, typename U> constexpr point_t<std::common_type_t<T, U>> operator*(T a, const point_t &b)¶: Multiply both elements of b by a and return the result

template<typename T, typename U> constexpr point_t<std::common_type_t<T, U>> operator/( const point_t<T> &a, const point_t &b, )¶: Element-wise division.

template<typename T> constexpr bool operator==(const point_t<T> &a, const point_t<T> &b)¶

template<typename T> constexpr bool operator!=(const point_t<T> &a, const point_t<T> &b)¶

template<typename T, typename U> constexpr auto vdot(const point_t<T> &a, const point_t &b)¶: Return the dot product of a and b

template<typename T> constexpr T square(const point_t<T> &a)¶: Equivalent to a[0]*a[0] + a[1]*a[1]

template<typename T, typename U> constexpr point_t<T> vcast(const point_t &x)¶: Equivalent to point_t{static_cast<T>(x[0]),static_cast<T>(x[1])}

template<typename Coord> constexpr point_t<Coord> vround(const point_t<real_coord_t<Coord>> &x)¶

template<typename Coord, typename T> constexpr real_coord_t<Coord> vmag(const point_t<T> &x)¶

template<typename Coord, typename T> constexpr real_coord_t<T> vangle(const point_t<T> &a, const point_t<T> &b)¶

template<typename Coord> constexpr long_coord_t<Coord> triangle_winding( const point_t<Coord> &p1, const point_t<Coord> &p2, const point_t<Coord> &p3, )¶: Returns a positive number if the triangle formed by the given points is clockwise, negative if counter-clockwise and zero if degenerate

template<coordinate Coord, point_range<Coord> Points> long_coord_t<Coord> winding_dir(Points &&points)¶

Returns a positive number if mostly clockwise, negative if mostly counter-clockwise and zero if degenerate or exactly half of the polygon’s area is inverted.

This algorithm works on any polygon. For non-overlapping non-inverting polygons, more efficient methods exist.