geometry/detail/floating_predicate.hpp

• View this file on GitHub
• Last update: 2026-08-20 21:15:27+09:00
• Include: #include "geometry/detail/floating_predicate.hpp"

Required by

• Geometry Bundle (geometry/all.hpp)
• Angle Sort (geometry/angle_sort.hpp)
• Circles (geometry/circle.hpp)
• Circle Coverage Areas (geometry/circle_coverage_areas.hpp)
• Area of Union of Circles (geometry/circle_union_area.hpp)
• Closest Pair of Points (geometry/closest_pair.hpp)
• Convex Decomposition (geometry/convex_decomposition.hpp)
• Convex Hull (geometry/convex_hull.hpp)
• Convex Layers (geometry/convex_layers.hpp)
• Convex Polygons (geometry/convex_polygon.hpp)
• Count Points in Triangle (geometry/count_points_in_triangle.hpp)
• Delaunay Triangulation (geometry/delaunay_triangulation.hpp)
• geometry/detail/convex_polygon_normalize.hpp
• Euclidean Minimum Spanning Tree (geometry/euclidean_mst.hpp)
• Farthest Pair of Points (geometry/farthest_pair.hpp)
• Half-Plane Intersection (geometry/half_plane_intersection.hpp)
• Linear Objects (geometry/linear.hpp)
• Manhattan Minimum Spanning Tree (geometry/manhattan_mst.hpp)
• Manhattan Segment Intersections (geometry/manhattan_segment_intersections.hpp)
• Minimum Enclosing Circle (geometry/minimum_enclosing_circle.hpp)
• Minkowski Sum (geometry/minkowski_sum.hpp)
• Perpendicular Bisector (geometry/perpendicular_bisector.hpp)
• 2D Point and Predicates (geometry/point.hpp)
• Polygons (geometry/polygon.hpp)
• Area of Union of Rectangles (geometry/rectangle_union_area.hpp)
• Steiner Convex Decomposition (geometry/steiner_convex_decomposition.hpp)
• Voronoi Diagram (geometry/voronoi_diagram.hpp)

Verified with

• verify/geometry/angle_sort.test.cpp
• verify/geometry/centroid.test.cpp
• verify/geometry/circle_boundary_intersection.test.cpp
• verify/geometry/circle_circle_intersection.test.cpp
• verify/geometry/circle_circle_intersection_area.test.cpp
• verify/geometry/circle_common_tangents.test.cpp
• verify/geometry/circle_coverage_areas.test.cpp
• verify/geometry/circle_filled.test.cpp
• verify/geometry/circle_line_intersection.test.cpp
• verify/geometry/circle_operations.test.cpp
• verify/geometry/circle_polygon_intersection_area.test.cpp
• verify/geometry/circle_ray.test.cpp
• verify/geometry/circle_relation.test.cpp
• verify/geometry/circle_tangent_points.test.cpp
• verify/geometry/circle_union_area.test.cpp
• verify/geometry/circumcircle.test.cpp
• verify/geometry/closest_pair.test.cpp
• verify/geometry/closest_points.test.cpp
• verify/geometry/convex_decomposition.test.cpp
• verify/geometry/convex_diameter.test.cpp
• verify/geometry/convex_hull.test.cpp
• verify/geometry/convex_layers.test.cpp
• verify/geometry/convex_polygon.test.cpp
• verify/geometry/count_points_in_triangle.test.cpp
• verify/geometry/delaunay_triangulation.test.cpp
• verify/geometry/euclidean_mst.test.cpp
• verify/geometry/farthest_pair.test.cpp
• verify/geometry/floating_predicates.test.cpp
• verify/geometry/geometry_algorithms.test.cpp
• verify/geometry/half_plane_intersection.test.cpp
• verify/geometry/half_plane_intersection_random.test.cpp
• verify/geometry/incircle.test.cpp
• verify/geometry/is_convex_polygon.test.cpp
• verify/geometry/linear_intersection.test.cpp
• verify/geometry/manhattan_mst.test.cpp
• verify/geometry/manhattan_segment_intersections.test.cpp
• verify/geometry/minimum_enclosing_circle.test.cpp
• verify/geometry/minkowski_sum.test.cpp
• verify/geometry/perpendicular_bisector.test.cpp
• verify/geometry/point_in_polygon.test.cpp
• verify/geometry/polygon_area.test.cpp
• verify/geometry/polygon_clipping.test.cpp
• verify/geometry/polygon_filled.test.cpp
• verify/geometry/polygon_operations.test.cpp
• verify/geometry/projection.test.cpp
• verify/geometry/rational.test.cpp
• verify/geometry/ray.test.cpp
• verify/geometry/rectangle_union_area.test.cpp
• verify/geometry/segment_intersection.test.cpp
• verify/geometry/segment_intersection_point.test.cpp
• verify/geometry/steiner_convex_decomposition.test.cpp
• verify/geometry/voronoi_diagram.test.cpp

Code

#ifndef M1UNE_GEOMETRY_DETAIL_FLOATING_PREDICATE_HPP
#define M1UNE_GEOMETRY_DETAIL_FLOATING_PREDICATE_HPP 1

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

#endif  // M1UNE_GEOMETRY_DETAIL_FLOATING_PREDICATE_HPP

#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

Back to top page