茂之钳
163 lines
4.5 KiB
C++
163 lines
4.5 KiB
C++
#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
|