2026-07-23 07:04:11 +00:00
|
|
|
|
#pragma once
|
|
|
|
|
|
#include "vde/mesh/delaunay_2d.h"
|
|
|
|
|
|
#include "vde/core/line.h"
|
|
|
|
|
|
#include <vector>
|
|
|
|
|
|
|
|
|
|
|
|
namespace vde::mesh {
|
2026-07-23 08:19:24 +00:00
|
|
|
|
using core::Point2D;
|
|
|
|
|
|
using core::Point3D;
|
|
|
|
|
|
using core::Vector3D;
|
2026-07-23 07:04:11 +00:00
|
|
|
|
|
2026-07-24 11:04:04 +00:00
|
|
|
|
/**
|
|
|
|
|
|
* @brief 约束 Delaunay 三角化（CDT）
|
|
|
|
|
|
*
|
|
|
|
|
|
* 在标准 Delaunay 三角化基础上强制指定的约束边必须出现在三角化中。
|
|
|
|
|
|
* 通过边翻转（edge flip）反复消除与约束边相交的三角形边，直到所有
|
|
|
|
|
|
* 约束边都成为三角形边。
|
|
|
|
|
|
*
|
|
|
|
|
|
* 约束边在输出三角化中一定存在（作为三角形边），但不保证满足
|
|
|
|
|
|
* 空圆性质——靠近约束边的三角形可能违反 Delaunay 条件。
|
|
|
|
|
|
*
|
|
|
|
|
|
* @param points 输入 2D 点集
|
|
|
|
|
|
* @param constraints 约束边列表，每项为 {起点索引, 终点索引}
|
|
|
|
|
|
* @return DelaunayResult 含约束边的三角化结果
|
|
|
|
|
|
*
|
|
|
|
|
|
* @note 约束边不能相交（否则行为未定义）；自相交约束需先分割交点
|
|
|
|
|
|
* @code{.cpp}
|
|
|
|
|
|
* // 带孔洞的三角化：约束边标记孔洞边界
|
|
|
|
|
|
* auto result = constrained_delaunay_2d(points,
|
|
|
|
|
|
* {{0,1}, {1,2}, {2,1}, {3,0}});
|
|
|
|
|
|
* @endcode
|
|
|
|
|
|
* @see delaunay_2d
|
|
|
|
|
|
* @ingroup mesh
|
|
|
|
|
|
*/
|
2026-07-23 07:04:11 +00:00
|
|
|
|
DelaunayResult constrained_delaunay_2d(
|
|
|
|
|
|
const std::vector<Point2D>& points,
|
|
|
|
|
|
const std::vector<std::pair<int, int>>& constraints);
|
|
|
|
|
|
|
|
|
|
|
|
} // namespace vde::mesh
|
