ViewDesignEngine/include/vde/core/polygon.h

#pragma once
#include "vde/core/point.h"
#include "vde/core/aabb.h"
#include <vector>
#include <array>

namespace vde::core {

/**
 * @brief 二维平面多边形
 *
 * 支持面积计算、点包含测试、简化和三角剖分。
 * 顶点按顺序排列（闭合多边形），不存储首尾重复顶点。
 *
 * @note 内部假设简单多边形（无自交），非简单多边形的行为未定义
 * @note 所有几何计算基于（假设的）XY 平面
 *
 * @ingroup core
 */
class Polygon2D {
public:
    /// 构造空多边形
    Polygon2D() = default;

    /**
     * @brief 从顶点列表构造多边形
     *
     * @param vertices 顶点序列（逆时针或顺时针均可）
     */
    explicit Polygon2D(std::vector<Point2D> vertices) : vertices_(std::move(vertices)) {}

    /// 获取顶点列表
    [[nodiscard]] const std::vector<Point2D>& vertices() const { return vertices_; }
    /// 获取顶点数量
    [[nodiscard]] size_t size() const { return vertices_.size(); }
    /// 多边形是否为空（< 3 个顶点视为退化）
    [[nodiscard]] bool empty() const { return vertices_.empty(); }

    /**
     * @brief 有向面积（Shoelace 公式）
     *
     * 正值表示逆时针（CCW），负值表示顺时针（CW），零表示自交或退化。
     *
     * @return 有向面积
     *
     * @code{.cpp}
     * Polygon2D poly({{0,0}, {1,0}, {0,1}});
     * double sa = poly.signed_area(); // > 0 (CCW)
     * @endcode
     */
    [[nodiscard]] double signed_area() const;

    /**
     * @brief 绝对面积
     * @return |signed_area()|
     */
    [[nodiscard]] double area() const { return std::abs(signed_area()); }

    /**
     * @brief 周长（各边长之和）
     * @return 总边长
     */
    [[nodiscard]] double perimeter() const;

    /**
     * @brief 面积加权质心
     *
     * 使用多边形三角剖分的面积加权平均计算质心。
     * 适用于非自交的任意多边形。
     *
     * @return 质心坐标
     */
    [[nodiscard]] Point2D centroid() const;

    /**
     * @brief 二维轴对齐包围盒
     *
     * 返回 AABB（z=0），min/max 的 z 分量均为 0。
     *
     * @return 包围盒
     */
    [[nodiscard]] AABB<double> bounding_box() const;

    /**
     * @brief 点包含测试（射线法）
     *
     * 从测试点向右发射水平射线，计算与多边形边的交点数量。
     * 奇数次交点在内部，偶数次在外部。
     *
     * @param p 测试点
     * @return true 若点在多边形内部或边界上
     *
     * @note 边界上的点也返回 true
     */
    [[nodiscard]] bool contains(const Point2D& p) const;

    /**
     * @brief 多边形是否为逆时针方向
     * @return signed_area() > 0
     */
    [[nodiscard]] bool is_ccw() const { return signed_area() > 0; }

    /**
     * @brief Douglas-Peucker 简化
     *
     * 用递归的 Douglas-Peucker 算法减少顶点数量，
     * 保证简化后多边形与原多边形的最大偏差不超过 tolerance。
     *
     * @param tolerance 允许的最大偏差
     * @return 简化后的新多边形
     *
     * @code{.cpp}
     * // 将 1000 个顶点的多边形简化为约 100 个
     * auto simple = poly.simplify(0.01);
     * @endcode
     *
     * @see triangulate
     */
    [[nodiscard]] Polygon2D simplify(double tolerance) const;

    /**
     * @brief 耳切法三角剖分（Ear Clipping）
     *
     * 将简单多边形剖分为三角形，返回每个三角形的顶点索引三元组。
     *
     * @return 三角形列表，每个元素为 {i, j, k} 表示顶点索引
     *
     * @pre 多边形为简单多边形（无自交）
     * @pre 顶点为逆时针顺序（CCW）
     *
     * @note 时间复杂度 O(n²)，适用于顶点数 < 1000 的多边形
     *
     * @code{.cpp}
     * Polygon2D poly(CCW vertices);
     * auto tris = poly.triangulate();
     * for (auto& t : tris) {
     *     // 顶点: poly.vertices()[t[0]], t[1], t[2]
     * }
     * @endcode
     *
     * @see simplify
     */
    [[nodiscard]] std::vector<std::array<int, 3>> triangulate() const;

    /**
     * @brief Andrew's Monotone Chain 二维凸包
     *
     * 计算点集的凸包，返回逆时针排列的凸包多边形。
     * 时间复杂度 O(n log n)。
     *
     * @param points 输入点集
     * @return 凸包多边形（CCW，不含共线中间点）
     *
     * @see convex_hull_2d
     */
    static Polygon2D convex_hull_2d(const std::vector<Point2D>& points);

private:
    std::vector<Point2D> vertices_;
};

}  // namespace vde::core