相关章节: CGAL的STL扩展 | 循环迭代器 | 半边数据结构 | 组合地图
3.3 属性映射（Property Map）
0. 实际问题：给几何附加数据
想象你在开发一个3D建模软件，需要给几何元素附加各种数据：
实际场景：
- 给每个顶点存储颜色（用于显示）
- 给每个面存储材质ID（用于渲染）
- 给每条边存储是否选中（用于编辑）
- 给每个顶点存储温度值（用于仿真）
方法1：直接在类中添加成员（紧耦合）
class MyVertex {
Point_3 position;
Color color; // 硬编码的属性
int material_id; // 另一个硬编码属性
bool is_selected; // 又一个硬编码属性
double temperature; // 还需要更多属性...
public:
MyVertex() : color(0, 0, 0), material_id(0),
is_selected(false), temperature(0.0) {}
};
// 问题：
// 1. 修改属性需要改类定义，不灵活
// 2. 所有顶点都占用相同内存，即使不需要某些属性
// 3. 无法运行时决定需要哪些属性
// 4. 不同算法需要不同属性，类会变得臃肿方法2：使用外部映射（松散耦合）
std::map<Vertex_handle, Color> vertex_colors;
std::map<Vertex_handle, int> vertex_materials;
std::map<Vertex_handle, bool> vertex_selection;
std::map<Vertex_handle, double> vertex_temperatures;
// 问题：
// 1. 管理多个映射复杂，代码分散
// 2. 每个map都有较大的内存开销（红黑树节点）
// 3. 访问速度慢（O(log n)）
// 4. 没有统一的接口，使用不便
// 5. 需要手动同步生命周期（顶点删除时从所有map删除）方法3：Property Map（最佳实践）
// CGAL的解决方案：统一的Property Map接口
Mesh mesh;
// 动态添加属性
auto color_map = mesh.add_property_map<Vertex_index, Color>("v:color");
auto material_map = mesh.add_property_map<Face_index, int>("f:material");
auto selection_map = mesh.add_property_map<Edge_index, bool>("e:selected");
// 统一的使用方式
color_map[vertex] = Color(255, 0, 0);
material_map[face] = 42;
selection_map[edge] = true;
// 优势：
// 1. 动态添加/删除属性，无需修改类定义
// 2. 统一的get/put接口
// 3. O(1)访问速度
// 4. 自动内存管理
// 5. 类型安全1. 渐进学习：从简单到复杂
步骤1：理解基本概念
什么是Property Map？
想象Property Map就像一张标签系统：
- 钥匙（Key）：几何元素（顶点、边、面）
- 值（Value）：你想存储的数据（颜色、权重、标记）
- 映射（Map）：从钥匙到值的查找表
// 生活中的类比：学生成绩表
// 键：学生ID（类似于Vertex_index）
// 值：成绩（类似于颜色、温度等属性）
std::map<std::string, double> grade_map;
grade_map["Alice"] = 95.5; // 类似于 color_map[vertex] = red;
grade_map["Bob"] = 87.0; // 类似于 color_map[vertex2] = blue;步骤2：使用指针数组实现（最基础）
#include <vector>
#include <iostream>
// 最简单的Property Map：指针数组
// 假设我们有5个顶点，索引为0-4
int main() {
// 创建顶点温度属性（类似于数组）
std::vector<double> vertex_temperatures(5, 0.0);
// 设置属性（O(1)时间）
vertex_temperatures[0] = 37.5;
vertex_temperatures[1] = 36.8;
vertex_temperatures[2] = 38.2;
// 获取属性
std::cout << "Vertex 0 temperature: " << vertex_temperatures[0] << "°C" << std::endl;
// 优点：最简单，访问最快
// 缺点：只能使用整数索引，不灵活
return 0;
}步骤3：使用std::map（灵活但慢）
#include <map>
#include <iostream>
#include <string>
// 使用句柄（类似于指针）作为键
struct Vertex_handle {
int id;
explicit Vertex_handle(int i) : id(i) {}
// 需要为map提供比较运算符
bool operator<(const Vertex_handle& other) const {
return id < other.id;
}
};
int main() {
// 使用map作为Property Map
std::map<Vertex_handle, double> temperature_map;
// 设置属性（O(log n)时间）
temperature_map[Vertex_handle(0)] = 37.5;
temperature_map[Vertex_handle(1)] = 36.8;
// 获取属性
std::cout << "Temperature: " << temperature_map[Vertex_handle(0)] << std::endl;
// 优点：可以使用任意类型作为键
// 缺点：访问较慢，内存开销大
return 0;
}步骤4：使用CGAL Property Map（高效且灵活）
#include <CGAL/property_map.h>
#include <vector>
#include <iostream>
int main() {
// 数据存储
std::vector<double> temperatures = {37.5, 36.8, 38.2, 37.0};
// 创建CGAL Property Map
auto temp_map = CGAL::make_property_map(temperatures);
// 使用统一的get/put接口
double t0 = get(temp_map, 0); // 获取
std::cout << "Vertex 0: " << t0 << std::endl;
put(temp_map, 0, 37.8); // 设置
std::cout << "Updated: " << get(temp_map, 0) << std::endl;
// 优点：
// 1. 统一的接口（所有Property Map都支持get/put）
// 2. 可以与CGAL算法无缝集成
// 3. 零开销抽象（性能与直接访问数组相同）
return 0;
}步骤5：使用Surface_mesh动态属性（推荐）
#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Vertex_index Vertex_index;
int main() {
Mesh mesh;
// 创建一些顶点
Vertex_index v0 = mesh.add_vertex(Point_3(0, 0, 0));
Vertex_index v1 = mesh.add_vertex(Point_3(1, 0, 0));
Vertex_index v2 = mesh.add_vertex(Point_3(0, 1, 0));
// 动态添加颜色属性
auto color_map = mesh.add_property_map<Vertex_index,
std::array<unsigned char, 3>>("v:color");
// 设置颜色
color_map[v0] = {255, 0, 0}; // 红色
color_map[v1] = {0, 255, 0}; // 绿色
color_map[v2] = {0, 0, 255}; // 蓝色
// 遍历所有顶点并输出颜色
for (Vertex_index v : mesh.vertices()) {
auto color = color_map[v];
std::cout << "Vertex " << v << ": RGB("
<< (int)color[0] << ", "
<< (int)color[1] << ", "
<< (int)color[2] << ")" << std::endl;
}
return 0;
}2. Property Map实战食谱（Cookbook）
模式1：顶点颜色映射
场景：给网格上色，用于可视化
#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Vertex_index Vertex_index;
struct Color {
unsigned char r, g, b;
Color(unsigned char r=0, unsigned char g=0, unsigned char b=0)
: r(r), g(g), b(b) {}
};
int main() {
Mesh mesh;
// 创建四面体
Vertex_index v0 = mesh.add_vertex(Point_3(0, 0, 0));
Vertex_index v1 = mesh.add_vertex(Point_3(1, 0, 0));
Vertex_index v2 = mesh.add_vertex(Point_3(0, 1, 0));
Vertex_index v3 = mesh.add_vertex(Point_3(0, 0, 1));
mesh.add_face(v0, v1, v2);
mesh.add_face(v0, v1, v3);
mesh.add_face(v0, v2, v3);
mesh.add_face(v1, v2, v3);
// 添加颜色属性
auto color_map = mesh.add_property_map<Vertex_index, Color>("v:color").first;
// 根据顶点高度设置颜色（热力图效果）
for (Vertex_index v : mesh.vertices()) {
Point_3 p = mesh.point(v);
double height = p.z(); // 使用z坐标作为高度
// 高度越低越蓝，越高越红
unsigned char red = static_cast<unsigned char>(255 * height);
unsigned char blue = static_cast<unsigned char>(255 * (1 - height));
color_map[v] = Color(red, 0, blue);
}
// 输出颜色信息
std::cout << "Vertex colors (heatmap):" << std::endl;
for (Vertex_index v : mesh.vertices()) {
Color c = color_map[v];
std::cout << " Vertex " << v << ": RGB("
<< (int)c.r << ", " << (int)c.g << ", " << (int)c.b << ")"
<< std::endl;
}
return 0;
}模式2：边权重映射
场景：最短路径计算、网络流
#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
#include <cmath>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Vertex_index Vertex_index;
typedef Mesh::Edge_index Edge_index;
int main() {
Mesh mesh;
// 创建网格
Vertex_index v0 = mesh.add_vertex(Point_3(0, 0, 0));
Vertex_index v1 = mesh.add_vertex(Point_3(1, 0, 0));
Vertex_index v2 = mesh.add_vertex(Point_3(1, 1, 0));
Vertex_index v3 = mesh.add_vertex(Point_3(0, 1, 0));
mesh.add_face(v0, v1, v2);
mesh.add_face(v0, v2, v3);
// 添加边权重属性（用于最短路径）
auto weight_map = mesh.add_property_map<Edge_index, double>("e:weight").first;
// 计算边长度作为权重
for (Edge_index e : mesh.edges()) {
auto h = mesh.halfedge(e);
Vertex_index src = mesh.source(h);
Vertex_index tgt = mesh.target(h);
Point_3 p1 = mesh.point(src);
Point_3 p2 = mesh.point(tgt);
// 欧几里得距离
double weight = std::sqrt(CGAL::squared_distance(p1, p2));
weight_map[e] = weight;
std::cout << "Edge " << e << " (" << src << "->" << tgt
<< "): weight = " << weight << std::endl;
}
return 0;
}模式3：面法向量缓存
场景：加速渲染，避免重复计算
#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef Kernel::Vector_3 Vector_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Face_index Face_index;
// 计算并缓存面法向量
void compute_and_cache_face_normals(Mesh& mesh) {
// 获取或添加法向量属性
auto normal_map = mesh.add_property_map<Face_index, Vector_3>("f:normal").first;
for (Face_index f : mesh.faces()) {
// 获取面的三个顶点
auto h = mesh.halfedge(f);
Point_3 p0 = mesh.point(mesh.source(h));
Point_3 p1 = mesh.point(mesh.target(h));
Point_3 p2 = mesh.point(mesh.target(mesh.next(h)));
// 计算法向量（叉积）
Vector_3 v1 = p1 - p0;
Vector_3 v2 = p2 - p0;
Vector_3 normal = CGAL::cross_product(v1, v2);
// 归一化
normal = normal / std::sqrt(normal.squared_length());
// 缓存结果
normal_map[f] = normal;
}
}
int main() {
Mesh mesh;
// 创建三角形
auto v0 = mesh.add_vertex(Point_3(0, 0, 0));
auto v1 = mesh.add_vertex(Point_3(1, 0, 0));
auto v2 = mesh.add_vertex(Point_3(0, 1, 0));
auto v3 = mesh.add_vertex(Point_3(0, 0, 1));
mesh.add_face(v0, v1, v2);
mesh.add_face(v0, v1, v3);
// 计算法向量
compute_and_cache_face_normals(mesh);
// 使用缓存的法向量
auto normal_map = mesh.property_map<Face_index, Vector_3>("f:normal").value();
std::cout << "Face normals:" << std::endl;
for (Face_index f : mesh.faces()) {
Vector_3 n = normal_map[f];
std::cout << " Face " << f << ": ("
<< n.x() << ", " << n.y() << ", " << n.z() << ")" << std::endl;
}
return 0;
}模式4：临时标记（Visitor模式）
场景：遍历算法中的访问标记，避免重复访问
#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <queue>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Vertex_index Vertex_index;
// 使用Property Map实现BFS遍历
void bfs_traverse(Mesh& mesh, Vertex_index start) {
// 临时添加访问标记属性
auto visited_map = mesh.add_property_map<Vertex_index, bool>("v:visited", false).first;
auto distance_map = mesh.add_property_map<Vertex_index, int>("v:distance", -1).first;
std::queue<Vertex_index> queue;
// 初始化起点
visited_map[start] = true;
distance_map[start] = 0;
queue.push(start);
std::cout << "BFS traversal starting from vertex " << start << ":" << std::endl;
while (\!queue.empty()) {
Vertex_index v = queue.front();
queue.pop();
std::cout << " Visited vertex " << v
<< " (distance: " << distance_map[v] << ")" << std::endl;
// 遍历所有邻居
for (auto h : mesh.halfedges_around_target(mesh.halfedge(v))) {
Vertex_index neighbor = mesh.source(h);
if (\!visited_map[neighbor]) {
visited_map[neighbor] = true;
distance_map[neighbor] = distance_map[v] + 1;
queue.push(neighbor);
}
}
}
// 清理：删除临时属性
mesh.remove_property_map(visited_map);
mesh.remove_property_map(distance_map);
}
int main() {
Mesh mesh;
// 创建简单网格（2x2）
auto v00 = mesh.add_vertex(Point_3(0, 0, 0));
auto v10 = mesh.add_vertex(Point_3(1, 0, 0));
auto v20 = mesh.add_vertex(Point_3(2, 0, 0));
auto v01 = mesh.add_vertex(Point_3(0, 1, 0));
auto v11 = mesh.add_vertex(Point_3(1, 1, 0));
auto v21 = mesh.add_vertex(Point_3(2, 1, 0));
mesh.add_face(v00, v10, v11);
mesh.add_face(v00, v11, v01);
mesh.add_face(v10, v20, v21);
mesh.add_face(v10, v21, v11);
// 执行BFS
bfs_traverse(mesh, v00);
return 0;
}模式5：多属性管理
场景：同时管理多种属性，如顶点坐标、颜色、纹理坐标、法向量等
#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
#include <array>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef Kernel::Vector_3 Vector_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Vertex_index Vertex_index;
struct VertexAttributes {
// 颜色
std::array<unsigned char, 3> color;
// 纹理坐标
float u, v;
// 法向量
Vector_3 normal;
// 材质ID
int material_id;
// 选中状态
bool is_selected;
VertexAttributes()
: color({255, 255, 255}), u(0), v(0),
normal(Vector_3(0, 0, 1)), material_id(0), is_selected(false) {}
};
int main() {
Mesh mesh;
// 创建顶点
auto v0 = mesh.add_vertex(Point_3(0, 0, 0));
auto v1 = mesh.add_vertex(Point_3(1, 0, 0));
auto v2 = mesh.add_vertex(Point_3(0, 1, 0));
// 方法1：使用结构体存储所有属性（适合属性较少的情况）
auto attr_map = mesh.add_property_map<Vertex_index, VertexAttributes>("v:attributes").first;
// 设置属性
attr_map[v0].color = {255, 0, 0};
attr_map[v0].u = 0.0f;
attr_map[v0].v = 0.0f;
attr_map[v0].material_id = 1;
attr_map[v0].is_selected = true;
// 方法2：分开存储（适合需要频繁访问单个属性的情况）
auto color_map = mesh.add_property_map<Vertex_index, std::array<unsigned char, 3>>("v:color").first;
auto texcoord_map = mesh.add_property_map<Vertex_index, std::pair<float, float>>("v:texcoord").first;
auto normal_map = mesh.add_property_map<Vertex_index, Vector_3>("v:normal").first;
auto material_map = mesh.add_property_map<Vertex_index, int>("v:material").first;
auto selected_map = mesh.add_property_map<Vertex_index, bool>("v:selected").first;
// 批量设置属性
for (Vertex_index v : mesh.vertices()) {
color_map[v] = {128, 128, 128};
texcoord_map[v] = {0.5f, 0.5f};
normal_map[v] = Vector_3(0, 0, 1);
material_map[v] = 0;
selected_map[v] = false;
}
// 输出所有属性
std::cout << "Vertex attributes:" << std::endl;
for (Vertex_index v : mesh.vertices()) {
std::cout << " Vertex " << v << ":" << std::endl;
std::cout << " Color: RGB("
<< (int)color_map[v][0] << ", "
<< (int)color_map[v][1] << ", "
<< (int)color_map[v][2] << ")" << std::endl;
std::cout << " TexCoord: (" << texcoord_map[v].first << ", "
<< texcoord_map[v].second << ")" << std::endl;
std::cout << " Material: " << material_map[v] << std::endl;
std::cout << " Selected: " << (selected_map[v] ? "yes" : "no") << std::endl;
}
// 列出所有属性名
std::cout << "\nAll vertex properties:" << std::endl;
for (const auto& name : mesh.properties<Vertex_index>()) {
std::cout << " - " << name << std::endl;
}
return 0;
}3. Before/After对比：从传统方法到Property Map
场景：计算顶点曲率并可视化
Before：传统方法（繁琐且不灵活）
#include <vector>
#include <map>
#include <iostream>
// 传统方法：手动管理多个数组和映射
struct Vertex {
double x, y, z;
int id;
};
class MeshWithAttributes {
std::vector<Vertex> vertices;
// 多个分离的属性存储
std::vector<double> curvatures; // 需要与vertices索引同步
std::map<int, bool> selected; // 使用ID映射
std::map<int, int> material_ids;
public:
void add_vertex(double x, double y, double z) {
Vertex v{x, y, z, (int)vertices.size()};
vertices.push_back(v);
curvatures.push_back(0.0); // 需要手动同步
}
void set_curvature(int vertex_id, double curvature) {
if (vertex_id >= 0 && vertex_id < curvatures.size()) {
curvatures[vertex_id] = curvature;
}
}
double get_curvature(int vertex_id) {
if (vertex_id >= 0 && vertex_id < curvatures.size()) {
return curvatures[vertex_id];
}
return 0.0;
}
void select_vertex(int vertex_id) {
selected[vertex_id] = true;
}
bool is_selected(int vertex_id) {
return selected.count(vertex_id) > 0 && selected[vertex_id];
}
// 问题：
// 1. 需要手动同步多个容器
// 2. 不同类型的属性使用不同的访问方式
// 3. 删除顶点时需要更新所有容器
// 4. 代码重复且容易出错
// 5. 无法运行时添加新属性
};
int main() {
MeshWithAttributes mesh;
mesh.add_vertex(0, 0, 0);
mesh.add_vertex(1, 0, 0);
mesh.add_vertex(0, 1, 0);
// 计算曲率（模拟）
mesh.set_curvature(0, 0.5);
mesh.set_curvature(1, 0.3);
mesh.set_curvature(2, 0.8);
// 选择顶点
mesh.select_vertex(0);
mesh.select_vertex(2);
// 输出
for (int i = 0; i < 3; ++i) {
std::cout << "Vertex " << i << ":"
<< " curvature=" << mesh.get_curvature(i)
<< " selected=" << (mesh.is_selected(i) ? "yes" : "no")
<< std::endl;
}
return 0;
}After：使用Property Map（简洁且灵活）
#include <CGAL/Surface_mesh.h>
#include <CGAL/Simple_cartesian.h>
#include <iostream>
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_3 Point_3;
typedef CGAL::Surface_mesh<Point_3> Mesh;
typedef Mesh::Vertex_index Vertex_index;
int main() {
Mesh mesh;
// 创建顶点
Vertex_index v0 = mesh.add_vertex(Point_3(0, 0, 0));
Vertex_index v1 = mesh.add_vertex(Point_3(1, 0, 0));
Vertex_index v2 = mesh.add_vertex(Point_3(0, 1, 0));
// 动态添加属性（一行代码）
auto curvature_map = mesh.add_property_map<Vertex_index, double>("v:curvature", 0.0).first;
auto selected_map = mesh.add_property_map<Vertex_index, bool>("v:selected", false).first;
auto color_map = mesh.add_property_map<Vertex_index, std::array<unsigned char, 3>>("v:color").first;
// 计算并设置曲率（模拟）
curvature_map[v0] = 0.5;
curvature_map[v1] = 0.3;
curvature_map[v2] = 0.8;
// 根据曲率设置颜色（热力图）
for (Vertex_index v : mesh.vertices()) {
double c = curvature_map[v];
unsigned char r = static_cast<unsigned char>(255 * c);
unsigned char b = static_cast<unsigned char>(255 * (1 - c));
color_map[v] = {r, 0, b};
}
// 选择高曲率顶点
for (Vertex_index v : mesh.vertices()) {
selected_map[v] = (curvature_map[v] > 0.4);
}
// 统一输出
std::cout << "Vertex attributes:" << std::endl;
for (Vertex_index v : mesh.vertices()) {
auto color = color_map[v];
std::cout << " Vertex " << v << ":"
<< " curvature=" << curvature_map[v]
<< " selected=" << (selected_map[v] ? "yes" : "no")
<< " color=RGB("
<< (int)color[0] << "," << (int)color[1] << "," << (int)color[2] << ")"
<< std::endl;
}
// 优势：
// 1. 动态添加属性，无需预先定义
// 2. 统一的访问接口（operator[]）
// 3. 自动内存管理和生命周期同步
// 4. 类型安全
// 5. 可以与CGAL算法无缝集成
return 0;
}4. 性能对比实验
测试不同Property Map实现的性能
#include <CGAL/property_map.h>
#include <CGAL/Surface_mesh.h>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>
// 计时工具
template<typename Func>
double benchmark(Func&& func, int iterations = 1000000) {
auto start = std::chrono::high_resolution_clock::now();
func(iterations);
auto end = std::chrono::high_resolution_clock::now();
return std::chrono::duration<double, std::milli>(end - start).count();
}
int main() {
const int N = 10000; // 顶点数
const int ITERATIONS = 1000000;
std::cout << "Property Map Performance Comparison" << std::endl;
std::cout << "===================================" << std::endl;
std::cout << "Vertices: " << N << std::endl;
std::cout << "Iterations: " << ITERATIONS << std::endl;
std::cout << std::endl;
// 准备数据
std::vector<double> data(N);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dis(0, N-1);
for (int i = 0; i < N; ++i) {
data[i] = i * 1.0;
}
// 1. 原始指针数组（最快，但不灵活）
double ptr_time = benchmark([&](int iters) {
double* ptr = data.data();
volatile double sum = 0;
for (int i = 0; i < iters; ++i) {
int idx = dis(gen);
sum += ptr[idx]; // 直接访问
}
}, ITERATIONS);
// 2. std::vector（常用）
double vector_time = benchmark([&](int iters) {
volatile double sum = 0;
for (int i = 0; i < iters; ++i) {
int idx = dis(gen);
sum += data[idx];
}
}, ITERATIONS);
// 3. std::map（最慢，但有序）
std::map<int, double> map_data;
for (int i = 0; i < N; ++i) map_data[i] = i * 1.0;
double map_time = benchmark([&](int iters) {
volatile double sum = 0;
for (int i = 0; i < iters; ++i) {
int idx = dis(gen);
sum += map_data[idx];
}
}, ITERATIONS);
// 4. std::unordered_map（较快，无序）
std::unordered_map<int, double> umap_data;
for (int i = 0; i < N; ++i) umap_data[i] = i * 1.0;
double umap_time = benchmark([&](int iters) {
volatile double sum = 0;
for (int i = 0; i < iters; ++i) {
int idx = dis(gen);
sum += umap_data[idx];
}
}, ITERATIONS);
// 5. CGAL Pointer_property_map（零开销）
auto ptr_map = CGAL::make_property_map(data);
double pmap_time = benchmark([&](int iters) {
volatile double sum = 0;
for (int i = 0; i < iters; ++i) {
int idx = dis(gen);
sum += get(ptr_map, idx);
}
}, ITERATIONS);
// 6. Surface_mesh Property_map（高效动态）
typedef CGAL::Simple_cartesian<double> Kernel;
typedef CGAL::Surface_mesh<Kernel::Point_3> Mesh;
Mesh mesh;
for (int i = 0; i < N; ++i) {
mesh.add_vertex(Kernel::Point_3(i, 0, 0));
}
auto sm_map = mesh.add_property_map<Mesh::Vertex_index, double>("v:value", 0.0).first;
for (int i = 0; i < N; ++i) {
sm_map[Mesh::Vertex_index(i)] = i * 1.0;
}
double sm_time = benchmark([&](int iters) {
volatile double sum = 0;
for (int i = 0; i < iters; ++i) {
int idx = dis(gen);
sum += sm_map[Mesh::Vertex_index(idx)];
}
}, ITERATIONS);
// 输出结果表格
std::cout << "Results (milliseconds):" << std::endl;
std::cout << "-----------------------" << std::endl;
std::cout << "Raw pointer array: " << ptr_time << " ms" << std::endl;
std::cout << "std::vector: " << vector_time << " ms" << std::endl;
std::cout << "std::map: " << map_time << " ms" << std::endl;
std::cout << "std::unordered_map: " << umap_time << " ms" << std::endl;
std::cout << "CGAL Pointer_property: " << pmap_time << " ms" << std::endl;
std::cout << "Surface_mesh Property: " << sm_time << " ms" << std::endl;
std::cout << std::endl;
// 计算相对性能
std::cout << "Relative Performance (vs raw pointer):" << std::endl;
std::cout << "---------------------------------------" << std::endl;
std::cout << "std::vector: " << (vector_time / ptr_time) << "x" << std::endl;
std::cout << "std::map: " << (map_time / ptr_time) << "x" << std::endl;
std::cout << "std::unordered_map: " << (umap_time / ptr_time) << "x" << std::endl;
std::cout << "CGAL Pointer_property: " << (pmap_time / ptr_time) << "x" << std::endl;
std::cout << "Surface_mesh Property: " << (sm_time / ptr_time) << "x" << std::endl;
return 0;
}性能对比总结
| Property Map类型 | 访问速度 | 内存开销 | 灵活性 | 适用场景 |
|---|---|---|---|---|
| 原始指针数组 | O(1)，最快 | 最低 | 最低 | 性能关键，固定数据 |
| std::vector | O(1)，快 | 低 | 低 | 密集数据，整数索引 |
| std::map | O(log n)，慢 | 高（节点） | 中 | 需要有序遍历 |
| std::unordered_map | O(1)平均，较快 | 中 | 中 | 稀疏数据 |
| CGAL Pointer_property_map | O(1)，快 | 低 | 中 | 与CGAL算法集成 |
| Surface_mesh Property_map | O(1)，快 | 低 | 高 | 动态属性管理 |
建议：
- 对于固定属性，使用
std::vector或CGAL::Pointer_property_map - 对于动态属性，使用
Surface_mesh::Property_map - 避免在性能关键路径使用
std::map
5. 理论基础（原第1节，精简版）
5.1 属性映射的设计模式理论
属性映射（Property Map）是CGAL中实现**访问者模式（Visitor Pattern）和外部属性（External Properties）**的核心机制。它允许将任意数据附加到几何对象，而无需修改对象本身的定义。
核心思想：
- 关注点分离：几何对象只包含几何信息，属性通过外部映射管理
- 延迟绑定：属性可以在运行时动态添加和删除
- 类型安全：利用C++模板确保编译时类型检查
- 零开销抽象：Pointer_property_map等实现无额外存储开销
5.2 Property Map概念层次
| 概念 | 要求 | 用途 |
|---|---|---|
ReadablePropertyMap | 支持 get(pm, key) | 只读访问 |
WritablePropertyMap | 支持 put(pm, key, val) | 只写访问 |
ReadWritePropertyMap | 同时支持get和put | 读写访问 |
LvaluePropertyMap | 支持 pm[key] 返回引用 | 直接引用访问 |
DynamicPropertyMap | 支持运行时添加/删除 | 动态属性管理 |
6. 架构分析（原第2节，精简版）
6.1 属性映射类层次结构
Property Map体系
├── 基础概念
│ ├── readable_property_map_tag
│ ├── writable_property_map_tag
│ ├── read_write_property_map_tag
│ └── lvalue_property_map_tag
│
├── 内置Property Map
│ ├── Pointer_property_map<T> // 指针数组包装
│ ├── Identity_property_map<T> // 恒等映射
│ ├── Dereference_property_map<T> // 解引用映射
│ ├── First_of_pair_property_map<Pair> // pair.first访问
│ ├── Second_of_pair_property_map<Pair>// pair.second访问
│ ├── Constant_property_map<Key, Value>// 常量值
│ ├── Boolean_property_map<Set> // 集合成员测试
│ └── Cartesian_converter_property_map // 坐标转换
│
├── 组合Property Map
│ ├── Compose_property_map<KeyMap, ValueMap> // 组合映射
│ └── OR_property_map<PM1, PM2> // 逻辑或
│
└── Surface_mesh专用
├── Property_map_base<I, T, CRTP> // 基类
├── Property_array<T> // 属性数组
└── Property_container<Ref_class, Key> // 属性容器
6.2 Surface_mesh属性系统架构
Surface_mesh的属性系统采用**类型擦除（Type Erasure）**技术，支持运行时动态添加属性：
Surface_mesh
├── vertices_ : Property_container<Surface_mesh, Vertex_index>
├── halfedges_ : Property_container<Surface_mesh, Halfedge_index>
├── edges_ : Property_container<Surface_mesh, Edge_index>
└── faces_ : Property_container<Surface_mesh, Face_index>
Property_container
└── parrays_ : vector<Base_property_array*>
├── Property_array<T1>
├── Property_array<T2>
└── Property_array<T3>
7. 实现细节（原第3节）
3.1 基础Property Map实现
// 文件: CGAL/property_map.h
namespace CGAL {
// 指针属性映射 - 零开销实现
template<class T>
struct Pointer_property_map {
typedef boost::iterator_property_map<T*,
boost::typed_identity_property_map<std::size_t>,
T, T&> type; // 可变版本
typedef boost::iterator_property_map<const T*,
boost::typed_identity_property_map<std::size_t>,
T, const T&> const_type; // 常量版本
};
// 创建指针属性映射的工厂函数
template<class T>
inline typename Pointer_property_map<T>::type
make_property_map(T* pointer) {
return typename Pointer_property_map<T>::type(pointer);
}
template<class T>
inline typename Pointer_property_map<T>::type
make_property_map(std::vector<T>& v) {
if (v.empty()) {
return make_property_map(static_cast<T*>(nullptr));
}
return make_property_map(&v[0]);
}
// 恒等属性映射
template<typename T>
struct Identity_property_map {
typedef T key_type;
typedef T value_type;
typedef T& reference;
typedef boost::lvalue_property_map_tag category;
T& operator[](T& k) const { return k; }
const T& operator[](const T& k) const { return k; }
T operator[](T&& k) const { return std::forward<T>(k); }
friend T& get(const Identity_property_map&, T& k) { return k; }
friend const T& get(const Identity_property_map&, const T& k) { return k; }
friend T get(const Identity_property_map&, T&& k) {
return std::forward<T>(k);
}
friend void put(const Identity_property_map&, T& k, const T& v) {
k = v;
}
};
// 解引用属性映射
template<typename T, typename Iter = T*>
struct Dereference_property_map
: public boost::put_get_helper<
typename std::iterator_traits<Iter>::reference,
Dereference_property_map<T, Iter>> {
typedef Iter key_type;
typedef std::remove_const_t<T> value_type;
typedef typename std::iterator_traits<Iter>::reference reference;
typedef boost::lvalue_property_map_tag category;
template<class Iter_>
reference operator[](const Iter_& it) const { return *it; }
};
// pair属性映射
template<typename Pair>
struct First_of_pair_property_map {
typedef Pair key_type;
typedef typename Pair::first_type value_type;
typedef const value_type& reference;
typedef boost::lvalue_property_map_tag category;
const value_type& operator[](const key_type& pair) const {
return pair.first;
}
friend reference get(const First_of_pair_property_map&, const key_type& k) {
return k.first;
}
friend void put(const First_of_pair_property_map&, key_type& k,
const value_type& v) {
k.first = v;
}
};
template<typename Pair>
struct Second_of_pair_property_map {
typedef Pair key_type;
typedef typename Pair::second_type value_type;
typedef const value_type& reference;
typedef boost::lvalue_property_map_tag category;
const value_type& operator[](const key_type& pair) const {
return pair.second;
}
friend reference get(const Second_of_pair_property_map&, const key_type& k) {
return k.second;
}
friend void put(const Second_of_pair_property_map&, key_type& k,
const value_type& v) {
k.second = v;
}
};
// tuple属性映射
template<int N, typename Tuple>
struct Nth_of_tuple_property_map {
typedef Tuple key_type;
typedef typename std::tuple_element<N, Tuple>::type value_type;
typedef const value_type& reference;
typedef boost::lvalue_property_map_tag category;
const value_type& operator[](const key_type& tuple) const {
return std::get<N>(tuple);
}
friend reference get(const Nth_of_tuple_property_map&, const key_type& k) {
return std::get<N>(k);
}
friend void put(const Nth_of_tuple_property_map&, key_type& k,
const value_type& v) {
std::get<N>(k) = v;
}
};
// 常量属性映射
template<class KeyType, class ValueType>
struct Constant_property_map {
ValueType default_value;
typedef KeyType key_type;
typedef ValueType value_type;
typedef const value_type& reference;
typedef boost::read_write_property_map_tag category;
Constant_property_map() : default_value{} {}
explicit Constant_property_map(const value_type& v) : default_value(v) {}
friend reference get(const Constant_property_map& pm, const key_type&) {
return pm.default_value;
}
friend void put(const Constant_property_map&, const key_type&,
const value_type&) {
// 无操作
}
};
// 布尔集合属性映射
template<class Set>
struct Boolean_property_map {
typedef typename Set::value_type key_type;
typedef bool value_type;
typedef bool reference;
typedef boost::read_write_property_map_tag category;
Set* set_ptr;
explicit Boolean_property_map(Set& s) : set_ptr(&s) {}
Boolean_property_map() : set_ptr(nullptr) {}
friend bool get(const Boolean_property_map<Set>& pm, const key_type& k) {
CGAL_assertion(pm.set_ptr \!= nullptr);
return pm.set_ptr->count(k) \!= 0;
}
friend void put(Boolean_property_map<Set> pm, const key_type& k, bool v) {
CGAL_assertion(pm.set_ptr \!= nullptr);
if (v) pm.set_ptr->insert(k);
else pm.set_ptr-<erase(k);
}
};
// 组合属性映射
template<class KeyMap, class ValueMap>
struct Compose_property_map {
typedef typename boost::property_traits<KeyMap>::key_type key_type;
typedef typename boost::property_traits<ValueMap>::value_type value_type;
typedef typename boost::property_traits<ValueMap>::reference reference;
typedef typename boost::property_traits<ValueMap>::category category;
KeyMap key_map;
ValueMap value_map;
Compose_property_map(KeyMap km = KeyMap(), ValueMap vm = ValueMap())
: key_map(km), value_map(vm) {}
friend reference get(Compose_property_map map, const key_type& k) {
return get(map.value_map, get(map.key_map, k));
}
friend void put(const Compose_property_map& map, const key_type& k,
const value_type& v) {
put(map.value_map, get(map.key_map, k), v);
}
};
// 随机访问属性映射
template<typename Container>
class Random_access_property_map {
Container& m_container;
public:
typedef std::size_t key_type;
typedef typename Container::value_type value_type;
typedef typename Container::reference reference;
typedef boost::lvalue_property_map_tag category;
explicit Random_access_property_map(Container& c) : m_container(c) {}
friend reference get(Random_access_property_map map, key_type index) {
return map.m_container[index];
}
template<class Key>
friend void put(Random_access_property_map map, Key index,
const value_type& value,
std::enable_if_t<\!std::is_const<Container>::value>* = 0) {
map.m_container[index] = value;
}
decltype(auto) operator[](key_type index) const {
return m_container[index];
}
};
// 笛卡尔坐标转换属性映射
template<class GeomObject, class Vpm>
struct Cartesian_converter_property_map {
typedef typename boost::property_traits<Vpm>::key_type key_type;
typedef GeomObject value_type;
typedef value_type reference;
typedef boost::read_write_property_map_tag category;
Vpm vpm;
typedef typename Kernel_traits<GeomObject>::type K2;
typedef typename Kernel_traits<
typename boost::property_traits<Vpm>::value_type>::type K1;
explicit Cartesian_converter_property_map(Vpm v) : vpm(v) {}
friend value_type get(const Cartesian_converter_property_map& pm,
const key_type& k) {
return CGAL::Cartesian_converter<K1, K2>()(get(pm.vpm, k));
}
friend void put(Cartesian_converter_property_map& pm, const key_type& k,
const value_type& v) {
put(pm.vpm, k, CGAL::Cartesian_converter<K2, K1>()(v));
}
};
} // namespace CGAL3.2 Surface_mesh属性系统实现
// 文件: CGAL/Surface_mesh/Properties.h
namespace CGAL {
namespace Properties {
// 属性数组基类
class Base_property_array {
public:
explicit Base_property_array(const std::string& name) : name_(name) {}
virtual ~Base_property_array() {}
virtual void reserve(size_t n) = 0;
virtual void resize(size_t n) = 0;
virtual void shrink_to_fit() = 0;
virtual void push_back() = 0;
virtual void reset(size_t idx) = 0;
virtual bool transfer(const Base_property_array& other) = 0;
virtual bool transfer(const Base_property_array& other,
std::size_t from, std::size_t to) = 0;
virtual void swap(size_t i0, size_t i1) = 0;
virtual Base_property_array* clone() const = 0;
virtual Base_property_array* empty_clone() const = 0;
virtual const std::type_info& type() const = 0;
const std::string& name() const { return name_; }
bool is_same(const Base_property_array& other) {
return (name() == other.name() && type() == other.type());
}
protected:
std::string name_;
};
// 类型化属性数组
template<class T>
class Property_array : public Base_property_array {
public:
typedef T value_type;
typedef std::vector<value_type> vector_type;
typedef typename vector_type::reference reference;
typedef typename vector_type::const_reference const_reference;
typedef typename vector_type::iterator iterator;
typedef typename vector_type::const_iterator const_iterator;
Property_array(const std::string& name, T t = T())
: Base_property_array(name), value_(t) {}
// 虚拟接口实现
void reserve(size_t n) override { data_.reserve(n); }
void resize(size_t n) override { data_.resize(n, value_); }
void shrink_to_fit() override { vector_type(data_).swap(data_); }
void push_back() override { data_.push_back(value_); }
void reset(size_t idx) override { data_[idx] = value_; }
bool transfer(const Base_property_array& other) override {
const Property_array<T>* pa = dynamic_cast<const Property_array*>(&other);
if (pa \!= nullptr) {
std::copy(pa->data_.begin(), pa->data_.end(),
data_.end() - pa->data_.size());
return true;
}
return false;
}
bool transfer(const Base_property_array& other, std::size_t from,
std::size_t to) override {
const Property_array<T>* pa = dynamic_cast<const Property_array*>(&other);
if (pa \!= nullptr) {
data_[to] = (*pa)[from];
return true;
}
return false;
}
void swap(size_t i0, size_t i1) override {
using std::swap;
swap(data_[i0], data_[i1]);
}
Base_property_array* clone() const override {
Property_array<T>* p = new Property_array<T>(this->name_, this->value_);
p->data_ = data_;
return p;
}
Base_property_array* empty_clone() const override {
return new Property_array<T>(this->name_, this->value_);
}
const std::type_info& type() const override { return typeid(T); }
// 直接访问接口
const T* data() const { return data_.data(); }
reference operator[](std::size_t idx) { return data_[idx]; }
const_reference operator[](std::size_t idx) const { return data_[idx]; }
iterator begin() { return data_.begin(); }
iterator end() { return data_.end(); }
const_iterator begin() const { return data_.begin(); }
const_iterator end() const { return data_.end(); }
private:
vector_type data_;
value_type value_;
};
// 属性容器
template<typename Ref_class, typename Key>
class Property_container {
public:
Property_container() = default;
~Property_container() { clear(); }
Property_container(const Property_container& rhs) { operator=(rhs); }
Property_container(Property_container&& c) noexcept { c.swap(*this); }
Property_container& operator=(const Property_container& rhs) {
if (this \!= &rhs) {
clear();
parrays_.resize(rhs.n_properties());
size_ = rhs.size_;
capacity_ = rhs.capacity_;
for (std::size_t i = 0; i < parrays_.size(); ++i)
parrays_[i] = rhs.parrays_[i]->clone();
}
return *this;
}
Property_container& operator=(Property_container&& c) noexcept {
Property_container tmp(std::move(c));
tmp.swap(*this);
return *this;
}
// 添加属性
template<class T>
std::pair<typename Get_pmap_type<T>::type, bool>
add(const std::string& name, const T t = T()) {
typedef typename Ref_class::template Get_property_map<Key, T>::type Pmap;
// 检查是否已存在
for (std::size_t i = 0; i < parrays_.size(); ++i) {
std::optional<Pmap> out = get<T>(name, i);
if (out.has_value())
return std::make_pair(*out, false);
}
// 创建新属性数组
Property_array<T>* p = new Property_array<T>(name, t);
p->reserve(capacity_);
p->resize(size_);
parrays_.push_back(p);
return std::make_pair(Pmap(p), true);
}
// 获取属性
template<class T>
std::optional<typename Get_pmap_type<T>::type>
get(const std::string& name) const {
typedef typename Ref_class::template Get_property_map<Key, T>::type Pmap;
for (std::size_t i = 0; i < parrays_.size(); ++i) {
std::optional<Pmap> out = get<T>(name, i);
if (out.has_value())
return out;
}
return std::nullopt;
}
// 获取或添加属性
template<class T>
typename Get_pmap_type<T>::type
get_or_add(const std::string& name, const T t = T()) {
std::optional<typename Get_pmap_type<T>::type> out = get<T>(name);
if (out.has_value())
return out.value();
else
return add<T>(name, t).first;
}
// 删除属性
template<class T>
bool remove(typename Get_pmap_type<T>::type& h) {
auto it = std::find(parrays_.begin(), parrays_.end(), h.parray_);
if (it \!= parrays_.end()) {
delete *it;
parrays_.erase(it);
h.reset();
return true;
}
return false;
}
// 删除所有属性
void clear() {
for (std::size_t i = 0; i < parrays_.size(); ++i)
delete parrays_[i];
parrays_.clear();
size_ = 0;
}
// 容量管理
void reserve(size_t n) {
for (std::size_t i = 0; i < parrays_.size(); ++i)
parrays_[i]->reserve(n);
capacity_ = (std::max)(n, capacity_);
}
void resize(size_t n) {
for (std::size_t i = 0; i < parrays_.size(); ++i)
parrays_[i]->resize(n);
size_ = n;
}
void push_back() {
for (std::size_t i = 0; i < parrays_.size(); ++i)
parrays_[i]->push_back();
++size_;
capacity_ = (std::max)(size_, capacity_);
}
// 查询
size_t size() const { return size_; }
size_t capacity() const { return capacity_; }
size_t n_properties() const { return parrays_.size(); }
std::vector<std::string> properties() const {
std::vector<std::string> names;
for (std::size_t i = 0; i < parrays_.size(); ++i)
names.push_back(parrays_[i]->name());
return names;
}
private:
std::vector<Base_property_array*> parrays_;
size_t size_ = 0;
size_t capacity_ = 0;
};
} // namespace Properties
// Property_map基类
template<class I, class T, class CRTP_derived_class>
class Property_map_base
: public boost::put_get_helper<
typename Properties::Property_array<T>::reference,
CRTP_derived_class> {
public:
typedef I key_type;
typedef T value_type;
typedef boost::lvalue_property_map_tag category;
typedef typename Properties::Property_array<T>::reference reference;
typedef typename Properties::Property_array<T>::const_reference const_reference;
typedef typename Properties::Property_array<T>::iterator iterator;
typedef typename Properties::Property_array<T>::const_iterator const_iterator;
Property_map_base(Properties::Property_array<T>* p = nullptr)
: parray_(p) {}
Property_map_base(Property_map_base&& pm) noexcept
: parray_(std::exchange(pm.parray_, nullptr)) {}
Property_map_base(const Property_map_base& pm) : parray_(pm.parray_) {}
Property_map_base& operator=(const Property_map_base& pm) {
parray_ = pm.parray_;
return *this;
}
void reset() { parray_ = nullptr; }
explicit operator bool() const { return parray_ \!= nullptr; }
bool operator==(const Property_map_base& pm) const {
return parray_ == pm.parray_;
}
bool operator\!=(const Property_map_base& pm) const {
return parray_ \!= pm.parray_;
}
reference operator[](const I& i) const {
return (*parray_)[static_cast<std::size_t>(i)];
}
const T* data() const { return parray_>data(); }
iterator begin() { return parray_>begin(); }
iterator end() { return parray_>end(); }
const_iterator begin() const { return parray_>begin(); }
const_iterator end() const { return parray_>end(); }
friend reference get(const Property_map_base& pm, const key_type& k) {
return pm[k];
}
friend void put(Property_map_base& pm, const key_type& k,
const value_type& v) {
pm[k] = v;
}
private:
Properties::Property_array<T>* parray_;
};
} // namespace CGAL8. 使用示例
[保留原有第4节示例内容]
9. 复杂度分析
9.1 时间复杂度
| Property Map类型 | get | put | operator[] | 空间 |
|---|---|---|---|---|
| Pointer_property_map | O(1) | O(1) | O(1) | O(n) |
| Identity_property_map | O(1) | O(1) | O(1) | O(1) |
| Dereference_property_map | O(1) | O(1) | O(1) | O(1) |
| First/Second_of_pair | O(1) | O(1) | O(1) | O(1) |
| Constant_property_map | O(1) | O(1) | N/A | O(1) |
| Boolean_property_map | O(log n) | O(log n) | N/A | O(n) |
| Compose_property_map | O(f + g) | O(f + g) | N/A | O(1) |
| Surface_mesh Property | O(1) | O(1) | O(1) | O(n) |
9.2 空间复杂度与性能对比
[保留原有表格]
10. 关键文件位置
| 文件路径 | 说明 |
|---|---|
| Property_map/include/CGAL/property_map.h | 核心Property Map定义 |
| Surface_mesh/include/CGAL/Surface_mesh/Properties.h | Surface_mesh属性系统 |
11. 最佳实践
11.1 使用建议
- 选择合适的Property Map类型
- 优先使用Surface_mesh的动态属性系统
- 使用工厂函数创建Property Map
- 组合Property Map实现复杂逻辑
11.2 常见陷阱
- 生命周期管理：避免vector被销毁后Property Map失效
- 类型匹配：确保property_map类型匹配
- 空Property Map检查：使用has_value()检查