相关章节: 组合地图

5.1 Nef多面体

理论基础

Nef多面体的数学定义

Nef多面体（Nef Polyhedra）是由Walter Nef在1978年提出的一种几何表示方法，用于描述 $d$ 维空间中的多面体集合。

定义：Nef多面体是半空间（half-spaces）的布尔组合：

$P = ⋃_{i} ⋂_{j} H_{ij}$

其中 $H_{ij}$ 是半空间（由线性不等式定义的集合）。

关键特性：

闭包性：对布尔运算（并、交、差、补）封闭
维度无关：适用于任意维度
统一表示：同时表示开集和闭集、有界和无界集合
精确性：支持精确的几何计算

球面映射（Spherical Map）

Nef多面体的核心数据结构是球面映射，它将多面体的局部邻域信息编码在单位球面上。

概念：

对于多面体表面上的每个点，考虑其无穷小邻域
将该邻域投影到单位球面上
球面上的划分表示该点周围的空间结构

顶点球面映射：

对于顶点 $v$ ，球面映射表示 $v$ 周围的空间划分
球面上的每个区域对应一个关联的体（volume）
球面上的边对应关联的面（face）
球面上的顶点对应关联的边（edge）

选择性布尔运算

Nef多面体支持选择性布尔运算，允许用户指定参与运算的特定部分：

结果 = A ⊕ B （在选定的面/边/顶点上）

选择机制基于**标记（marks）**系统：

每个顶点、边、面、体都有布尔标记
标记表示该元素是否属于特定集合
布尔运算可以仅作用于标记为真的元素

架构分析

类层次结构

Nef_polyhedron_2<T>
├── Sphere_map           // 球面映射
│   ├── Vertex           // 带球面映射的顶点
│   ├── Halfedge         // 半边
│   └── Face             // 面
└── Mark system          // 标记系统

Nef_polyhedron_3<T>
├── Sphere_map           // 3D球面映射
│   ├── Vertex           // 顶点
│   ├── Halfedge         // 半边
│   ├── Halffacet        // 半面
│   └── Volume           // 体
└── Mark system

头文件位置：CGAL/Nef_polyhedron_2.h, CGAL/Nef_polyhedron_3.h

Nef_polyhedron_2 实现

#include <CGAL/Nef_polyhedron_2.h>
 
// Nef_polyhedron_2 的简化定义
template <class Kernel_>
class Nef_polyhedron_2 {
public:
    typedef Kernel_                               Kernel;
    typedef typename Kernel::Point_2              Point_2;
    typedef typename Kernel::Segment_2            Segment_2;
    typedef typename Kernel::Line_2               Line_2;
    typedef typename Kernel::Direction_2          Direction_2;
    
    // 内部表示类型
    typedef Sphere_map<Kernel>                    Sphere_map;
    typedef typename Sphere_map::Vertex           Vertex;
    typedef typename Sphere_map::Halfedge         Halfedge;
    typedef typename Sphere_map::Face             Face;
    
    // 标记类型
    typedef bool                                  Mark;
    
    // 内容类型枚举
    enum Content { EMPTY, COMPLEMENT, POLYHEDRON };
    
private:
    Sphere_map sphere_map_;     // 球面映射
    Content content_;           // 内容类型
    
public:
    // 构造函数
    Nef_polyhedron_2(Content content = EMPTY);
    
    // 从半平面构造
    Nef_polyhedron_2(const Line_2& line, 
                     const Point_2& point,
                     Content content = POLYHEDRON);
    
    // 从多边形构造
    Nef_polyhedron_2(const Polygon_2<Kernel>& polygon);
    
    // 从简单多边形构造
    template <class Forward_iterator>
    Nef_polyhedron_2(Forward_iterator begin, Forward_iterator end);
    
    // 布尔运算
    Nef_polyhedron_2 operator+(const Nef_polyhedron_2& other) const;  // 并
    Nef_polyhedron_2 operator*(const Nef_polyhedron_2& other) const;  // 交
    Nef_polyhedron_2 operator-(const Nef_polyhedron_2& other) const;  // 差
    Nef_polyhedron_2 complement() const;                               // 补
    
    // 修改操作
    Nef_polyhedron_2& operator+=(const Nef_polyhedron_2& other);
    Nef_polyhedron_2& operator*=(const Nef_polyhedron_2& other);
    Nef_polyhedron_2& operator-=(const Nef_polyhedron_2& other);
    
    // 查询
    bool is_empty() const;
    bool is_plane() const;  // 整个平面
    bool is_bounded() const;
    bool contains(const Point_2& p) const;
    bool contained_in(const Nef_polyhedron_2& other) const;
    
    // 转换
    Polygon_2<Kernel> to_polygon() const;
    void extract_polygons(std::vector<Polygon_2<Kernel>>& polygons) const;
    
    // 迭代器
    class Vertex_iterator;
    class Halfedge_iterator;
    class Face_iterator;
    
    Vertex_iterator vertices_begin() const;
    Vertex_iterator vertices_end() const;
    Halfedge_iterator halfedges_begin() const;
    Halfedge_iterator halfedges_end() const;
    Face_iterator faces_begin() const;
    Face_iterator faces_end() const;
    
    // 标记访问
    Mark mark(Vertex_handle v) const;
    Mark mark(Halfedge_handle e) const;
    Mark mark(Face_handle f) const;
    
    void set_mark(Vertex_handle v, Mark m);
    void set_mark(Halfedge_handle e, Mark m);
    void set_mark(Face_handle f, Mark m);
};

Nef_polyhedron_3 实现

#include <CGAL/Nef_polyhedron_3.h>
 
// Nef_polyhedron_3 的简化定义
template <class Kernel_, class Items_ = Default_items, 
          class Mark_ = bool, class Mark_vector_ = std::vector<Mark_>>
class Nef_polyhedron_3 {
public:
    typedef Kernel_                               Kernel;
    typedef Items_                                Items;
    typedef Mark_                                 Mark;
    typedef Mark_vector_                          Mark_vector;
    
    typedef typename Kernel::Point_3              Point_3;
    typedef typename Kernel::Plane_3              Plane_3;
    typedef typename Kernel::Segment_3            Segment_3;
    
    // 内部表示类型
    typedef Sphere_map<Kernel, Items>             Sphere_map;
    typedef typename Sphere_map::Vertex           Vertex;
    typedef typename Sphere_map::Halfedge         Halfedge;
    typedef typename Sphere_map::Halffacet        Halffacet;
    typedef typename Sphere_map::Volume           Volume;
    typedef typename Sphere_map::SVertex          SVertex;    // 球面顶点
    typedef typename Sphere_map::SHalfedge        SHalfedge;  // 球面半边
    typedef typename Sphere_map::SHalfloop        SHalfloop;  // 球面环
    typedef typename Sphere_map::SFace            SFace;      // 球面面
    
    // 内容类型
    enum Content { EMPTY, COMPLEMENT, POLYHEDRON };
    
private:
    Sphere_map sphere_map_;     // 3D球面映射
    Content content_;
    
public:
    // 构造函数
    Nef_polyhedron_3(Content content = EMPTY);
    
    // 从半空间构造
    Nef_polyhedron_3(const Plane_3& plane, 
                     const Point_3& point,
                     Content content = POLYHEDRON);
    
    // 从多面体构造
    template <class Polyhedron>
    Nef_polyhedron_3(const Polyhedron& poly);
    
    // 从曲面网格构造
    template <class Surface_mesh>
    Nef_polyhedron_3(const Surface_mesh& mesh);
    
    // 布尔运算
    Nef_polyhedron_3 operator+(const Nef_polyhedron_3& other) const;  // 并
    Nef_polyhedron_3 operator*(const Nef_polyhedron_3& other) const;  // 交
    Nef_polyhedron_3 operator-(const Nef_polyhedron_3& other) const;  // 差
    Nef_polyhedron_3 complement() const;                               // 补
    
    // 修改操作
    Nef_polyhedron_3& operator+=(const Nef_polyhedron_3& other);
    Nef_polyhedron_3& operator*=(const Nef_polyhedron_3& other);
    Nef_polyhedron_3& operator-=(const Nef_polyhedron_3& other);
    
    // 查询
    bool is_empty() const;
    bool is_space() const;  // 整个空间
    bool is_bounded() const;
    bool contains(const Point_3& p) const;
    bool contained_in(const Nef_polyhedron_3& other) const;
    
    // 转换
    template <class Polyhedron>
    void convert_to_polyhedron(Polyhedron& poly) const;
    
    template <class Surface_mesh>
    void convert_to_mesh(Surface_mesh& mesh) const;
    
    // 访问内部结构
    Volume_handle volumes_begin() const;
    Volume_handle volumes_end() const;
    
    // 顶点访问（带球面映射）
    class Vertex_iterator;
    Vertex_iterator vertices_begin() const;
    Vertex_iterator vertices_end() const;
    
    // 标记系统
    Mark mark(Vertex_handle v) const;
    Mark mark(Halfedge_handle e) const;
    Mark mark(Halffacet_handle f) const;
    Mark mark(Volume_handle v) const;
    
    void set_mark(Vertex_handle v, Mark m);
    void set_mark(Halfedge_handle e, Mark m);
    void set_mark(Halffacet_handle f, Mark m);
    void set_mark(Volume_handle v, Mark m);
    
    // 选择性布尔运算
    Nef_polyhedron_3 intersection(const Plane_3& plane, 
                                   const Point_3& point) const;
    Nef_polyhedron_3 join(const Plane_3& plane, 
                          const Point_3& point) const;
    
    // 正则化
    Nef_polyhedron_3 regularization() const;
    
    // 边界计算
    Nef_polyhedron_3 boundary() const;
    
    // 闭包、内部、外部
    Nef_polyhedron_3 closure() const;
    Nef_polyhedron_3 interior() const;
    Nef_polyhedron_3 exterior() const;
};

球面映射实现

// 3D球面映射的简化定义
template <class Kernel_, class Items_>
class Sphere_map {
public:
    typedef Kernel_                               Kernel;
    typedef Items_                                Items;
    
    // 几何类型
    typedef typename Kernel::Point_3              Point_3;
    typedef typename Kernel::Vector_3             Vector_3;
    typedef typename Kernel::Plane_3              Plane_3;
    typedef typename Kernel::Circle_3             Circle_3;
    typedef typename Kernel::Sphere_3             Sphere_3;
    
    // 组合类型
    typedef typename Items::template Vertex<Sphere_map>      Vertex;
    typedef typename Items::template Halfedge<Sphere_map>    Halfedge;
    typedef typename Items::template Halffacet<Sphere_map>   Halffacet;
    typedef typename Items::template Volume<Sphere_map>      Volume;
    
    // 球面图类型（存储在每个顶点中）
    typedef typename Items::template SVertex<Sphere_map>     SVertex;
    typedef typename Items::template SHalfedge<Sphere_map>   SHalfedge;
    typedef typename Items::template SHalfloop<Sphere_map>   SHalfloop;
    typedef typename Items::template SFace<Sphere_map>       SFace;
    
    // 半边数据结构
    typedef HalfedgeDS<
        typename Items::template HDS_items<Sphere_map>
    > HDS;
    
private:
    HDS hds_;  // 半边数据结构
    
public:
    // 顶点操作
    Vertex_handle new_vertex(const Point_3& p);
    void delete_vertex(Vertex_handle v);
    
    // 半边操作
    Halfedge_handle new_halfedge(Vertex_handle src, Vertex_handle tgt);
    
    // 球面图操作（存储在顶点中）
    SVertex_handle new_svertex(Vertex_handle v, const Vector_3& dir);
    SHalfedge_handle new_shalfedge(SVertex_handle src, SVertex_handle tgt);
    SFace_handle new_sface(Vertex_handle v);
    
    // 访问器
    Vertex_iterator vertices_begin();
    Vertex_iterator vertices_end();
    Halfedge_iterator halfedges_begin();
    Halfedge_iterator halfedges_end();
    Halffacet_iterator halffacets_begin();
    Halffacet_iterator halffacets_end();
    Volume_iterator volumes_begin();
    Volume_iterator volumes_end();
};
 
// 顶点类（包含球面图）
template <class Sphere_map_>
class Vertex {
public:
    typedef Sphere_map_                           Sphere_map;
    typedef typename Sphere_map::Point_3          Point_3;
    typedef typename Sphere_map::SVertex          SVertex;
    typedef typename Sphere_map::SHalfedge        SHalfedge;
    typedef typename Sphere_map::SFace            SFace;
    
private:
    Point_3 point_;           // 顶点坐标
    Sphere_map sm_;           // 球面图（表示局部邻域）
    
public:
    const Point_3& point() const { return point_; }
    void set_point(const Point_3& p) { point_ = p; }
    
    // 球面图访问
    Sphere_map& sphere_map() { return sm_; }
    const Sphere_map& sphere_map() const { return sm_; }
    
    // 球面图遍历
    SVertex_iterator svertices_begin();
    SVertex_iterator svertices_end();
    SFace_iterator sfaces_begin();
    SFace_iterator sfaces_end();
};

实现细节

布尔运算算法

// 布尔运算的核心实现（简化版）
template <class Kernel>
Nef_polyhedron_2<Kernel> Nef_polyhedron_2<Kernel>::boolean_operation(
    const Nef_polyhedron_2& A,
    const Nef_polyhedron_2& B,
    Boolean_operation_type op)
{
    // 步骤1：构建合成球面映射
    // 将A和B的边叠加，创建所有交点
    Sphere_map composite;
    overlay(A.sphere_map_, B.sphere_map_, composite);
    
    // 步骤2：传播标记
    // 根据原始多面体的标记和布尔运算类型，计算新标记
    propagate_marks(composite, A.sphere_map_, B.sphere_map_, op);
    
    // 步骤3：简化
    // 移除冗余边和顶点
    simplify(composite);
    
    // 步骤4：构建结果多面体
    Nef_polyhedron_2 result;
    result.sphere_map_ = composite;
    result.content_ = POLYHEDRON;
    
    return result;
}
 
// 叠加两个球面映射
template <class Kernel>
void overlay(const Sphere_map& A, const Sphere_map& B, Sphere_map& result) {
    // 复制A的所有顶点和边
    for (auto v = A.vertices_begin(); v != A.vertices_end(); ++v) {
        result.new_vertex(v->point());
    }
    
    // 复制B的顶点和边，创建交点
    for (auto v = B.vertices_begin(); v != B.vertices_end(); ++v) {
        // 检查是否已存在
        auto existing = result.find_vertex(v->point());
        if (existing == result.vertices_end()) {
            result.new_vertex(v->point());
        }
    }
    
    // 计算边相交并细分
    for (auto e1 = A.halfedges_begin(); e1 != A.halfedges_end(); ++e1) {
        for (auto e2 = B.halfedges_begin(); e2 != B.halfedges_end(); ++e2) {
            // 计算线段相交
            auto inter = CGAL::intersection(
                Segment_2(e1->source()->point(), e1->target()->point()),
                Segment_2(e2->source()->point(), e2->target()->point())
            );
            
            if (inter) {
                if (const Point_2* p = boost::get<Point_2>(&*inter)) {
                    // 在交点处细分边
                    result.split_edge_at_point(e1, *p);
                    result.split_edge_at_point(e2, *p);
                }
            }
        }
    }
}
 
// 标记传播
template <class Kernel>
void propagate_marks(Sphere_map& composite, 
                     const Sphere_map& A,
                     const Sphere_map& B,
                     Boolean_operation_type op) {
    for (auto v = composite.vertices_begin(); v != composite.vertices_end(); ++v) {
        // 确定该顶点在A和B中的标记
        Mark in_A = A.contains(v->point());
        Mark in_B = B.contains(v->point());
        
        // 根据布尔运算类型计算新标记
        Mark result_mark;
        switch (op) {
            case UNION:        result_mark = in_A || in_B; break;
            case INTERSECTION: result_mark = in_A && in_B; break;
            case DIFFERENCE:   result_mark = in_A && !in_B; break;
            case COMPLEMENT:   result_mark = !in_A; break;
        }
        
        v->set_mark(result_mark);
    }
    
    // 传播到边和面
    propagate_to_faces(composite);
}

点包含测试

// 点包含测试（使用球面映射）
template <class Kernel>
bool Nef_polyhedron_3<Kernel>::contains(const Point_3& p) const {
    if (is_empty()) return false;
    if (is_space()) return true;
    
    // 找到包含p的体
    Volume_handle vol = locate(p);
    return mark(vol);
}
 
// 定位点所在的体
template <class Kernel>
Volume_handle Nef_polyhedron_3<Kernel>::locate(const Point_3& p) const {
    // 从无穷远体开始
    Volume_handle current = volumes_begin();
    
    // 射线投射算法
    Ray_3 ray(p, Direction_3(1, 0, 0));  // 正x方向的射线
    
    // 找到射线穿过的所有面
    std::vector<Halffacet_handle> crossed_facets;
    for (auto f = halffacets_begin(); f != halffacets_end(); ++f) {
        if (f->plane().has_on_positive_side(p)) {
            // 检查射线是否与面相交
            auto inter = CGAL::intersection(ray, f->plane());
            if (inter) {
                crossed_facets.push_back(f);
            }
        }
    }
    
    // 按距离排序
    std::sort(crossed_facets.begin(), crossed_facets.end(),
              [&p](Halffacet_handle a, Halffacet_handle b) {
                  return squared_distance(p, a->plane()) < 
                         squared_distance(p, b->plane());
              });
    
    // 根据穿过的面确定所在的体
    for (auto f : crossed_facets) {
        current = (current == f->incident_volume()) ? 
                  f->twin()->incident_volume() : 
                  f->incident_volume();
    }
    
    return current;
}

选择性布尔运算

// 选择性布尔运算实现
template <class Kernel>
Nef_polyhedron_3<Kernel> Nef_polyhedron_3<Kernel>::selective_union(
    const Nef_polyhedron_3& other,
    Mark_selector selector) const
{
    Nef_polyhedron_3 result = *this;
    
    // 遍历所有面
    for (auto f = halffacets_begin(); f != halffacets_end(); ++f) {
        if (selector(f)) {
            // 根据选择器决定是否包含该面
            result.set_mark(f, mark(f) || other.mark(f));
        }
    }
    
    // 清理和简化
    result.simplify();
    
    return result;
}
 
// 示例选择器：仅选择特定平面上的面
struct Plane_selector {
    Plane_3 plane;
    FT tolerance;
    
    bool operator()(Halffacet_handle f) const {
        return CGAL::squared_distance(plane, f->plane()) < tolerance;
    }
};

使用示例

示例1：基本2D Nef多面体操作

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_2.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Line_2 Line_2;
typedef CGAL::Nef_polyhedron_2<K> Nef_polyhedron_2;
 
int main() {
    // 从半平面创建Nef多面体
    Line_2 line1(Point_2(0, 0), Point_2(1, 0));  // x轴
    Nef_polyhedron_2 halfplane1(line1, Point_2(0, 1), Nef_polyhedron_2::POLYHEDRON);
    
    Line_2 line2(Point_2(0, 0), Point_2(0, 1));  // y轴
    Nef_polyhedron_2 halfplane2(line2, Point_2(1, 0), Nef_polyhedron_2::POLYHEDRON);
    
    // 布尔运算：交集（第一象限）
    Nef_polyhedron_2 first_quadrant = halfplane1 * halfplane2;
    
    std::cout << "First quadrant is empty: " << first_quadrant.is_empty() << std::endl;
    std::cout << "Contains (1,1): " << first_quadrant.contains(Point_2(1, 1)) << std::endl;
    std::cout << "Contains (-1,1): " << first_quadrant.contains(Point_2(-1, 1)) << std::endl;
    
    // 创建三角形
    std::vector<Point_2> triangle_points = {
        Point_2(0, 0), Point_2(5, 0), Point_2(0, 5)
    };
    Nef_polyhedron_2 triangle(triangle_points.begin(), triangle_points.end());
    
    // 创建矩形
    std::vector<Point_2> rect_points = {
        Point_2(2, 2), Point_2(7, 2), Point_2(7, 7), Point_2(2, 7)
    };
    Nef_polyhedron_2 rectangle(rect_points.begin(), rect_points.end());
    
    // 布尔运算
    Nef_polyhedron_2 intersection = triangle * rectangle;
    Nef_polyhedron_2 union_result = triangle + rectangle;
    Nef_polyhedron_2 difference = triangle - rectangle;
    
    std::cout << "\nBoolean operations:" << std::endl;
    std::cout << "  Intersection is empty: " << intersection.is_empty() << std::endl;
    std::cout << "  Union is empty: " << union_result.is_empty() << std::endl;
    std::cout << "  Difference is empty: " << difference.is_empty() << std::endl;
    
    return 0;
}

示例2：3D Nef多面体操作

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <CGAL/Polyhedron_3.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_3 Point_3;
typedef K::Plane_3 Plane_3;
typedef CGAL::Nef_polyhedron_3<K> Nef_polyhedron_3;
typedef CGAL::Polyhedron_3<K> Polyhedron_3;
 
// 创建立方体
Nef_polyhedron_3 create_cube(const Point_3& min_corner, const Point_3& max_corner) {
    // 使用6个半空间的交集
    Plane_3 planes[6] = {
        Plane_3(Point_3(min_corner.x(), 0, 0), Vector_3(-1, 0, 0)),  // x >= min_x
        Plane_3(Point_3(max_corner.x(), 0, 0), Vector_3(1, 0, 0)),   // x <= max_x
        Plane_3(Point_3(0, min_corner.y(), 0), Vector_3(0, -1, 0)),  // y >= min_y
        Plane_3(Point_3(0, max_corner.y(), 0), Vector_3(0, 1, 0)),   // y <= max_y
        Plane_3(Point_3(0, 0, min_corner.z()), Vector_3(0, 0, -1)),  // z >= min_z
        Plane_3(Point_3(0, 0, max_corner.z()), Vector_3(0, 0, 1))    // z <= max_z
    };
    
    Nef_polyhedron_3 cube(planes[0], Point_3(0, 0, 0), Nef_polyhedron_3::POLYHEDRON);
    for (int i = 1; i < 6; ++i) {
        Nef_polyhedron_3 halfspace(planes[i], Point_3(0, 0, 0), Nef_polyhedron_3::POLYHEDRON);
        cube *= halfspace;
    }
    
    return cube;
}
 
int main() {
    // 创建两个立方体
    Nef_polyhedron_3 cube1 = create_cube(Point_3(0, 0, 0), Point_3(5, 5, 5));
    Nef_polyhedron_3 cube2 = create_cube(Point_3(3, 3, 3), Point_3(8, 8, 8));
    
    std::cout << "Cube1 contains (2,2,2): " << cube1.contains(Point_3(2, 2, 2)) << std::endl;
    std::cout << "Cube1 contains (6,6,6): " << cube1.contains(Point_3(6, 6, 6)) << std::endl;
    
    // 布尔运算
    Nef_polyhedron_3 intersection = cube1 * cube2;
    Nef_polyhedron_3 union_result = cube1 + cube2;
    Nef_polyhedron_3 difference = cube1 - cube2;
    
    std::cout << "\nBoolean operations:" << std::endl;
    std::cout << "  Intersection is empty: " << intersection.is_empty() << std::endl;
    std::cout << "  Union is bounded: " << union_result.is_bounded() << std::endl;
    std::cout << "  Difference is empty: " << difference.is_empty() << std::endl;
    
    // 转换为Polyhedron
    Polyhedron_3 poly;
    if (intersection.is_bounded() && !intersection.is_empty()) {
        intersection.convert_to_polyhedron(poly);
        std::cout << "\nIntersection polyhedron has " << poly.size_of_vertices() 
                  << " vertices" << std::endl;
    }
    
    return 0;
}

示例3：复杂布尔运算与标记系统

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Nef_polyhedron_3.h>
#include <iostream>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_3 Point_3;
typedef CGAL::Nef_polyhedron_3<K> Nef_polyhedron_3;
 
int main() {
    // 创建基础形状
    Nef_polyhedron_3 cube1 = create_cube(Point_3(0, 0, 0), Point_3(4, 4, 4));
    Nef_polyhedron_3 cube2 = create_cube(Point_3(2, 0, 0), Point_3(6, 4, 4));
    Nef_polyhedron_3 cube3 = create_cube(Point_3(0, 2, 0), Point_3(4, 6, 4));
    
    // 复杂布尔运算
    Nef_polyhedron_3 result = (cube1 + cube2) * cube3;
    
    std::cout << "Complex boolean result:" << std::endl;
    std::cout << "  Is empty: " << result.is_empty() << std::endl;
    std::cout << "  Is bounded: " << result.is_bounded() << std::endl;
    
    // 访问内部结构
    std::cout << "\nInternal structure:" << std::endl;
    
    int vertex_count = 0;
    for (auto v = result.vertices_begin(); v != result.vertices_end(); ++v) {
        ++vertex_count;
    }
    std::cout << "  Vertices: " << vertex_count << std::endl;
    
    int volume_count = 0;
    for (auto vol = result.volumes_begin(); vol != result.volumes_end(); ++vol) {
        ++volume_count;
        std::cout << "  Volume mark: " << result.mark(vol) << std::endl;
    }
    std::cout << "  Total volumes: " << volume_count << std::endl;
    
    // 正则化（移除低维特征）
    Nef_polyhedron_3 regular = result.regularization();
    std::cout << "\nAfter regularization:" << std::endl;
    std::cout << "  Is equal to original: " << (regular == result) << std::endl;
    
    return 0;
}

复杂度分析

时间复杂度

操作	时间复杂度	说明
构造（从n个半空间）	O(n²) 或 O(n log n)	取决于算法
布尔运算	O((n+m) log(n+m) + k)	n,m为顶点数，k为交点数
点包含测试	O(n)	射线投射
转换为多面体	O(n)	遍历所有面
正则化	O(n)	清理低维特征

空间复杂度

表示	空间复杂度	说明
Nef_polyhedron_2	O(n)	n为顶点数
Nef_polyhedron_3	O(n + e + f + v)	半边数据结构
球面映射（每个顶点）	O(d)	d为度数

布尔运算复杂度分析

布尔运算的复杂度主要取决于：

叠加（Overlay）：O((n+m) log(n+m))
标记传播：O(n+m)
简化：O(n+m)

总复杂度：O((n+m) log(n+m) + k)，其中k是新创建的交点数。

关键文件位置

文件路径	说明
`CGAL/Nef_polyhedron_2.h`	2D Nef多面体主头文件
`CGAL/Nef_polyhedron_3.h`	3D Nef多面体主头文件
`CGAL/Nef_2/Sphere_map.h`	2D球面映射
`CGAL/Nef_3/Sphere_map.h`	3D球面映射
`CGAL/Nef_2/PM_visualizor.h`	2D可视化
`CGAL/Nef_3/Visualizor.h`	3D可视化
`CGAL/Nef_2/Boolean_operations.h`	布尔运算实现
`CGAL/Nef_3/Boolean_operations.h`	3D布尔运算
`CGAL/Nef_2/Point_location.h`	点定位
`CGAL/Nef_3/Point_location.h`	3D点定位

Chunibyo

Explorer

5.1 Nef多面体

5.1 Nef多面体

理论基础

Nef多面体的数学定义

球面映射（Spherical Map）

选择性布尔运算

架构分析

类层次结构

Nef_polyhedron_2 实现

Nef_polyhedron_3 实现

球面映射实现

实现细节

布尔运算算法

点包含测试

选择性布尔运算

使用示例

示例1：基本2D Nef多面体操作

示例2：3D Nef多面体操作

示例3：复杂布尔运算与标记系统

复杂度分析

时间复杂度

空间复杂度

布尔运算复杂度分析

关键文件位置

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

5.1 Nef多面体

5.1 Nef多面体 §

理论基础 §

Nef多面体的数学定义 §

球面映射（Spherical Map） §

选择性布尔运算 §

架构分析 §

类层次结构 §

Nef_polyhedron_2 实现 §

Nef_polyhedron_3 实现 §

球面映射实现 §

实现细节 §

布尔运算算法 §

点包含测试 §

选择性布尔运算 §

使用示例 §

示例1：基本2D Nef多面体操作 §

示例2：3D Nef多面体操作 §

示例3：复杂布尔运算与标记系统 §

复杂度分析 §

时间复杂度 §

空间复杂度 §

布尔运算复杂度分析 §

关键文件位置 §

Graph View

Table of Contents

Backlinks

5.1 Nef多面体

理论基础

Nef多面体的数学定义

球面映射（Spherical Map）

选择性布尔运算

架构分析

类层次结构

Nef_polyhedron_2 实现

Nef_polyhedron_3 实现

球面映射实现

实现细节

布尔运算算法

点包含测试

选择性布尔运算

使用示例

示例1：基本2D Nef多面体操作

示例2：3D Nef多面体操作

示例3：复杂布尔运算与标记系统

复杂度分析

时间复杂度

空间复杂度

布尔运算复杂度分析

关键文件位置