ViewDesignEngine/include/vde/foundation/exact_predicates.h

#pragma once
#include "vde/foundation/math_types.h"

namespace vde::foundation::exact {

/**
 * @brief 二维定向测试结果
 *
 * 判断三点构成的三角形的定向（顺时针 / 逆时针 / 共线）。
 *
 * @ingroup foundation
 */
enum class Orientation { Clockwise, CounterClockwise, Collinear };

/**
 * @brief 圆测试结果
 *
 * 判断点 d 相对于三角形 abc 外接圆的位置。
 *
 * @ingroup foundation
 */
enum class CircleTest { Inside, On, Outside };

/**
 * @brief 自适应精度二维定向测试（Shewchuk 算法）
 *
 * 判断点 a, b, c 的定向。使用自适应浮点精度：
 * 先用双精度计算行列式，若结果不可靠则逐步提高精度，直至确定符号。
 *
 * @param a 第一个点
 * @param b 第二个点
 * @param c 第三个点
 * @return Orientation::Clockwise 若 a→b→c 顺时针
 * @return Orientation::CounterClockwise 若 a→b→c 逆时针
 * @return Orientation::Collinear 若三点共线
 *
 * @note Delaunay 三角剖分、凸包计算等几何算法的核心原语
 * @warning 输入点坐标必须为有限值，NaN/Inf 会导致未定义行为
 *
 * @code{.cpp}
 * Point2D a(0,0), b(1,0), c(0,1);
 * auto ori = exact::orient_2d(a, b, c);
 * // ori == Orientation::CounterClockwise
 * @endcode
 *
 * @see orient_3d, in_circle
 * @ingroup foundation
 */
Orientation orient_2d(const Point2D& a, const Point2D& b, const Point2D& c);

/**
 * @brief 自适应精度三维定向测试
 *
 * 判断点 a, b, c, d 的定向（即点 d 在平面 abc 的哪一侧）。
 * 等价于计算四面体 abcd 的有向体积的符号。
 *
 * @param a 第一个点
 * @param b 第二个点
 * @param c 第三个点
 * @param d 第四个点（测试点）
 * @return Orientation::CounterClockwise 若 d 在平面 abc 上方（按右手法则）
 * @return Orientation::Clockwise 若 d 在平面 abc 下方
 * @return Orientation::Collinear 若四点共面
 *
 * @note 三维 Delaunay 剖分和凸包计算的核心原语
 *
 * @code{.cpp}
 * Point3D a(0,0,0), b(1,0,0), c(0,1,0), d(0,0,1);
 * auto ori = exact::orient_3d(a, b, c, d);
 * // ori == Orientation::CounterClockwise
 * @endcode
 *
 * @see orient_2d, in_circle
 * @ingroup foundation
 */
Orientation orient_3d(const Point3D& a, const Point3D& b,
                      const Point3D& c, const Point3D& d);

/**
 * @brief 自适应精度圆内测试（In-Circle Test）
 *
 * 判断点 d 是否在三角形 abc 的外接圆内部、边界上或外部。
 * 等价于计算 4×4 行列式的符号。
 *
 * @param a 三角形第一个顶点
 * @param b 三角形第二个顶点
 * @param c 三角形第三个顶点
 * @param d 待测试点
 * @return CircleTest::Inside 若 d 在三角形外接圆内部
 * @return CircleTest::On 若 d 恰好在三角形外接圆上
 * @return CircleTest::Outside 若 d 在三角形外接圆外部
 *
 * @note Delaunay 三角剖分的空圆性质检查核心原语
 * @pre 三点 a、b、c 不共线
 *
 * @code{.cpp}
 * Point2D a(0,0), b(2,0), c(0,2);
 * Point2D d(0.5, 0.5);  // 在外接圆内部
 * auto result = exact::in_circle(a, b, c, d);
 * // result == CircleTest::Inside
 * @endcode
 *
 * @see orient_2d, orient_3d
 * @ingroup foundation
 */
CircleTest in_circle(const Point2D& a, const Point2D& b,
                     const Point2D& c, const Point2D& d);

}  // namespace vde::foundation::exact

/**
 * @brief 自适应双精度谓词后端（默认）
 *
 * 封装 exact 命名空间下的自适应精度谓词函数，
 * 作为 Predicates 的默认后端实现。
 *
 * @ingroup foundation
 */
namespace vde::foundation {
struct AdaptiveDouble {
    /**
     * @brief 二维定向测试
     * @param a,b,c 三个二维点
     * @return 定向结果
     * @see exact::orient_2d
     */
    static exact::Orientation orient_2d(const Point2D& a, const Point2D& b, const Point2D& c) {
        return exact::orient_2d(a, b, c);
    }
    /**
     * @brief 三维定向测试
     * @param a,b,c,d 四个三维点
     * @return 定向结果
     * @see exact::orient_3d
     */
    static exact::Orientation orient_3d(const Point3D& a, const Point3D& b,
                                  const Point3D& c, const Point3D& d) {
        return exact::orient_3d(a, b, c, d);
    }
    /**
     * @brief 圆内测试
     * @param a,b,c 三角形三顶点
     * @param d 待测试点
     * @return 圆测试结果
     * @see exact::in_circle
     */
    static exact::CircleTest in_circle(const Point2D& a, const Point2D& b,
                                const Point2D& c, const Point2D& d) {
        return exact::in_circle(a, b, c, d);
    }
};
}  // namespace vde::foundation