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: 顶点位置属性映射                                     │
│                                                             │
└─────────────────────────────────────────────────────────────┘

属性映射的类别

根据访问方式,属性映射分为几类:

  1. ReadablePropertyMap:只读访问(get操作)
  2. WritablePropertyMap:只写访问(put操作)
  3. ReadWritePropertyMap:读写访问(getput
  4. 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); }
};

本节要点

  1. 属性映射是解耦的关键:将算法与数据结构分离,提高代码复用性。

  2. 多种实现方式:根据访问模式选择密集存储(vector)或稀疏存储(map)。

  3. Boost.PropertyMap概念:遵循标准概念确保与CGAL和BGL的兼容性。

  4. 生命周期管理:确保属性映射引用的数据在访问期间有效。

  5. 动态属性:属性映射允许在不修改类定义的情况下添加新属性。

  6. 组合能力:通过组合简单的属性映射构建复杂的数据访问模式。


进一步阅读

  • Boost.PropertyMap文档:属性映射概念和实现
  • CGAL文档:Property_map模块和BGL集成
  • 《The Boost Graph Library》:属性映射在图算法中的应用