m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: Half-Plane Intersection
(geometry/half_plane_intersection.hpp)

Overview

half_plane_intersection constructs the bounded convex polygon common to a collection of closed half-planes. A half-plane is represented by a directed Line<T>: the legal side is the boundary line and everything to its left.

For a line from a to b, a point p is legal exactly when

\[\operatorname{cross}(b-a,p-a) \geq 0.\]

The result reports whether the intersection is empty, unbounded, bounded with zero area, or a bounded positive-area polygon. Polygon vertices use long double because intersections need not have integral coordinates.

Result

enum class HalfPlaneIntersectionStatus {
    Empty,
    Unbounded,
    Degenerate,
    Bounded,
};

struct HalfPlaneIntersectionResult {
    HalfPlaneIntersectionStatus status;
    std::vector<Point<long double>> polygon;
};
Status Meaning
Empty No point satisfies every half-plane.
Unbounded The intersection is nonempty and unbounded, including an unbounded line or ray.
Degenerate The intersection is bounded but has zero area, so it is a point or segment.
Bounded The intersection has positive area; polygon contains its boundary.

polygon is empty for every status except Bounded.

Function

Function Description Complexity
half_plane_intersection(half_planes, eps) Classifies the intersection and returns its polygon when it is bounded with positive area. Expected $O(N\log N)$ time, $O(N^2)$ worst-case time, and $O(N)$ memory

The exact signature is:

template <Coordinate T>
HalfPlaneIntersectionResult half_plane_intersection(
    const std::vector<Line<T>>& half_planes,
    long double eps = 1e-12L
);

Every boundary line must have distinct endpoints. For Bounded, the returned polygon is counterclockwise, starts at its lexicographically smallest vertex, and does not repeat that vertex at the end. Closed boundaries are included. The empty collection of constraints has status Unbounded because its intersection is the entire plane.

Feasibility is checked by randomized incremental two-dimensional linear programming, which gives the expected time bound above. The tolerance is applied after boundary directions are normalized, so it acts as both an angular and a signed-distance tolerance.

Example

#include "geometry/half_plane_intersection.hpp"

#include <iostream>
#include <vector>

int main() {
    using namespace m1une::geometry;
    using P = Point<long double>;

    std::vector<Line<long double>> half_planes;
    half_planes.push_back(Line<long double>{P(0, 0), P(2, 0)});
    half_planes.push_back(Line<long double>{P(2, 0), P(2, 2)});
    half_planes.push_back(Line<long double>{P(2, 2), P(0, 2)});
    half_planes.push_back(Line<long double>{P(0, 2), P(0, 0)});

    auto result = half_plane_intersection(half_planes);
    if (result.status == HalfPlaneIntersectionStatus::Bounded) {
        std::cout << result.polygon.size() << "\n";  // 4
    }
}

Depends on

Required by

Verified with

Code

#ifndef M1UNE_GEOMETRY_HALF_PLANE_INTERSECTION_HPP
#define M1UNE_GEOMETRY_HALF_PLANE_INTERSECTION_HPP 1

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <deque>
#include <limits>
#include <numbers>
#include <optional>
#include <random>
#include <utility>
#include <vector>

#include "linear.hpp"

namespace m1une {
namespace geometry {

enum class HalfPlaneIntersectionStatus {
    Empty,
    Unbounded,
    Degenerate,
    Bounded,
};

struct HalfPlaneIntersectionResult {
    HalfPlaneIntersectionStatus status;
    std::vector<Point<long double>> polygon;
};

namespace half_plane_intersection_detail {

struct HalfPlane {
    Point<long double> point;
    Point<long double> direction;
    long double angle;

    HalfPlane(
        const Point<long double>& point_value,
        const Point<long double>& direction_value
    ) : point(point_value), direction(direction_value) {
        angle = std::atan2(direction.y, direction.x);
        if (angle < 0) angle += 2 * std::numbers::pi_v<long double>;
    }
};

inline bool direction_less(const HalfPlane& first, const HalfPlane& second) {
    return first.angle < second.angle;
}

inline bool parallel(
    const HalfPlane& first,
    const HalfPlane& second,
    long double eps
) {
    return std::fabs(cross(first.direction, second.direction)) <= eps;
}

inline bool same_direction(
    const HalfPlane& first,
    const HalfPlane& second,
    long double eps
) {
    return parallel(first, second, eps) &&
           dot(first.direction, second.direction) > 0;
}

inline bool outside(
    const HalfPlane& half_plane,
    const Point<long double>& point,
    long double eps
) {
    return cross(half_plane.direction, point - half_plane.point) < -eps;
}

inline bool more_restrictive(
    const HalfPlane& candidate,
    const HalfPlane& current,
    long double eps
) {
    return cross(
        current.direction,
        candidate.point - current.point
    ) > eps;
}

inline std::optional<Point<long double>> intersection(
    const HalfPlane& first,
    const HalfPlane& second,
    long double eps
) {
    long double denominator = cross(first.direction, second.direction);
    if (std::fabs(denominator) <= eps) return std::nullopt;
    long double ratio = cross(
        second.point - first.point,
        second.direction
    ) / denominator;
    return first.point + first.direction * ratio;
}

inline void merge_same_direction(
    std::vector<HalfPlane>& half_planes,
    const HalfPlane& half_plane,
    long double eps
) {
    if (
        half_planes.empty() ||
        !same_direction(half_planes.back(), half_plane, eps)
    ) {
        half_planes.push_back(half_plane);
        return;
    }
    if (more_restrictive(half_plane, half_planes.back(), eps)) {
        half_planes.back() = half_plane;
    }
}

inline void merge_cyclic_ends(
    std::vector<HalfPlane>& half_planes,
    long double eps
) {
    if (
        half_planes.size() < 2 ||
        !same_direction(half_planes.front(), half_planes.back(), eps)
    ) {
        return;
    }
    if (more_restrictive(half_planes.back(), half_planes.front(), eps)) {
        half_planes.front() = half_planes.back();
    }
    half_planes.pop_back();
}

inline bool has_feasible_point(
    std::vector<HalfPlane> half_planes,
    long double eps
) {
    std::mt19937_64 generator(0x6a09e667f3bcc909ULL);
    std::shuffle(half_planes.begin(), half_planes.end(), generator);

    Point<long double> feasible(0, 0);
    for (std::size_t index = 0; index < half_planes.size(); ++index) {
        const HalfPlane& current = half_planes[index];
        if (!outside(current, feasible, eps)) continue;

        Point<long double> normal(
            -current.direction.y,
            current.direction.x
        );
        Point<long double> base = normal * dot(normal, current.point);
        long double lower = -std::numeric_limits<long double>::infinity();
        long double upper = std::numeric_limits<long double>::infinity();
        for (std::size_t previous_index = 0;
             previous_index < index;
             ++previous_index) {
            const HalfPlane& previous = half_planes[previous_index];
            long double coefficient = cross(
                previous.direction,
                current.direction
            );
            long double constant = cross(
                previous.direction,
                base - previous.point
            );
            if (std::fabs(coefficient) <= eps) {
                if (constant < -eps) return false;
                continue;
            }

            long double bound = (-eps - constant) / coefficient;
            if (coefficient > 0) {
                lower = std::max(lower, bound);
            } else {
                upper = std::min(upper, bound);
            }
            if (lower > upper) return false;
        }

        long double parameter = 0;
        if (parameter < lower) parameter = lower;
        if (parameter > upper) parameter = upper;
        feasible = base + current.direction * parameter;
    }
    return true;
}

inline bool has_bounded_recession_cone(
    const std::vector<HalfPlane>& half_planes,
    long double eps
) {
    if (half_planes.empty()) return false;

    constexpr long double pi = std::numbers::pi_v<long double>;
    long double maximum_gap =
        half_planes.front().angle + 2 * pi - half_planes.back().angle;
    for (std::size_t index = 1; index < half_planes.size(); ++index) {
        maximum_gap = std::max(
            maximum_gap,
            half_planes[index].angle - half_planes[index - 1].angle
        );
    }
    return maximum_gap < pi - eps;
}

}  // namespace half_plane_intersection_detail

// Each directed line keeps its closed left half-plane. Returns the vertices of
// a bounded intersection with positive area in counterclockwise order. Empty,
// unbounded, and bounded zero-area intersections have distinct statuses.
template <Coordinate T>
HalfPlaneIntersectionResult half_plane_intersection(
    const std::vector<Line<T>>& half_planes,
    long double eps = 1e-12L
) {
    using half_plane_intersection_detail::HalfPlane;
    namespace detail = half_plane_intersection_detail;

    assert(eps >= 0);
    std::vector<HalfPlane> sorted;
    sorted.reserve(half_planes.size());
    for (const Line<T>& line : half_planes) {
        assert(line.a != line.b);
        Point<long double> point(line.a);
        Point<long double> direction = Point<long double>(line.b) - point;
        long double length = norm(direction);
        direction = direction / length;
        sorted.push_back(HalfPlane{point, direction});
    }
    if (!detail::has_feasible_point(sorted, eps)) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Empty,
            {},
        };
    }
    std::sort(sorted.begin(), sorted.end(), detail::direction_less);
    if (!detail::has_bounded_recession_cone(sorted, eps)) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Unbounded,
            {},
        };
    }
    if (sorted.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    std::vector<HalfPlane> unique;
    unique.reserve(sorted.size());
    for (const HalfPlane& half_plane : sorted) {
        detail::merge_same_direction(unique, half_plane, eps);
    }
    detail::merge_cyclic_ends(unique, eps);
    if (unique.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    std::deque<HalfPlane> deque;
    for (const HalfPlane& half_plane : unique) {
        while (deque.size() >= 2) {
            auto point = detail::intersection(
                deque[deque.size() - 2],
                deque.back(),
                eps
            );
            if (!point.has_value()) {
                return HalfPlaneIntersectionResult{
                    HalfPlaneIntersectionStatus::Degenerate,
                    {},
                };
            }
            if (!detail::outside(half_plane, *point, eps)) break;
            deque.pop_back();
        }
        while (deque.size() >= 2) {
            auto point = detail::intersection(deque[0], deque[1], eps);
            if (!point.has_value()) {
                return HalfPlaneIntersectionResult{
                    HalfPlaneIntersectionStatus::Degenerate,
                    {},
                };
            }
            if (!detail::outside(half_plane, *point, eps)) break;
            deque.pop_front();
        }
        deque.push_back(half_plane);
    }

    while (deque.size() >= 3) {
        auto point = detail::intersection(
            deque[deque.size() - 2],
            deque.back(),
            eps
        );
        if (!point.has_value()) {
            return HalfPlaneIntersectionResult{
                HalfPlaneIntersectionStatus::Degenerate,
                {},
            };
        }
        if (!detail::outside(deque.front(), *point, eps)) break;
        deque.pop_back();
    }
    while (deque.size() >= 3) {
        auto point = detail::intersection(deque[0], deque[1], eps);
        if (!point.has_value()) {
            return HalfPlaneIntersectionResult{
                HalfPlaneIntersectionStatus::Degenerate,
                {},
            };
        }
        if (!detail::outside(deque.back(), *point, eps)) break;
        deque.pop_front();
    }
    if (deque.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    std::vector<Point<long double>> polygon;
    polygon.reserve(deque.size());
    for (std::size_t index = 0; index < deque.size(); ++index) {
        auto point = detail::intersection(
            deque[index],
            deque[(index + 1) % deque.size()],
            eps
        );
        if (!point.has_value()) {
            return HalfPlaneIntersectionResult{
                HalfPlaneIntersectionStatus::Degenerate,
                {},
            };
        }
        if (
            polygon.empty() ||
            distance(polygon.back(), *point) > eps
        ) {
            polygon.push_back(*point);
        }
    }
    if (
        polygon.size() >= 2 &&
        distance(polygon.front(), polygon.back()) <= eps
    ) {
        polygon.pop_back();
    }
    if (polygon.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    long double signed_area2 = 0;
    Point<long double> origin = polygon.front();
    for (std::size_t index = 1; index + 1 < polygon.size(); ++index) {
        signed_area2 += cross(
            polygon[index] - origin,
            polygon[index + 1] - origin
        );
    }
    if (signed_area2 <= eps) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    auto first = std::min_element(polygon.begin(), polygon.end());
    std::rotate(polygon.begin(), first, polygon.end());
    return HalfPlaneIntersectionResult{
        HalfPlaneIntersectionStatus::Bounded,
        std::move(polygon),
    };
}

}  // namespace geometry
}  // namespace m1une

#endif  // M1UNE_GEOMETRY_HALF_PLANE_INTERSECTION_HPP
#line 1 "geometry/half_plane_intersection.hpp"



#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstddef>
#include <deque>
#include <limits>
#include <numbers>
#include <optional>
#include <random>
#include <utility>
#include <vector>

#line 1 "geometry/linear.hpp"



#line 7 "geometry/linear.hpp"

#line 1 "geometry/point.hpp"



#line 5 "geometry/point.hpp"
#include <concepts>
#line 7 "geometry/point.hpp"
#include <type_traits>

#line 1 "geometry/detail/floating_predicate.hpp"



namespace m1une {
namespace geometry {
namespace predicate_detail {

template <typename T>
constexpr T absolute(T value) {
    return value < T(0) ? -value : value;
}

template <typename T>
constexpr T max_value(T first, T second) {
    return first < second ? second : first;
}

template <typename T>
constexpr T vector_scale(T x, T y) {
    return max_value(absolute(x), absolute(y));
}

template <bool Exact, typename T>
constexpr int scaled_sign(T value, T scale, long double eps) {
    if constexpr (Exact) {
        return (value > T(0)) - (value < T(0));
    } else {
        const T tolerance = T(eps) * scale;
        return (value > tolerance) - (value < -tolerance);
    }
}

template <bool Exact, typename T>
constexpr T determinant_scale(T ax, T ay, T bx, T by) {
    if constexpr (Exact) {
        return T(0);
    } else {
        return vector_scale(ax, ay) * vector_scale(bx, by);
    }
}

template <bool Exact, typename T>
constexpr int determinant_sign(
    T ax,
    T ay,
    T bx,
    T by,
    long double eps
) {
    const T determinant = ax * by - ay * bx;
    return scaled_sign<Exact>(
        determinant,
        determinant_scale<Exact>(ax, ay, bx, by),
        eps
    );
}

template <bool Exact, typename T>
constexpr int orientation_sign(
    T direction_x,
    T direction_y,
    T offset_x,
    T offset_y,
    long double eps
) {
    const T determinant =
        direction_x * offset_y - direction_y * offset_x;
    T scale = T(0);
    if constexpr (!Exact) {
        const T direction_scale =
            vector_scale(direction_x, direction_y);
        scale = direction_scale * max_value(
            direction_scale,
            vector_scale(offset_x, offset_y)
        );
    }
    return scaled_sign<Exact>(determinant, scale, eps);
}

template <bool Exact, typename T>
constexpr int dot_sign(
    T ax,
    T ay,
    T bx,
    T by,
    long double eps
) {
    const T value = ax * bx + ay * by;
    T scale = T(0);
    if constexpr (!Exact) {
        scale = vector_scale(ax, ay) * vector_scale(bx, by);
    }
    return scaled_sign<Exact>(value, scale, eps);
}

}  // namespace predicate_detail
}  // namespace geometry
}  // namespace m1une


#line 10 "geometry/point.hpp"

namespace m1une {
namespace geometry {

template <typename T>
concept Coordinate = !std::same_as<std::remove_cv_t<T>, bool> &&
    (std::is_arithmetic_v<T> ||
     (std::copyable<T> && std::totally_ordered<T> && requires(T a, T b) {
         T(0);
         T(1);
         static_cast<long double>(a);
         { +a } -> std::same_as<T>;
         { -a } -> std::same_as<T>;
         { a + b } -> std::same_as<T>;
         { a - b } -> std::same_as<T>;
         { a * b } -> std::same_as<T>;
         { a / b } -> std::same_as<T>;
         { a += b } -> std::same_as<T&>;
         { a -= b } -> std::same_as<T&>;
     }));

// Custom coordinate types keep their own exact arithmetic.
template <typename T>
concept ExactCoordinate = Coordinate<T> && !std::floating_point<T>;

template <Coordinate T>
using wide_type = std::conditional_t<std::integral<T>, __int128_t,
    std::conditional_t<std::floating_point<T>, long double, T>>;

template <Coordinate T>
struct Point {
    T x;
    T y;

    constexpr Point() : x(0), y(0) {}
    constexpr Point(T x_value, T y_value) : x(x_value), y(y_value) {}

    template <Coordinate U>
    explicit constexpr Point(const Point<U>& other)
        : x(static_cast<T>(other.x)), y(static_cast<T>(other.y)) {}

    constexpr Point& operator+=(const Point& other) {
        x += other.x;
        y += other.y;
        return *this;
    }

    constexpr Point& operator-=(const Point& other) {
        x -= other.x;
        y -= other.y;
        return *this;
    }

    constexpr Point operator+() const {
        return *this;
    }

    constexpr Point operator-() const {
        return Point(-x, -y);
    }

    friend constexpr Point operator+(Point left, const Point& right) {
        return left += right;
    }

    friend constexpr Point operator-(Point left, const Point& right) {
        return left -= right;
    }

    friend constexpr bool operator==(const Point&, const Point&) = default;

    friend constexpr bool operator<(const Point& left, const Point& right) {
        if (left.x != right.x) return left.x < right.x;
        return left.y < right.y;
    }
};

template <Coordinate T>
constexpr Point<long double> centroid(const Point<T>& point) {
    return Point<long double>(point);
}

template <Coordinate T, typename Scalar>
requires (std::is_arithmetic_v<Scalar> || Coordinate<Scalar>)
constexpr auto operator*(const Point<T>& point, Scalar scalar) {
    using Result = std::common_type_t<T, Scalar>;
    return Point<Result>(
        Result(point.x) * Result(scalar),
        Result(point.y) * Result(scalar)
    );
}

template <typename Scalar, Coordinate T>
requires (std::is_arithmetic_v<Scalar> || Coordinate<Scalar>)
constexpr auto operator*(Scalar scalar, const Point<T>& point) {
    return point * scalar;
}

template <Coordinate T, typename Scalar>
requires (std::is_arithmetic_v<Scalar> || Coordinate<Scalar>)
constexpr auto operator/(const Point<T>& point, Scalar scalar) {
    using Result = std::common_type_t<T, Scalar>;
    return Point<Result>(
        Result(point.x) / Result(scalar),
        Result(point.y) / Result(scalar)
    );
}

template <Coordinate T>
constexpr wide_type<T> dot(const Point<T>& a, const Point<T>& b) {
    using W = wide_type<T>;
    return W(a.x) * W(b.x) + W(a.y) * W(b.y);
}

template <Coordinate T>
constexpr wide_type<T> cross(const Point<T>& a, const Point<T>& b) {
    using W = wide_type<T>;
    return W(a.x) * W(b.y) - W(a.y) * W(b.x);
}

template <Coordinate T>
constexpr wide_type<T> cross(
    const Point<T>& origin,
    const Point<T>& a,
    const Point<T>& b
) {
    using W = wide_type<T>;
    W ax = W(a.x) - W(origin.x);
    W ay = W(a.y) - W(origin.y);
    W bx = W(b.x) - W(origin.x);
    W by = W(b.y) - W(origin.y);
    return ax * by - ay * bx;
}

template <Coordinate T>
constexpr wide_type<T> norm2(const Point<T>& point) {
    return dot(point, point);
}

template <Coordinate T>
constexpr wide_type<T> distance2(const Point<T>& a, const Point<T>& b) {
    using W = wide_type<T>;
    W dx = W(a.x) - W(b.x);
    W dy = W(a.y) - W(b.y);
    return dx * dx + dy * dy;
}

template <Coordinate T>
long double norm(const Point<T>& point) {
    return std::hypot(
        static_cast<long double>(point.x),
        static_cast<long double>(point.y)
    );
}

template <Coordinate T>
long double distance(const Point<T>& a, const Point<T>& b) {
    return std::hypot(
        static_cast<long double>(a.x) - static_cast<long double>(b.x),
        static_cast<long double>(a.y) - static_cast<long double>(b.y)
    );
}

template <Coordinate T, typename M, typename N>
requires (std::is_arithmetic_v<M> || Coordinate<M>) &&
         (std::is_arithmetic_v<N> || Coordinate<N>)
constexpr Point<long double> internal_division_point(
    const Point<T>& a,
    const Point<T>& b,
    M m,
    N n
) {
    long double first_ratio = static_cast<long double>(m);
    long double second_ratio = static_cast<long double>(n);
    long double denominator = first_ratio + second_ratio;
    assert(denominator != 0);
    Point<long double> first(a);
    Point<long double> direction = Point<long double>(b) - first;
    return first + direction * (first_ratio / denominator);
}

template <Coordinate T, typename M, typename N>
requires (std::is_arithmetic_v<M> || Coordinate<M>) &&
         (std::is_arithmetic_v<N> || Coordinate<N>)
constexpr Point<long double> external_division_point(
    const Point<T>& a,
    const Point<T>& b,
    M m,
    N n
) {
    long double first_ratio = static_cast<long double>(m);
    long double second_ratio = static_cast<long double>(n);
    long double denominator = first_ratio - second_ratio;
    assert(denominator != 0);
    Point<long double> first(a);
    Point<long double> direction = Point<long double>(b) - first;
    return first + direction * (first_ratio / denominator);
}

template <Coordinate T>
constexpr int sign(wide_type<T> value, long double eps = 1e-12L) {
    return predicate_detail::scaled_sign<ExactCoordinate<T>>(
        value,
        wide_type<T>(1),
        eps
    );
}

template <Coordinate T>
constexpr int orientation(
    const Point<T>& a,
    const Point<T>& b,
    const Point<T>& c,
    long double eps = 1e-12L
) {
    using W = wide_type<T>;
    const W first_x = W(b.x) - W(a.x);
    const W first_y = W(b.y) - W(a.y);
    const W second_x = W(c.x) - W(a.x);
    const W second_y = W(c.y) - W(a.y);
    return predicate_detail::orientation_sign<ExactCoordinate<T>>(
        first_x,
        first_y,
        second_x,
        second_y,
        eps
    );
}

template <Coordinate T>
constexpr bool collinear(
    const Point<T>& a,
    const Point<T>& b,
    const Point<T>& c,
    long double eps = 1e-12L
) {
    return orientation(a, b, c, eps) == 0;
}

template <Coordinate T>
Point<long double> rotate(const Point<T>& point, long double angle) {
    long double cosine = std::cos(angle);
    long double sine = std::sin(angle);
    return Point<long double>(
        static_cast<long double>(point.x) * cosine -
            static_cast<long double>(point.y) * sine,
        static_cast<long double>(point.x) * sine +
            static_cast<long double>(point.y) * cosine
    );
}

template <Coordinate T>
Point<long double> normalized(const Point<T>& point) {
    long double length = norm(point);
    assert(length != 0);
    return Point<long double>(
        static_cast<long double>(point.x) / length,
        static_cast<long double>(point.y) / length
    );
}

}  // namespace geometry
}  // namespace m1une


#line 9 "geometry/linear.hpp"

namespace m1une {
namespace geometry {

template <Coordinate T>
struct Line {
    Point<T> a;
    Point<T> b;
};

template <Coordinate T>
struct Segment {
    Point<T> a;
    Point<T> b;
};

template <Coordinate T>
struct Ray {
    Point<T> origin;
    Point<T> through;
};

enum class LinearIntersectionKind {
    Empty,
    Point,
    Segment,
    Ray,
    Line,
};

struct LinearIntersection {
    LinearIntersectionKind kind;
    Point<long double> first;
    Point<long double> second;
};

struct ClosestPoints {
    Point<long double> first;
    Point<long double> second;
};

namespace linear_intersection_detail {

inline LinearIntersection make_empty() {
    const Point<long double> zero;
    return LinearIntersection{
        LinearIntersectionKind::Empty,
        zero,
        zero,
    };
}

template <Coordinate T>
LinearIntersection make_point(const Point<T>& point) {
    const Point<long double> converted(point);
    return LinearIntersection{
        LinearIntersectionKind::Point,
        converted,
        converted,
    };
}

template <Coordinate T>
LinearIntersection make_object(
    LinearIntersectionKind kind,
    const Point<T>& first,
    const Point<T>& second
) {
    return LinearIntersection{
        kind,
        Point<long double>(first),
        Point<long double>(second),
    };
}

}  // namespace linear_intersection_detail

template <Coordinate T>
constexpr Point<long double> centroid(const Segment<T>& segment) {
    return Point<long double>(
        (
            static_cast<long double>(segment.a.x) +
            static_cast<long double>(segment.b.x)
        ) / 2,
        (
            static_cast<long double>(segment.a.y) +
            static_cast<long double>(segment.b.y)
        ) / 2
    );
}

template <Coordinate T>
bool on_line(
    const Line<T>& line,
    const Point<T>& point,
    long double eps = 1e-12L
) {
    assert(line.a != line.b);
    return orientation(line.a, line.b, point, eps) == 0;
}

template <Coordinate T>
bool parallel(const Line<T>& first, const Line<T>& second, long double eps = 1e-12L) {
    using W = wide_type<T>;
    W first_x = W(first.b.x) - W(first.a.x);
    W first_y = W(first.b.y) - W(first.a.y);
    W second_x = W(second.b.x) - W(second.a.x);
    W second_y = W(second.b.y) - W(second.a.y);
    return predicate_detail::determinant_sign<ExactCoordinate<T>>(
        first_x,
        first_y,
        second_x,
        second_y,
        eps
    ) == 0;
}

template <Coordinate T>
bool orthogonal(const Line<T>& first, const Line<T>& second, long double eps = 1e-12L) {
    using W = wide_type<T>;
    W first_x = W(first.b.x) - W(first.a.x);
    W first_y = W(first.b.y) - W(first.a.y);
    W second_x = W(second.b.x) - W(second.a.x);
    W second_y = W(second.b.y) - W(second.a.y);
    return predicate_detail::dot_sign<ExactCoordinate<T>>(
        first_x,
        first_y,
        second_x,
        second_y,
        eps
    ) == 0;
}

template <Coordinate T>
Point<long double> projection(const Line<T>& line, const Point<T>& point) {
    assert(line.a != line.b);
    Point<long double> a(line.a);
    Point<long double> direction(
        static_cast<long double>(line.b.x) - static_cast<long double>(line.a.x),
        static_cast<long double>(line.b.y) - static_cast<long double>(line.a.y)
    );
    Point<long double> offset(
        static_cast<long double>(point.x) - a.x,
        static_cast<long double>(point.y) - a.y
    );
    long double ratio = dot(offset, direction) / dot(direction, direction);
    return a + direction * ratio;
}

template <Coordinate T>
Point<long double> reflection(const Line<T>& line, const Point<T>& point) {
    Point<long double> projected = projection(line, point);
    return projected * 2.0L - Point<long double>(point);
}

template <Coordinate T>
bool intersects(
    const Line<T>& first,
    const Line<T>& second,
    long double eps = 1e-12L
) {
    return !parallel(first, second, eps) || on_line(first, second.a, eps);
}

template <Coordinate T>
bool on_segment(
    const Segment<T>& segment,
    const Point<T>& point,
    long double eps = 1e-12L
) {
    if (orientation(segment.a, segment.b, point, eps) != 0) return false;
    using W = wide_type<T>;
    const W direction_x = W(segment.b.x) - W(segment.a.x);
    const W direction_y = W(segment.b.y) - W(segment.a.y);
    if (direction_x == W(0) && direction_y == W(0)) {
        if constexpr (ExactCoordinate<T>) {
            return point == segment.a;
        } else {
            return
                predicate_detail::absolute(W(point.x) - W(segment.a.x)) <= eps &&
                predicate_detail::absolute(W(point.y) - W(segment.a.y)) <= eps;
        }
    }
    const W offset_x = W(point.x) - W(segment.a.x);
    const W offset_y = W(point.y) - W(segment.a.y);
    const W projection =
        offset_x * direction_x + offset_y * direction_y;
    const W length_squared =
        direction_x * direction_x + direction_y * direction_y;
    return
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            projection,
            length_squared,
            eps
        ) >= 0 &&
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            projection - length_squared,
            length_squared,
            eps
        ) <= 0;
}

template <Coordinate T>
Point<long double> projection(
    const Segment<T>& segment,
    const Point<T>& point
) {
    const Point<long double> first(segment.a);
    const Point<long double> direction =
        Point<long double>(segment.b) - first;
    const long double length_squared = dot(direction, direction);
    if (length_squared == 0) return first;
    const long double ratio = std::clamp(
        dot(Point<long double>(point) - first, direction) / length_squared,
        0.0L,
        1.0L
    );
    return first + direction * ratio;
}

template <Coordinate T>
bool intersects(
    const Segment<T>& first,
    const Segment<T>& second,
    long double eps = 1e-12L
) {
    int abc = orientation(first.a, first.b, second.a, eps);
    int abd = orientation(first.a, first.b, second.b, eps);
    int cda = orientation(second.a, second.b, first.a, eps);
    int cdb = orientation(second.a, second.b, first.b, eps);

    if (abc == 0 && on_segment(first, second.a, eps)) return true;
    if (abd == 0 && on_segment(first, second.b, eps)) return true;
    if (cda == 0 && on_segment(second, first.a, eps)) return true;
    if (cdb == 0 && on_segment(second, first.b, eps)) return true;
    return abc * abd < 0 && cda * cdb < 0;
}

template <Coordinate T>
bool intersects(
    const Line<T>& line,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    int first_side = orientation(line.a, line.b, segment.a, eps);
    int second_side = orientation(line.a, line.b, segment.b, eps);
    return first_side == 0 || second_side == 0 || first_side != second_side;
}

template <Coordinate T>
bool intersects(
    const Segment<T>& segment,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return intersects(line, segment, eps);
}

namespace linear_parameter_detail {

template <Coordinate T>
struct Parameters {
    wide_type<T> denominator;
    wide_type<T> denominator_scale;
    wide_type<T> first_numerator;
    wide_type<T> second_numerator;
};

template <Coordinate T>
Parameters<T> parameters(
    const Point<T>& first_origin,
    const Point<T>& first_through,
    const Point<T>& second_origin,
    const Point<T>& second_through
) {
    using W = wide_type<T>;
    W first_x = W(first_through.x) - W(first_origin.x);
    W first_y = W(first_through.y) - W(first_origin.y);
    W second_x = W(second_through.x) - W(second_origin.x);
    W second_y = W(second_through.y) - W(second_origin.y);
    W offset_x = W(second_origin.x) - W(first_origin.x);
    W offset_y = W(second_origin.y) - W(first_origin.y);
    return Parameters<T>{
        first_x * second_y - first_y * second_x,
        predicate_detail::determinant_scale<ExactCoordinate<T>>(
            first_x,
            first_y,
            second_x,
            second_y
        ),
        offset_x * second_y - offset_y * second_x,
        offset_x * first_y - offset_y * first_x
    };
}

template <Coordinate T>
int denominator_sign(const Parameters<T>& values, long double eps) {
    return predicate_detail::scaled_sign<ExactCoordinate<T>>(
        values.denominator,
        values.denominator_scale,
        eps
    );
}

template <Coordinate T>
bool ratio_nonnegative(
    wide_type<T> numerator,
    wide_type<T> denominator,
    long double eps
) {
    const int numerator_sign =
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            numerator,
            predicate_detail::absolute(denominator),
            eps
        );
    const int denominator_direction =
        (denominator > 0) - (denominator < 0);
    return
        numerator_sign == 0 ||
        numerator_sign == denominator_direction;
}

template <Coordinate T>
bool ratio_in_unit_interval(
    wide_type<T> numerator,
    wide_type<T> denominator,
    long double eps
) {
    const auto scale = predicate_detail::absolute(denominator);
    const int start_sign =
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            numerator,
            scale,
            eps
        );
    const int finish_sign =
        predicate_detail::scaled_sign<ExactCoordinate<T>>(
            numerator - denominator,
            scale,
            eps
        );
    if (denominator > 0) {
        return start_sign >= 0 && finish_sign <= 0;
    }
    return start_sign <= 0 && finish_sign >= 0;
}

}  // namespace linear_parameter_detail

template <Coordinate T>
bool on_ray(
    const Ray<T>& ray,
    const Point<T>& point,
    long double eps = 1e-12L
) {
    assert(ray.origin != ray.through);
    if (orientation(ray.origin, ray.through, point, eps) != 0) return false;
    using W = wide_type<T>;
    W direction_x = W(ray.through.x) - W(ray.origin.x);
    W direction_y = W(ray.through.y) - W(ray.origin.y);
    W offset_x = W(point.x) - W(ray.origin.x);
    W offset_y = W(point.y) - W(ray.origin.y);
    const W projection =
        direction_x * offset_x + direction_y * offset_y;
    const W length_squared =
        direction_x * direction_x + direction_y * direction_y;
    return predicate_detail::scaled_sign<ExactCoordinate<T>>(
        projection,
        length_squared,
        eps
    ) >= 0;
}

template <Coordinate T>
Point<long double> projection(const Ray<T>& ray, const Point<T>& point) {
    assert(ray.origin != ray.through);
    Point<long double> origin(ray.origin);
    Point<long double> direction =
        Point<long double>(ray.through) - origin;
    Point<long double> offset = Point<long double>(point) - origin;
    long double ratio = dot(offset, direction) / dot(direction, direction);
    if (ratio < 0) ratio = 0;
    return origin + direction * ratio;
}

template <Coordinate T>
Ray<long double> reflection(const Line<T>& line, const Ray<T>& ray) {
    assert(ray.origin != ray.through);
    return Ray<long double>{
        reflection(line, ray.origin),
        reflection(line, ray.through)
    };
}

template <Coordinate T>
Ray<long double> reflected_ray(
    const Ray<T>& incoming,
    const Point<T>& hit,
    const Line<T>& mirror,
    long double eps = 1e-12L
) {
    assert(incoming.origin != incoming.through);
    assert(on_line(mirror, hit, eps));
    Point<T> translated = hit + (incoming.through - incoming.origin);
    return Ray<long double>{
        Point<long double>(hit),
        reflection(mirror, translated)
    };
}

template <Coordinate T>
bool intersects(
    const Ray<T>& ray,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    assert(ray.origin != ray.through);
    assert(line.a != line.b);
    linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        ray.origin,
        ray.through,
        line.a,
        line.b
    );
    if (linear_parameter_detail::denominator_sign(values, eps) == 0) {
        return on_line(line, ray.origin, eps);
    }
    return linear_parameter_detail::ratio_nonnegative<T>(
        values.first_numerator,
        values.denominator,
        eps
    );
}

template <Coordinate T>
bool intersects(
    const Line<T>& line,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return intersects(ray, line, eps);
}

template <Coordinate T>
bool intersects(
    const Ray<T>& ray,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    assert(ray.origin != ray.through);
    if (segment.a == segment.b) return on_ray(ray, segment.a, eps);

    linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        ray.origin,
        ray.through,
        segment.a,
        segment.b
    );
    if (linear_parameter_detail::denominator_sign(values, eps) == 0) {
        if (orientation(ray.origin, ray.through, segment.a, eps) != 0) {
            return false;
        }
        return on_ray(ray, segment.a, eps) ||
               on_ray(ray, segment.b, eps) ||
               on_segment(segment, ray.origin, eps);
    }
    return linear_parameter_detail::ratio_nonnegative<T>(
               values.first_numerator,
               values.denominator,
               eps
           ) &&
           linear_parameter_detail::ratio_in_unit_interval<T>(
               values.second_numerator,
               values.denominator,
               eps
           );
}

template <Coordinate T>
bool intersects(
    const Segment<T>& segment,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return intersects(ray, segment, eps);
}

template <Coordinate T>
bool intersects(
    const Ray<T>& first,
    const Ray<T>& second,
    long double eps = 1e-12L
) {
    assert(first.origin != first.through);
    assert(second.origin != second.through);
    linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        first.origin,
        first.through,
        second.origin,
        second.through
    );
    if (linear_parameter_detail::denominator_sign(values, eps) == 0) {
        if (orientation(first.origin, first.through, second.origin, eps) != 0) {
            return false;
        }
        return on_ray(first, second.origin, eps) ||
               on_ray(second, first.origin, eps);
    }
    return linear_parameter_detail::ratio_nonnegative<T>(
               values.first_numerator,
               values.denominator,
               eps
           ) &&
           linear_parameter_detail::ratio_nonnegative<T>(
               values.second_numerator,
               values.denominator,
               eps
           );
}

namespace linear_intersection_detail {

enum class Domain {
    Line,
    Segment,
    Ray,
};

template <Coordinate T>
struct ParametricObject {
    Point<T> origin;
    Point<T> through;
    Domain domain;
};

template <Coordinate T>
ParametricObject<T> parametric_object(const Line<T>& line) {
    assert(line.a != line.b);
    return ParametricObject<T>{line.a, line.b, Domain::Line};
}

template <Coordinate T>
ParametricObject<T> parametric_object(const Segment<T>& segment) {
    return ParametricObject<T>{segment.a, segment.b, Domain::Segment};
}

template <Coordinate T>
ParametricObject<T> parametric_object(const Ray<T>& ray) {
    assert(ray.origin != ray.through);
    return ParametricObject<T>{ray.origin, ray.through, Domain::Ray};
}

template <Coordinate T>
bool contains(
    const ParametricObject<T>& object,
    const Point<T>& point,
    long double eps
) {
    if (object.domain == Domain::Line) {
        return on_line(Line<T>{object.origin, object.through}, point, eps);
    }
    if (object.domain == Domain::Segment) {
        return on_segment(
            Segment<T>{object.origin, object.through},
            point,
            eps
        );
    }
    return on_ray(Ray<T>{object.origin, object.through}, point, eps);
}

template <Coordinate T>
bool accepts_parameter(
    Domain domain,
    wide_type<T> numerator,
    wide_type<T> denominator,
    long double eps
) {
    if (domain == Domain::Line) return true;
    if (domain == Domain::Ray) {
        return linear_parameter_detail::ratio_nonnegative<T>(
            numerator,
            denominator,
            eps
        );
    }
    return linear_parameter_detail::ratio_in_unit_interval<T>(
        numerator,
        denominator,
        eps
    );
}

template <Coordinate T>
Point<long double> point_at_ratio(
    const ParametricObject<T>& object,
    wide_type<T> numerator,
    wide_type<T> denominator
) {
    const long double ratio =
        static_cast<long double>(numerator) /
        static_cast<long double>(denominator);
    const Point<long double> origin(object.origin);
    const Point<long double> direction =
        Point<long double>(object.through) - origin;
    return origin + direction * ratio;
}

template <Coordinate T>
struct AxisProjection {
    bool use_x;
    bool negate;

    wide_type<T> operator()(const Point<T>& point) const {
        const wide_type<T> value = use_x
            ? wide_type<T>(point.x)
            : wide_type<T>(point.y);
        return negate ? -value : value;
    }
};

template <Coordinate T>
AxisProjection<T> axis_projection(const ParametricObject<T>& object) {
    using W = wide_type<T>;
    const W direction_x = W(object.through.x) - W(object.origin.x);
    const W direction_y = W(object.through.y) - W(object.origin.y);
    const bool use_x =
        predicate_detail::absolute(direction_x) >=
        predicate_detail::absolute(direction_y);
    const W component = use_x ? direction_x : direction_y;
    assert(component != W(0));
    return AxisProjection<T>{use_x, component < W(0)};
}

template <Coordinate T>
struct ParameterInterval {
    bool has_lower;
    bool has_upper;
    wide_type<T> lower;
    wide_type<T> upper;
};

template <Coordinate T>
ParameterInterval<T> parameter_interval(
    const ParametricObject<T>& object,
    const AxisProjection<T>& projection
) {
    using W = wide_type<T>;
    const W origin = projection(object.origin);
    const W through = projection(object.through);
    if (object.domain == Domain::Line) {
        return ParameterInterval<T>{false, false, W(0), W(0)};
    }
    if (object.domain == Domain::Segment) {
        return ParameterInterval<T>{
            true,
            true,
            std::min(origin, through),
            std::max(origin, through),
        };
    }
    if (origin < through) {
        return ParameterInterval<T>{true, false, origin, W(0)};
    }
    return ParameterInterval<T>{false, true, W(0), origin};
}

template <Coordinate T>
ParameterInterval<T> intersect_intervals(
    ParameterInterval<T> first,
    const ParameterInterval<T>& second
) {
    if (
        second.has_lower &&
        (!first.has_lower || first.lower < second.lower)
    ) {
        first.has_lower = true;
        first.lower = second.lower;
    }
    if (
        second.has_upper &&
        (!first.has_upper || second.upper < first.upper)
    ) {
        first.has_upper = true;
        first.upper = second.upper;
    }
    return first;
}

template <Coordinate T>
Point<long double> point_at_projection(
    const ParametricObject<T>& object,
    const AxisProjection<T>& projection,
    long double target
) {
    const long double origin =
        static_cast<long double>(projection(object.origin));
    const long double through =
        static_cast<long double>(projection(object.through));
    const long double ratio = (target - origin) / (through - origin);
    const Point<long double> point(object.origin);
    const Point<long double> direction =
        Point<long double>(object.through) - point;
    return point + direction * ratio;
}

template <Coordinate T>
LinearIntersection collinear_intersection(
    const ParametricObject<T>& first,
    const ParametricObject<T>& second,
    long double eps
) {
    using W = wide_type<T>;
    const AxisProjection<T> projection = axis_projection(first);
    const ParameterInterval<T> first_interval =
        parameter_interval(first, projection);
    const ParameterInterval<T> second_interval =
        parameter_interval(second, projection);
    const ParameterInterval<T> common =
        intersect_intervals(first_interval, second_interval);

    W scale = predicate_detail::absolute(
        projection(first.through) - projection(first.origin)
    );
    scale = std::max(
        scale,
        predicate_detail::absolute(
            projection(second.through) - projection(second.origin)
        )
    );

    if (common.has_lower && common.has_upper) {
        const int order = predicate_detail::scaled_sign<ExactCoordinate<T>>(
            common.lower - common.upper,
            scale,
            eps
        );
        if (order > 0) return make_empty();
        if (order == 0) {
            const long double coordinate =
                (
                    static_cast<long double>(common.lower) +
                    static_cast<long double>(common.upper)
                ) / 2.0L;
            return make_point(
                point_at_projection(first, projection, coordinate)
            );
        }
        return make_object(
            LinearIntersectionKind::Segment,
            point_at_projection(
                first,
                projection,
                static_cast<long double>(common.lower)
            ),
            point_at_projection(
                first,
                projection,
                static_cast<long double>(common.upper)
            )
        );
    }

    const Point<long double> direction =
        Point<long double>(first.through) -
        Point<long double>(first.origin);
    if (common.has_lower) {
        const Point<long double> origin = point_at_projection(
            first,
            projection,
            static_cast<long double>(common.lower)
        );
        return make_object(
            LinearIntersectionKind::Ray,
            origin,
            origin + direction
        );
    }
    if (common.has_upper) {
        const Point<long double> origin = point_at_projection(
            first,
            projection,
            static_cast<long double>(common.upper)
        );
        return make_object(
            LinearIntersectionKind::Ray,
            origin,
            origin - direction
        );
    }
    return make_object(
        LinearIntersectionKind::Line,
        first.origin,
        first.through
    );
}

template <Coordinate T>
LinearIntersection intersect(
    const ParametricObject<T>& first,
    const ParametricObject<T>& second,
    long double eps
) {
    const bool first_degenerate = first.origin == first.through;
    const bool second_degenerate = second.origin == second.through;
    if (first_degenerate) {
        assert(first.domain == Domain::Segment);
        if (contains(second, first.origin, eps)) {
            return make_point(first.origin);
        }
        return make_empty();
    }
    if (second_degenerate) {
        assert(second.domain == Domain::Segment);
        if (contains(first, second.origin, eps)) {
            return make_point(second.origin);
        }
        return make_empty();
    }

    const linear_parameter_detail::Parameters<T> values =
        linear_parameter_detail::parameters(
        first.origin,
        first.through,
        second.origin,
        second.through
    );
    if (linear_parameter_detail::denominator_sign(values, eps) != 0) {
        if (
            !accepts_parameter<T>(
                first.domain,
                values.first_numerator,
                values.denominator,
                eps
            ) ||
            !accepts_parameter<T>(
                second.domain,
                values.second_numerator,
                values.denominator,
                eps
            )
        ) {
            return make_empty();
        }
        return make_point(
            point_at_ratio(
                first,
                values.first_numerator,
                values.denominator
            )
        );
    }
    if (
        orientation(
            first.origin,
            first.through,
            second.origin,
            eps
        ) != 0
    ) {
        return make_empty();
    }
    return collinear_intersection(first, second, eps);
}

}  // namespace linear_intersection_detail

template <Coordinate T>
LinearIntersection linear_intersection(
    const Line<T>& first,
    const Line<T>& second,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(first),
        linear_intersection_detail::parametric_object(second),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Line<T>& line,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(line),
        linear_intersection_detail::parametric_object(segment),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Segment<T>& segment,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(segment),
        linear_intersection_detail::parametric_object(line),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Segment<T>& first,
    const Segment<T>& second,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(first),
        linear_intersection_detail::parametric_object(second),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Ray<T>& ray,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(ray),
        linear_intersection_detail::parametric_object(line),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Line<T>& line,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(line),
        linear_intersection_detail::parametric_object(ray),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Ray<T>& ray,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(ray),
        linear_intersection_detail::parametric_object(segment),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Segment<T>& segment,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(segment),
        linear_intersection_detail::parametric_object(ray),
        eps
    );
}

template <Coordinate T>
LinearIntersection linear_intersection(
    const Ray<T>& first,
    const Ray<T>& second,
    long double eps = 1e-12L
) {
    return linear_intersection_detail::intersect(
        linear_intersection_detail::parametric_object(first),
        linear_intersection_detail::parametric_object(second),
        eps
    );
}

namespace closest_points_detail {

inline ClosestPoints reversed(const ClosestPoints& result) {
    return ClosestPoints{result.second, result.first};
}

inline bool point_less(
    const Point<long double>& first,
    const Point<long double>& second
) {
    if (first.x != second.x) return first.x < second.x;
    return first.y < second.y;
}

inline ClosestPoints common_point(const LinearIntersection& intersection) {
    assert(intersection.kind != LinearIntersectionKind::Empty);
    Point<long double> point = intersection.first;
    if (intersection.kind == LinearIntersectionKind::Segment) {
        if (point_less(intersection.second, point)) {
            point = intersection.second;
        }
    } else if (intersection.kind == LinearIntersectionKind::Line) {
        const Line<long double> line{
            intersection.first,
            intersection.second
        };
        point = projection(line, Point<long double>(0, 0));
    }
    return ClosestPoints{point, point};
}

inline long double separation2(const ClosestPoints& result) {
    return distance2(result.first, result.second);
}

inline bool canonical_less(
    const ClosestPoints& first,
    const ClosestPoints& second
) {
    Point<long double> first_start = first.first;
    Point<long double> first_finish = first.second;
    if (point_less(first_finish, first_start)) {
        std::swap(first_start, first_finish);
    }
    Point<long double> second_start = second.first;
    Point<long double> second_finish = second.second;
    if (point_less(second_finish, second_start)) {
        std::swap(second_start, second_finish);
    }
    if (point_less(first_start, second_start)) return true;
    if (point_less(second_start, first_start)) return false;
    return point_less(first_finish, second_finish);
}

inline void consider(ClosestPoints& best, const ClosestPoints& candidate) {
    const long double best_distance = separation2(best);
    const long double candidate_distance = separation2(candidate);
    if (
        candidate_distance < best_distance ||
        (
            candidate_distance == best_distance &&
            canonical_less(candidate, best)
        )
    ) {
        best = candidate;
    }
}

}  // namespace closest_points_detail

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& first,
    const Point<T>& second
) {
    return ClosestPoints{
        Point<long double>(first),
        Point<long double>(second),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& line,
    const Point<T>& point
) {
    return ClosestPoints{
        projection(line, point),
        Point<long double>(point),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& point,
    const Line<T>& line
) {
    return closest_points_detail::reversed(closest_points(line, point));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& segment,
    const Point<T>& point
) {
    return ClosestPoints{
        projection(segment, point),
        Point<long double>(point),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& point,
    const Segment<T>& segment
) {
    return closest_points_detail::reversed(closest_points(segment, point));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& ray,
    const Point<T>& point
) {
    return ClosestPoints{
        projection(ray, point),
        Point<long double>(point),
    };
}

template <Coordinate T>
ClosestPoints closest_points(
    const Point<T>& point,
    const Ray<T>& ray
) {
    return closest_points_detail::reversed(closest_points(ray, point));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& first,
    const Line<T>& second,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(first, second, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(first, second.a);
    closest_points_detail::consider(
        result,
        closest_points(first.a, second)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& line,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(line, segment, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(line, segment.a);
    closest_points_detail::consider(
        result,
        closest_points(line, segment.b)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& segment,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(
        closest_points(line, segment, eps)
    );
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& first,
    const Segment<T>& second,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(first, second, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(first, second.a);
    closest_points_detail::consider(
        result,
        closest_points(first, second.b)
    );
    closest_points_detail::consider(
        result,
        closest_points(first.a, second)
    );
    closest_points_detail::consider(
        result,
        closest_points(first.b, second)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Line<T>& line,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(line, ray, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    return closest_points(line, ray.origin);
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& ray,
    const Line<T>& line,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(closest_points(line, ray, eps));
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& ray,
    const Segment<T>& segment,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(ray, segment, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(ray, segment.a);
    closest_points_detail::consider(
        result,
        closest_points(ray, segment.b)
    );
    closest_points_detail::consider(
        result,
        closest_points(ray.origin, segment)
    );
    return result;
}

template <Coordinate T>
ClosestPoints closest_points(
    const Segment<T>& segment,
    const Ray<T>& ray,
    long double eps = 1e-12L
) {
    return closest_points_detail::reversed(
        closest_points(ray, segment, eps)
    );
}

template <Coordinate T>
ClosestPoints closest_points(
    const Ray<T>& first,
    const Ray<T>& second,
    long double eps = 1e-12L
) {
    const LinearIntersection intersection =
        linear_intersection(first, second, eps);
    if (intersection.kind != LinearIntersectionKind::Empty) {
        return closest_points_detail::common_point(intersection);
    }
    ClosestPoints result = closest_points(first, second.origin);
    closest_points_detail::consider(
        result,
        closest_points(first.origin, second)
    );
    return result;
}

template <Coordinate T>
long double distance(const Line<T>& line, const Point<T>& point) {
    const ClosestPoints result = closest_points(line, point);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Point<T>& point, const Line<T>& line) {
    return distance(line, point);
}

template <Coordinate T>
long double distance(const Segment<T>& segment, const Point<T>& point) {
    const ClosestPoints result = closest_points(segment, point);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Point<T>& point, const Segment<T>& segment) {
    return distance(segment, point);
}

template <Coordinate T>
long double distance(const Ray<T>& ray, const Point<T>& point) {
    const ClosestPoints result = closest_points(ray, point);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Point<T>& point, const Ray<T>& ray) {
    return distance(ray, point);
}

template <Coordinate T>
long double distance(const Line<T>& first, const Line<T>& second) {
    const ClosestPoints result = closest_points(first, second);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Line<T>& line, const Segment<T>& segment) {
    const ClosestPoints result = closest_points(line, segment);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Segment<T>& segment, const Line<T>& line) {
    return distance(line, segment);
}

template <Coordinate T>
long double distance(const Segment<T>& first, const Segment<T>& second) {
    const ClosestPoints result = closest_points(first, second);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Line<T>& line, const Ray<T>& ray) {
    const ClosestPoints result = closest_points(line, ray);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Ray<T>& ray, const Line<T>& line) {
    return distance(line, ray);
}

template <Coordinate T>
long double distance(const Ray<T>& ray, const Segment<T>& segment) {
    const ClosestPoints result = closest_points(ray, segment);
    return geometry::distance(result.first, result.second);
}

template <Coordinate T>
long double distance(const Segment<T>& segment, const Ray<T>& ray) {
    return distance(ray, segment);
}

template <Coordinate T>
long double distance(const Ray<T>& first, const Ray<T>& second) {
    const ClosestPoints result = closest_points(first, second);
    return geometry::distance(result.first, result.second);
}

}  // namespace geometry
}  // namespace m1une


#line 17 "geometry/half_plane_intersection.hpp"

namespace m1une {
namespace geometry {

enum class HalfPlaneIntersectionStatus {
    Empty,
    Unbounded,
    Degenerate,
    Bounded,
};

struct HalfPlaneIntersectionResult {
    HalfPlaneIntersectionStatus status;
    std::vector<Point<long double>> polygon;
};

namespace half_plane_intersection_detail {

struct HalfPlane {
    Point<long double> point;
    Point<long double> direction;
    long double angle;

    HalfPlane(
        const Point<long double>& point_value,
        const Point<long double>& direction_value
    ) : point(point_value), direction(direction_value) {
        angle = std::atan2(direction.y, direction.x);
        if (angle < 0) angle += 2 * std::numbers::pi_v<long double>;
    }
};

inline bool direction_less(const HalfPlane& first, const HalfPlane& second) {
    return first.angle < second.angle;
}

inline bool parallel(
    const HalfPlane& first,
    const HalfPlane& second,
    long double eps
) {
    return std::fabs(cross(first.direction, second.direction)) <= eps;
}

inline bool same_direction(
    const HalfPlane& first,
    const HalfPlane& second,
    long double eps
) {
    return parallel(first, second, eps) &&
           dot(first.direction, second.direction) > 0;
}

inline bool outside(
    const HalfPlane& half_plane,
    const Point<long double>& point,
    long double eps
) {
    return cross(half_plane.direction, point - half_plane.point) < -eps;
}

inline bool more_restrictive(
    const HalfPlane& candidate,
    const HalfPlane& current,
    long double eps
) {
    return cross(
        current.direction,
        candidate.point - current.point
    ) > eps;
}

inline std::optional<Point<long double>> intersection(
    const HalfPlane& first,
    const HalfPlane& second,
    long double eps
) {
    long double denominator = cross(first.direction, second.direction);
    if (std::fabs(denominator) <= eps) return std::nullopt;
    long double ratio = cross(
        second.point - first.point,
        second.direction
    ) / denominator;
    return first.point + first.direction * ratio;
}

inline void merge_same_direction(
    std::vector<HalfPlane>& half_planes,
    const HalfPlane& half_plane,
    long double eps
) {
    if (
        half_planes.empty() ||
        !same_direction(half_planes.back(), half_plane, eps)
    ) {
        half_planes.push_back(half_plane);
        return;
    }
    if (more_restrictive(half_plane, half_planes.back(), eps)) {
        half_planes.back() = half_plane;
    }
}

inline void merge_cyclic_ends(
    std::vector<HalfPlane>& half_planes,
    long double eps
) {
    if (
        half_planes.size() < 2 ||
        !same_direction(half_planes.front(), half_planes.back(), eps)
    ) {
        return;
    }
    if (more_restrictive(half_planes.back(), half_planes.front(), eps)) {
        half_planes.front() = half_planes.back();
    }
    half_planes.pop_back();
}

inline bool has_feasible_point(
    std::vector<HalfPlane> half_planes,
    long double eps
) {
    std::mt19937_64 generator(0x6a09e667f3bcc909ULL);
    std::shuffle(half_planes.begin(), half_planes.end(), generator);

    Point<long double> feasible(0, 0);
    for (std::size_t index = 0; index < half_planes.size(); ++index) {
        const HalfPlane& current = half_planes[index];
        if (!outside(current, feasible, eps)) continue;

        Point<long double> normal(
            -current.direction.y,
            current.direction.x
        );
        Point<long double> base = normal * dot(normal, current.point);
        long double lower = -std::numeric_limits<long double>::infinity();
        long double upper = std::numeric_limits<long double>::infinity();
        for (std::size_t previous_index = 0;
             previous_index < index;
             ++previous_index) {
            const HalfPlane& previous = half_planes[previous_index];
            long double coefficient = cross(
                previous.direction,
                current.direction
            );
            long double constant = cross(
                previous.direction,
                base - previous.point
            );
            if (std::fabs(coefficient) <= eps) {
                if (constant < -eps) return false;
                continue;
            }

            long double bound = (-eps - constant) / coefficient;
            if (coefficient > 0) {
                lower = std::max(lower, bound);
            } else {
                upper = std::min(upper, bound);
            }
            if (lower > upper) return false;
        }

        long double parameter = 0;
        if (parameter < lower) parameter = lower;
        if (parameter > upper) parameter = upper;
        feasible = base + current.direction * parameter;
    }
    return true;
}

inline bool has_bounded_recession_cone(
    const std::vector<HalfPlane>& half_planes,
    long double eps
) {
    if (half_planes.empty()) return false;

    constexpr long double pi = std::numbers::pi_v<long double>;
    long double maximum_gap =
        half_planes.front().angle + 2 * pi - half_planes.back().angle;
    for (std::size_t index = 1; index < half_planes.size(); ++index) {
        maximum_gap = std::max(
            maximum_gap,
            half_planes[index].angle - half_planes[index - 1].angle
        );
    }
    return maximum_gap < pi - eps;
}

}  // namespace half_plane_intersection_detail

// Each directed line keeps its closed left half-plane. Returns the vertices of
// a bounded intersection with positive area in counterclockwise order. Empty,
// unbounded, and bounded zero-area intersections have distinct statuses.
template <Coordinate T>
HalfPlaneIntersectionResult half_plane_intersection(
    const std::vector<Line<T>>& half_planes,
    long double eps = 1e-12L
) {
    using half_plane_intersection_detail::HalfPlane;
    namespace detail = half_plane_intersection_detail;

    assert(eps >= 0);
    std::vector<HalfPlane> sorted;
    sorted.reserve(half_planes.size());
    for (const Line<T>& line : half_planes) {
        assert(line.a != line.b);
        Point<long double> point(line.a);
        Point<long double> direction = Point<long double>(line.b) - point;
        long double length = norm(direction);
        direction = direction / length;
        sorted.push_back(HalfPlane{point, direction});
    }
    if (!detail::has_feasible_point(sorted, eps)) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Empty,
            {},
        };
    }
    std::sort(sorted.begin(), sorted.end(), detail::direction_less);
    if (!detail::has_bounded_recession_cone(sorted, eps)) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Unbounded,
            {},
        };
    }
    if (sorted.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    std::vector<HalfPlane> unique;
    unique.reserve(sorted.size());
    for (const HalfPlane& half_plane : sorted) {
        detail::merge_same_direction(unique, half_plane, eps);
    }
    detail::merge_cyclic_ends(unique, eps);
    if (unique.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    std::deque<HalfPlane> deque;
    for (const HalfPlane& half_plane : unique) {
        while (deque.size() >= 2) {
            auto point = detail::intersection(
                deque[deque.size() - 2],
                deque.back(),
                eps
            );
            if (!point.has_value()) {
                return HalfPlaneIntersectionResult{
                    HalfPlaneIntersectionStatus::Degenerate,
                    {},
                };
            }
            if (!detail::outside(half_plane, *point, eps)) break;
            deque.pop_back();
        }
        while (deque.size() >= 2) {
            auto point = detail::intersection(deque[0], deque[1], eps);
            if (!point.has_value()) {
                return HalfPlaneIntersectionResult{
                    HalfPlaneIntersectionStatus::Degenerate,
                    {},
                };
            }
            if (!detail::outside(half_plane, *point, eps)) break;
            deque.pop_front();
        }
        deque.push_back(half_plane);
    }

    while (deque.size() >= 3) {
        auto point = detail::intersection(
            deque[deque.size() - 2],
            deque.back(),
            eps
        );
        if (!point.has_value()) {
            return HalfPlaneIntersectionResult{
                HalfPlaneIntersectionStatus::Degenerate,
                {},
            };
        }
        if (!detail::outside(deque.front(), *point, eps)) break;
        deque.pop_back();
    }
    while (deque.size() >= 3) {
        auto point = detail::intersection(deque[0], deque[1], eps);
        if (!point.has_value()) {
            return HalfPlaneIntersectionResult{
                HalfPlaneIntersectionStatus::Degenerate,
                {},
            };
        }
        if (!detail::outside(deque.back(), *point, eps)) break;
        deque.pop_front();
    }
    if (deque.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    std::vector<Point<long double>> polygon;
    polygon.reserve(deque.size());
    for (std::size_t index = 0; index < deque.size(); ++index) {
        auto point = detail::intersection(
            deque[index],
            deque[(index + 1) % deque.size()],
            eps
        );
        if (!point.has_value()) {
            return HalfPlaneIntersectionResult{
                HalfPlaneIntersectionStatus::Degenerate,
                {},
            };
        }
        if (
            polygon.empty() ||
            distance(polygon.back(), *point) > eps
        ) {
            polygon.push_back(*point);
        }
    }
    if (
        polygon.size() >= 2 &&
        distance(polygon.front(), polygon.back()) <= eps
    ) {
        polygon.pop_back();
    }
    if (polygon.size() < 3) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    long double signed_area2 = 0;
    Point<long double> origin = polygon.front();
    for (std::size_t index = 1; index + 1 < polygon.size(); ++index) {
        signed_area2 += cross(
            polygon[index] - origin,
            polygon[index + 1] - origin
        );
    }
    if (signed_area2 <= eps) {
        return HalfPlaneIntersectionResult{
            HalfPlaneIntersectionStatus::Degenerate,
            {},
        };
    }

    auto first = std::min_element(polygon.begin(), polygon.end());
    std::rotate(polygon.begin(), first, polygon.end());
    return HalfPlaneIntersectionResult{
        HalfPlaneIntersectionStatus::Bounded,
        std::move(polygon),
    };
}

}  // namespace geometry
}  // namespace m1une
Back to top page