茂之钳
65 lines
1.7 KiB
C++
65 lines
1.7 KiB
C++
#pragma once
|
|
#include "vde/core/point.h"
|
|
#include <vector>
|
|
#include <array>
|
|
|
|
namespace vde::core {
|
|
using foundation::Point2D;
|
|
using foundation::Point3D;
|
|
using foundation::Vector2D;
|
|
using foundation::Vector3D;
|
|
|
|
/**
|
|
* @brief Voronoi 单元格
|
|
*
|
|
* 表示二维 Voronoi 图中的一个单元格，
|
|
* 包含生成点 site 以及该单元格的边界顶点和边。
|
|
*
|
|
* @ingroup core
|
|
*/
|
|
struct VoronoiCell {
|
|
/// 生成点（站点）
|
|
Point2D site;
|
|
|
|
/**
|
|
* @brief 单元格边界顶点（按逆时针顺序排列）
|
|
*
|
|
* 对于无界单元格，顶点列表可能不闭合。
|
|
*/
|
|
std::vector<Point2D> vertices;
|
|
|
|
/**
|
|
* @brief 单元格边界边
|
|
*
|
|
* 每条边表示为 vertices 中的两个索引。
|
|
*/
|
|
std::vector<std::array<int, 2>> edges;
|
|
};
|
|
|
|
/**
|
|
* @brief 二维 Voronoi 图生成（通过 Delaunay 对偶图）
|
|
*
|
|
* 从输入点集的 Delaunay 三角剖分构造其对偶 Voronoi 图。
|
|
* 每个输入点对应一个 VoronoiCell。
|
|
*
|
|
* @param points 输入点集（站点）
|
|
* @return 每个站点对应的 VoronoiCell 列表（顺序与输入一致）
|
|
*
|
|
* @note 对于凸包边界上的站点，对应的 Voronoi 单元格无界，顶点不完全闭合
|
|
* @note 内部使用 Delaunay 三角剖分作为中间步骤
|
|
*
|
|
* @code{.cpp}
|
|
* std::vector<Point2D> sites = {{0,0}, {1,0}, {0,1}, {1,1}};
|
|
* auto cells = voronoi_2d(sites);
|
|
* for (auto& cell : cells) {
|
|
* std::cout << "Site: " << cell.site.transpose() << "\n";
|
|
* std::cout << " Vertices: " << cell.vertices.size() << "\n";
|
|
* }
|
|
* @endcode
|
|
*
|
|
* @ingroup core
|
|
*/
|
|
std::vector<VoronoiCell> voronoi_2d(const std::vector<Point2D>& points);
|
|
|
|
} // namespace vde::core
|