如何在CGAL中关联点标签并遍历给定点的关联Delaunay四面体？

一、保留/重建点与标签的关联 #

方法1：自定义带标签的点类型 #

直接扩展CGAL的点类型，让每个点自带标签，这样剖分构建时标签信息不会丢失。

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>

// 自定义带标签的点结构，适配CGAL内核要求
struct LabeledPoint {
    double x, y, z;
    int label;

    LabeledPoint(double x_, double y_, double z_, int label_) 
        : x(x_), y(y_), z(z_), label(label_) {}

    // CGAL内核要求的坐标访问接口
    double x() const { return x; }
    double y() const { return y; }
    double z() const { return z; }
};

// 基于自定义点类型构建内核
struct MyKernel : CGAL::Exact_predicates_inexact_constructions_kernel {
    typedef LabeledPoint Point_3;
};

// 使用自定义内核的Delaunay剖分类型
typedef CGAL::Delaunay_triangulation_3<MyKernel> Delaunay;

// 修改构建代码
Agregat myag(mystr);
std::list<LabeledPoint> L;
for (int i = 1 ; i < myag.Nbt() ; i++){
    // 替换i为实际标签字段，比如myag.get_label(i)
    L.push_front(LabeledPoint(myag.X(i), myag.Y(i), myag.Z(i), i)); 
}

Delaunay T(L.begin(), L.end());

方法2：构建点到标签的映射 #

如果不想修改点类型，可以在构建点列表时同步创建映射表，后续通过CGAL点对象反向查找标签。

#include <map>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_3 Point;
typedef CGAL::Delaunay_triangulation_3<K> Delaunay;

// 构建点列表与映射表
Agregat myag(mystr);
std::list<Point> L;
std::map<Point, int> point_to_label; // 若用unordered_map需自定义Point的哈希函数

for (int i = 1 ; i < myag.Nbt() ; i++){
    Point p(myag.X(i), myag.Y(i), myag.Z(i));
    L.push_front(p);
    // 替换i为实际标签字段
    point_to_label[p] = i; 
}

Delaunay T(L.begin(), L.end());

注意：输入点需保证唯一，否则映射表会覆盖重复点的标签（Delaunay剖分本身会合并重合点）。

二、遍历点关联的四面体并关联标签 #

CGAL提供了现成的迭代器和方法来遍历顶点及关联的四面体，以下是实现示例：

基于自定义点类型的实现 #

// 遍历所有有限顶点
for (auto vit = T.finite_vertices_begin(); vit != T.finite_vertices_end(); ++vit) {
    // 获取当前点的标签
    const LabeledPoint& lp = vit->point();
    int current_label = lp.label;
    std::cout << "点标签: " << current_label << "，关联的四面体：" << std::endl;

    // 获取当前顶点关联的所有胞腔（四面体）
    typedef Delaunay::Cell_handle Cell_handle;
    std::vector<Cell_handle> adjacent_cells;
    T.incident_cells(vit, std::back_inserter(adjacent_cells));

    // 遍历每个四面体
    for (Cell_handle ch : adjacent_cells) {
        if (T.is_infinite(ch)) continue; // 跳过无限胞腔

        // 输出四面体的四个顶点标签
        std::cout << "  四面体顶点标签: ";
        for (int i = 0; i < 4; ++i) {
            const LabeledPoint& p = ch->vertex(i)->point();
            std::cout << p.label << " ";
        }
        std::cout << std::endl;
    }
}

基于映射表的实现 #

只需将获取标签的部分替换为：

const Point& p = vit->point();
int current_label = point_to_label[p];

关键接口说明 #

• T.finite_vertices_begin()/T.finite_vertices_end()：遍历所有有限顶点的迭代器（跳过剖分边界的无限顶点）。
• T.incident_cells(vit, output_iterator)：获取顶点vit关联的所有胞腔，包含无限胞腔，需用T.is_infinite(ch)过滤。
• ch->vertex(i)：获取四面体的第i个顶点（i取值0-3），返回Vertex_handle，通过->point()获取点对象。

内容的提问来源于stack exchange，提问作者user22744