19.5 属性映射(Property Maps)
相关章节
在本节中你将学到…
- 属性映射的设计哲学和核心概念
- CGAL内置的属性映射类型
- 如何编写自定义属性映射
- 属性映射与BGL(Boost Graph Library)的集成
- 实际应用中的最佳实践
19.5.1 概念解释
什么是属性映射?
属性映射(Property Map)是一种抽象机制,它将键(Key)映射到值(Value),类似于字典或哈希表,但更加灵活和类型安全。在CGAL中,属性映射是连接几何算法与数据结构的关键桥梁。
类比理解: 想象你管理一个大型仓库(数据结构)。传统方式是每个物品(几何对象)都自带所有信息(坐标、颜色、法向量等)。属性映射则像是一个中央数据库,你可以为任何物品关联任意属性,而不需要修改物品本身。
属性映射的核心概念
┌─────────────────────────────────────────────────────────────┐
│ 属性映射概念 │
├─────────────────────────────────────────────────────────────┤
│ │
│ Key(键) Property Map(映射) Value(值) │
│ │ │ │ │
│ │ get(map, key) │ │ │
│ │ ────────────────> │ │ │
│ │ │ │ │
│ │ put(map, key, value) │ │
│ │ ─────────────────────────────────────> │ │
│ │
│ 示例: │
│ - Key: 顶点句柄 (vertex_descriptor) │
│ - Value: 点坐标 (Point_3) │
│ - Map: 顶点位置属性映射 │
│ │
└─────────────────────────────────────────────────────────────┘
属性映射的类别
根据访问方式,属性映射分为几类:
- ReadablePropertyMap:只读访问(
get操作) - WritablePropertyMap:只写访问(
put操作) - ReadWritePropertyMap:读写访问(
get和put) - LvaluePropertyMap:通过引用访问(支持
operator[])
19.5.2 为什么需要属性映射?
问题1:算法与数据结构的解耦
// 紧耦合:算法直接访问数据结构内部
void smooth_mesh(Mesh& mesh) {
for (auto v : mesh.vertices()) {
mesh.point(v) = compute_new_position(v); // 依赖具体接口
}
}问题:如果数据结构不是CGAL的Surface_mesh,而是OpenMesh或自定义结构,算法需要重写!
问题2:动态属性管理
// 某些属性只在特定算法中需要
void compute_normals(Mesh& mesh) {
// 需要为每个面存储法向量
// 但不应该修改Mesh类的定义!
}问题3:算法组合
// 多个算法可能需要不同的属性组合
algorithm1(mesh, vertex_color_map, vertex_normal_map);
algorithm2(mesh, vertex_texture_map, vertex_quality_map);19.5.3 代码示例
基础示例:理解属性映射
#include <iostream>
#include <vector>
#include <map>
#include <string>
// ============================================
// 基础属性映射概念
// ============================================
// 简单的属性映射:使用std::vector
class VertexPositionMap {
std::vector<std::pair<double, double>> positions;
public:
// 定义必要的类型
typedef int key_type; // 顶点索引
typedef std::pair<double, double> value_type;
typedef const std::pair<double, double>& reference;
// 构造函数
explicit VertexPositionMap(size_t n) : positions(n) {}
// get操作(读取)
friend reference get(const VertexPositionMap& map, key_type key) {
return map.positions[key];
}
// put操作(写入)
friend void put(VertexPositionMap& map, key_type key, const value_type& value) {
map.positions[key] = value;
}
// 可选:operator[]支持
reference operator[](key_type key) const {
return positions[key];
}
};
// 使用属性映射的算法
template <typename PositionMap>
void print_positions(const PositionMap& map, int num_vertices) {
for (int i = 0; i < num_vertices; ++i) {
auto pos = get(map, i); // 通过属性映射访问
std::cout << "Vertex " << i << ": ("
<< pos.first << ", " << pos.second << ")" << std::endl;
}
}
template <typename PositionMap>
void translate_mesh(PositionMap& map, int num_vertices, double dx, double dy) {
for (int i = 0; i < num_vertices; ++i) {
auto pos = get(map, i);
put(map, i, std::make_pair(pos.first + dx, pos.second + dy));
}
}
int main() {
// 创建属性映射
VertexPositionMap pos_map(3);
// 设置顶点位置
put(pos_map, 0, std::make_pair(0.0, 0.0));
put(pos_map, 1, std::make_pair(1.0, 0.0));
put(pos_map, 2, std::make_pair(0.5, 1.0));
// 打印
std::cout << "Original positions:" << std::endl;
print_positions(pos_map, 3);
// 平移
translate_mesh(pos_map, 3, 1.0, 2.0);
std::cout << "\nTranslated positions:" << std::endl;
print_positions(pos_map, 3);
return 0;
}中级示例:多种属性映射实现
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <memory>
// ============================================
// 多种属性映射实现方式
// ============================================
// 1. 基于std::vector的属性映射(密集存储)
template <typename T>
class VectorPropertyMap {
std::vector<T> data;
public:
typedef int key_type;
typedef T value_type;
typedef T& reference;
explicit VectorPropertyMap(size_t n = 0, const T& default_val = T())
: data(n, default_val) {}
void resize(size_t n, const T& default_val = T()) {
data.resize(n, default_val);
}
friend const T& get(const VectorPropertyMap& map, key_type key) {
return map.data[key];
}
friend void put(VectorPropertyMap& map, key_type key, const T& value) {
map.data[key] = value;
}
T& operator[](key_type key) { return data[key]; }
const T& operator[](key_type key) const { return data[key]; }
};
// 2. 基于std::map的属性映射(稀疏存储)
template <typename Key, typename T>
class MapPropertyMap {
std::map<Key, T> data;
T default_value;
public:
typedef Key key_type;
typedef T value_type;
typedef const T& reference;
explicit MapPropertyMap(const T& default_val = T())
: default_value(default_val) {}
friend T get(const MapPropertyMap& map, const Key& key) {
auto it = map.data.find(key);
return (it \!= map.data.end()) ? it->second : map.default_value;
}
friend void put(MapPropertyMap& map, const Key& key, const T& value) {
map.data[key] = value;
}
};
// 3. 基于函数计算的属性映射(动态计算)
template <typename Key, typename Func>
class ComputedPropertyMap {
Func func;
public:
typedef Key key_type;
typedef decltype(std::declval<Func>()(std::declval<Key>())) value_type;
typedef value_type reference;
explicit ComputedPropertyMap(Func f) : func(f) {}
friend value_type get(const ComputedPropertyMap& map, const Key& key) {
return map.func(key);
}
// 注意:ComputedPropertyMap通常是只读的
};
// 辅助函数:创建计算属性映射
template <typename Key, typename Func>
ComputedPropertyMap<Key, Func> make_computed_property_map(Func f) {
return ComputedPropertyMap<Key, Func>(f);
}
// 4. 组合属性映射(链式查找)
template <typename PrimaryMap, typename FallbackMap>
class FallbackPropertyMap {
PrimaryMap primary;
FallbackMap fallback;
public:
typedef typename PrimaryMap::key_type key_type;
typedef typename PrimaryMap::value_type value_type;
typedef typename PrimaryMap::reference reference;
FallbackPropertyMap(PrimaryMap p, FallbackMap f)
: primary(std::move(p)), fallback(std::move(f)) {}
friend auto get(const FallbackPropertyMap& map, const key_type& key)
-> decltype(get(map.primary, key)) {
// 这里简化处理,实际应该检查primary是否有值
return get(map.primary, key);
}
};
// ============================================
// 使用属性映射的通用算法
// ============================================
template <typename PositionMap, typename ColorMap>
void render_mesh(const PositionMap& positions, const ColorMap& colors, int num_vertices) {
std::cout << "Rendering mesh:" << std::endl;
for (int i = 0; i < num_vertices; ++i) {
auto pos = get(positions, i);
auto color = get(colors, i);
std::cout << " Vertex " << i << ": pos=(" << pos
<< "), color=" << color << std::endl;
}
}
int main() {
// 使用VectorPropertyMap存储顶点位置
VectorPropertyMap<double> positions(5);
for (int i = 0; i < 5; ++i) {
put(positions, i, i * 1.5);
}
// 使用MapPropertyMap存储稀疏的颜色信息
MapPropertyMap<int, std::string> colors("white");
put(colors, 0, "red");
put(colors, 2, "blue");
// 顶点1,3,4使用默认值"white"
// 使用ComputedPropertyMap动态计算法向量
auto normal_map = make_computed_property_map<int>([](int idx) {
return idx * 0.1; // 简化的法向量计算
});
// 打印结果
std::cout << "Positions:" << std::endl;
for (int i = 0; i < 5; ++i) {
std::cout << " " << get(positions, i) << std::endl;
}
std::cout << "\nColors:" << std::endl;
for (int i = 0; i < 5; ++i) {
std::cout << " " << get(colors, i) << std::endl;
}
std::cout << "\nNormals (computed):" << std::endl;
for (int i = 0; i < 5; ++i) {
std::cout << " " << get(normal_map, i) << std::endl;
}
return 0;
}高级示例:CGAL风格的属性映射
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <boost/property_map/property_map.hpp>
// ============================================
// CGAL风格的属性映射实现
// ============================================
namespace CGAL {
// 属性映射概念标签
struct readable_property_map_tag {};
struct writable_property_map_tag {};
struct read_write_property_map_tag : readable_property_map_tag, writable_property_map_tag {};
struct lvalue_property_map_tag : read_write_property_map_tag {};
// ============================================
// IdentityPropertyMap: 键映射到自身
// ============================================
template <typename T>
struct Identity_property_map {
typedef T key_type;
typedef T value_type;
typedef T& reference;
typedef lvalue_property_map_tag category;
T& operator[](T& k) const { return k; }
const T& operator[](const T& k) const { return 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 void put(const Identity_property_map&, T& k, const T& v) { k = v; }
};
// ============================================
// ConstantPropertyMap: 返回固定值
// ============================================
template <typename KeyType, typename ValueType>
struct Constant_property_map {
ValueType value;
typedef KeyType key_type;
typedef ValueType value_type;
typedef const value_type& reference;
typedef readable_property_map_tag category;
explicit Constant_property_map(const value_type& v) : value(v) {}
friend const value_type& get(const Constant_property_map& map, const key_type&) {
return map.value;
}
};
// ============================================
// ComposePropertyMap: 组合两个属性映射
// ============================================
template <typename KeyMap, typename ValueMap>
struct Compose_property_map {
KeyMap key_map;
ValueMap value_map;
typedef typename KeyMap::key_type key_type;
typedef typename ValueMap::value_type value_type;
typedef typename ValueMap::reference reference;
typedef typename ValueMap::category category;
Compose_property_map(KeyMap km, ValueMap vm)
: key_map(std::move(km)), value_map(std::move(vm)) {}
friend reference get(const Compose_property_map& map, const key_type& k) {
return get(map.value_map, get(map.key_map, k));
}
friend void put(Compose_property_map& map, const key_type& k, const value_type& v) {
put(map.value_map, get(map.key_map, k), v);
}
};
// ============================================
// FirstOfPairPropertyMap: 访问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 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;
}
};
// ============================================
// PointerPropertyMap: 使用原始指针
// ============================================
template <typename T>
struct Pointer_property_map {
typedef std::size_t key_type;
typedef T value_type;
typedef T& reference;
typedef lvalue_property_map_tag category;
T* ptr;
explicit Pointer_property_map(T* p = nullptr) : ptr(p) {}
friend T& get(const Pointer_property_map& map, key_type key) {
return map.ptr[key];
}
friend void put(const Pointer_property_map& map, key_type key, const T& value) {
map.ptr[key] = value;
}
T& operator[](key_type key) const { return ptr[key]; }
};
// 辅助函数
template <typename T>
Pointer_property_map<T> make_property_map(T* ptr) {
return Pointer_property_map<T>(ptr);
}
template <typename T>
Pointer_property_map<T> make_property_map(std::vector<T>& vec) {
return Pointer_property_map<T>(vec.empty() ? nullptr : &vec[0]);
}
// ============================================
// BooleanPropertyMap: 基于std::set的布尔映射
// ============================================
template <typename Set>
struct Boolean_property_map {
typedef typename Set::value_type key_type;
typedef bool value_type;
typedef bool reference;
typedef 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& map, const key_type& k) {
return map.set_ptr->find(k) \!= map.set_ptr->end();
}
friend void put(Boolean_property_map& map, const key_type& k, bool v) {
if (v) map.set_ptr->insert(k);
else map.set_ptr->erase(k);
}
};
} // namespace CGAL
// ============================================
// 使用示例
// ============================================
using namespace CGAL;
int main() {
// 1. IdentityPropertyMap
std::cout << "=== Identity Property Map ===" << std::endl;
Identity_property_map<int> id_map;
int x = 5;
std::cout << "Original: " << x << std::endl;
put(id_map, x, 10);
std::cout << "After put: " << x << std::endl;
// 2. ConstantPropertyMap
std::cout << "\n=== Constant Property Map ===" << std::endl;
Constant_property_map<int, std::string> const_map("default");
std::cout << "Value for key 0: " << get(const_map, 0) << std::endl;
std::cout << "Value for key 42: " << get(const_map, 42) << std::endl;
// 3. PointerPropertyMap
std::cout << "\n=== Pointer Property Map ===" << std::endl;
std::vector<double> data = {1.0, 2.0, 3.0, 4.0, 5.0};
auto ptr_map = make_property_map(data);
std::cout << "Value at index 2: " << get(ptr_map, 2) << std::endl;
put(ptr_map, 2, 10.0);
std::cout << "After put: " << data[2] << std::endl;
// 4. First_of_pair_property_map
std::cout << "\n=== First of Pair Property Map ===" << std::endl;
std::vector<std::pair<int, std::string>> pairs = {
{1, "one"}, {2, "two"}, {3, "three"}
};
First_of_pair_property_map<std::pair<int, std::string>> first_map;
std::cout << "First of pair[1]: " << get(first_map, pairs[1]) << std::endl;
// 5. BooleanPropertyMap
std::cout << "\n=== Boolean Property Map ===" << std::endl;
std::set<int> selected_vertices;
Boolean_property_map<std::set<int>> bool_map(selected_vertices);
put(bool_map, 1, true);
put(bool_map, 3, true);
put(bool_map, 5, true);
std::cout << "Is 1 selected? " << (get(bool_map, 1) ? "yes" : "no") << std::endl;
std::cout << "Is 2 selected? " << (get(bool_map, 2) ? "yes" : "no") << std::endl;
return 0;
}19.5.4 CGAL中的应用
CGAL Property_map模块
CGAL在Property_map/include/CGAL/property_map.h中提供了丰富的属性映射实现:
// 来自CGAL源代码的简化展示
namespace CGAL {
// 解引用属性映射(通过迭代器访问)
template<class InputIterator>
struct Input_iterator_property_map {
typedef InputIterator key_type;
typedef typename std::iterator_traits<InputIterator>::value_type value_type;
typedef typename std::iterator_traits<InputIterator>::reference reference;
typedef boost::readable_property_map_tag category;
friend reference get(Input_iterator_property_map, const InputIterator& it) {
return *it;
}
};
// 组合属性映射
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;
// ...
friend reference get(Compose_property_map map, const key_type& k) {
return get(map.value_map, get(map.key_map, k));
}
};
// 笛卡尔坐标转换属性映射
template<class GeomObject, class Vpm>
struct Cartesian_converter_property_map {
typedef typename boost::property_traits<Vpm>::key_type key_type;
typedef GeomObject value_type;
// ...
friend value_type get(const Cartesian_converter_property_map& pm, const key_type& k) {
return CGAL::Cartesian_converter<K1, K2>()(get(pm.vpm, k));
}
};
} // namespace CGAL与BGL集成
#include <CGAL/Surface_mesh.h>
#include <CGAL/boost/graph/properties.h>
#include <boost/graph/properties.hpp>
using Mesh = CGAL::Surface_mesh<Point_3>;
void example(Mesh& mesh) {
// 获取顶点位置属性映射
auto vertex_point_map = get(CGAL::vertex_point, mesh);
// 使用属性映射访问顶点坐标
for (auto v : mesh.vertices()) {
Point_3 p = get(vertex_point_map, v);
// ...
}
// 创建动态属性(法向量)
auto vertex_normal_map = mesh.add_property_map<Mesh::Vertex_index, Vector_3>("v:normal").first;
// 计算法向量并存储
for (auto v : mesh.vertices()) {
Vector_3 n = compute_normal(v, mesh);
put(vertex_normal_map, v, n);
}
}19.5.5 常见陷阱
陷阱1:属性映射生命周期
// 危险:属性映射引用已销毁的数据
auto create_map() {
std::vector<double> data = {1.0, 2.0, 3.0};
return make_property_map(data); // data在函数结束时销毁!
}
// 解决方案:确保数据生命周期长于属性映射
class MeshWithProperties {
std::vector<double> positions;
Pointer_property_map<double> position_map;
public:
MeshWithProperties() : position_map(make_property_map(positions)) {}
};陷阱2:键类型不匹配
// 问题:使用int索引访问size_t键的属性映射
std::vector<Point_3> points;
auto map = make_property_map(points);
int idx = 0;
auto p = get(map, idx); // 可能编译错误或意外行为
// 解决方案:使用正确的键类型
std::size_t idx = 0;
auto p = get(map, idx);陷阱3:忽略属性映射类别
// 错误:对只读属性映射使用put
template <typename PropertyMap>
void bad_function(PropertyMap& map) {
put(map, key, value); // 编译错误如果PropertyMap是readable的
}
// 正确:使用概念检查
template <typename PropertyMap>
void good_function(PropertyMap& map) {
static_assert(std::is_convertible<
typename boost::property_traits<PropertyMap>::category,
boost::writable_property_map_tag
>::value, "PropertyMap must be writable");
put(map, key, value);
}19.5.6 最佳实践
实践1:使用Boost.PropertyMap概念
#include <boost/property_map/property_map.hpp>
// 确保自定义属性映射符合Boost概念
template <typename Key, typename Value>
class MyPropertyMap {
public:
typedef Key key_type;
typedef Value value_type;
typedef Value& reference;
typedef boost::lvalue_property_map_tag category; // 声明概念
// 实现get/put/operator[]
};
// 概念检查
BOOST_CONCEPT_ASSERT((boost::LvaluePropertyMapConcept<MyPropertyMap<int, double>>));实践2:延迟属性创建
template <typename Mesh>
class LazyPropertyManager {
Mesh& mesh;
mutable std::optional<PropertyMap> cached_map;
public:
explicit LazyPropertyManager(Mesh& m) : mesh(m) {}
const PropertyMap& get_map() const {
if (\!cached_map) {
cached_map = create_property_map(mesh);
}
return *cached_map;
}
};实践3:属性映射组合
// 将多个属性映射组合成一个访问器
template <typename PositionMap, typename NormalMap, typename ColorMap>
struct VertexAttributes {
PositionMap positions;
NormalMap normals;
ColorMap colors;
auto get_position(key_type key) const { return get(positions, key); }
auto get_normal(key_type key) const { return get(normals, key); }
auto get_color(key_type key) const { return get(colors, key); }
};本节要点
-
属性映射是解耦的关键:将算法与数据结构分离,提高代码复用性。
-
多种实现方式:根据访问模式选择密集存储(vector)或稀疏存储(map)。
-
Boost.PropertyMap概念:遵循标准概念确保与CGAL和BGL的兼容性。
-
生命周期管理:确保属性映射引用的数据在访问期间有效。
-
动态属性:属性映射允许在不修改类定义的情况下添加新属性。
-
组合能力:通过组合简单的属性映射构建复杂的数据访问模式。
进一步阅读
- Boost.PropertyMap文档:属性映射概念和实现
- CGAL文档:Property_map模块和BGL集成
- 《The Boost Graph Library》:属性映射在图算法中的应用