2.2 过滤内核与精确谓词

理论基础

区间算术原理

区间算术（Interval Arithmetic）是一种数值计算方法，其中每个数用一个区间表示，保证包含真实值。对于区间 $[a, b]$ 和 $[c, d]$ ：

加法： $[a, b] + [c, d] = [a + c, b + d]$
减法： $[a, b] - [c, d] = [a - d, b - c]$
乘法： $[a, b] \times [c, d] = [min (a c, a d, b c, b d), max (a c, a d, b c, b d)]$
除法：需要考虑除数区间是否包含零

关键性质：区间运算保证结果区间一定包含真实运算结果。

过滤机制原理

过滤内核的核心思想是快速排除简单情况，仅在必要时使用精确计算：

谓词评估流程：
┌─────────────────┐
│  区间算术计算    │ ──→ 区间不包含0 ──→ 返回确定结果
│  (快速浮点)     │
└────────┬────────┘
         │ 区间包含0（不确定）
         ↓
┌─────────────────┐
│  精确计算        │ ──→ 返回精确结果
│  (较慢但可靠)    │
└─────────────────┘

谓词过滤的数学基础

考虑方向谓词 orientation(p, q, r)，计算行列式：

$Δ = q_{x} - p_{x} r_{x} - p_{x} q_{y} - p_{y} r_{y} - p_{y}$

过滤策略：

使用区间算术计算 $\tilde{Δ} = [Δ_{min}, Δ_{ma x}]$
若 $Δ_{min} > 0$ ，确定返回 LEFT_TURN
若 $Δ_{ma x} < 0$ ，确定返回 RIGHT_TURN
若区间包含0，需要精确计算

过滤成功率：在”良好”的输入数据上，通常 >99% 的谓词调用可以通过区间算术确定。

架构分析

Filtered_kernel 类层次

Kernel (概念)
└── Filtered_kernel<K, CK, EK, FK>
    ├── CK = Cartesian<Interval_nt>     - 区间算术内核（过滤层）
    ├── EK = Cartesian<Exact_nt>        - 精确内核（备用）
    └── FK = Cartesian<Float_nt>        - 浮点内核（构造用）

头文件位置：CGAL/Filtered_kernel.h, CGAL/Filtered_kernel/Cartesian.h

Filtered_kernel 实现

#include <CGAL/Filtered_kernel.h>
 
// Filtered_kernel 简化定义
template < typename CK, typename EK, typename FK >
class Filtered_kernel {
public:
    // 各层内核类型
    typedef CK          Approximate_kernel;     // 近似计算（区间算术）
    typedef EK          Exact_kernel;           // 精确计算
    typedef FK          Floating_point_kernel;  // 浮点构造
    
    // 数类型
    typedef typename CK::FT    FT;  // 区间数类型
    typedef typename EK::RT    RT;  // 精确数类型
    
    // 几何对象类型（使用类型擦除包装）
    typedef Filtered_point_2<Filtered_kernel>   Point_2;
    typedef Filtered_point_3<Filtered_kernel>   Point_3;
    typedef Filtered_vector_2<Filtered_kernel>  Vector_2;
    // ...
};
 
// 便捷定义：自动选择各层内核
template < typename Kernel >
struct Filtered_kernel_base {
    // 从Kernel自动派生CK, EK, FK
    typedef Cartesian< Interval_nt<false> >         CK;
    typedef Cartesian< typename Kernel::RT >        EK;
    typedef Cartesian< double >                     FK;
    
    typedef Filtered_kernel<CK, EK, FK>             Type;
};

Lazy_exact_nt 架构

头文件位置：CGAL/Lazy_exact_nt.h

// Lazy_exact_nt 的简化定义
template < typename ET >
class Lazy_exact_nt {
public:
    typedef ET Exact_type;
    typedef Interval_nt<false> Interval_type;
    
private:
    // 双重表示
    mutable boost::optional<ET> exact_;           // 精确值（延迟计算）
    mutable Interval_type interval_;               // 区间近似值
    
    // 操作DAG节点（用于延迟计算）
    typedef Lazy_exact_nt_rep<ET> Rep;
    std::shared_ptr<Rep> rep_;
    
public:
    // 从近似值构造
    Lazy_exact_nt(double d) : interval_(d) {}
    
    // 从精确值构造
    Lazy_exact_nt(const ET& e) : exact_(e), interval_(to_interval(e)) {}
    
    // 获取区间近似（快速）
    const Interval_type& interval() const {
        return interval_;
    }
    
    // 获取精确值（按需计算）
    const ET& exact() const {
        if (!exact_) {
            exact_ = rep_->compute_exact();
            interval_ = to_interval(*exact_);
        }
        return *exact_;
    }
    
    // 算术运算符（构建延迟计算图）
    Lazy_exact_nt operator+(const Lazy_exact_nt& other) const;
    Lazy_exact_nt operator-(const Lazy_exact_nt& other) const;
    Lazy_exact_nt operator*(const Lazy_exact_nt& other) const;
    Lazy_exact_nt operator/(const Lazy_exact_nt& other) const;
    
    // 比较运算符（使用区间过滤）
    bool operator<(const Lazy_exact_nt& other) const {
        // 首先尝试区间比较
        if (interval_.sup() < other.interval_.inf()) return true;
        if (interval_.inf() > other.interval_.sup()) return false;
        // 区间重叠，需要精确比较
        return exact() < other.exact();
    }
    // ... 其他比较运算符
};

预定义过滤内核

CGAL提供了两个常用的预定义过滤内核：

// 文件：CGAL/Exact_predicates_inexact_constructions_kernel.h
 
// EPICK：精确谓词，非精确构造
typedef Filtered_kernel<
    Cartesian< Interval_nt<false> >,           // CK：区间内核
    Cartesian< Gmpq >,                         // EK：GMP有理数内核
    Cartesian< double >                        // FK：双精度内核
> Exact_predicates_inexact_constructions_kernel_base;
 
struct Exact_predicates_inexact_constructions_kernel 
    : public Exact_predicates_inexact_constructions_kernel_base {
    // 使用浮点进行构造，但谓词是精确的
    typedef double FT;
};
 
// EPECK：精确谓词，精确构造
typedef Filtered_kernel<
    Cartesian< Interval_nt<false> >,           // CK
    Cartesian< Gmpq >,                         // EK
    Cartesian< double >                        // FK
> Exact_predicates_exact_constructions_kernel_base;
 
struct Exact_predicates_exact_constructions_kernel 
    : public Exact_predicates_exact_constructions_kernel_base {
    // 使用Lazy_exact_nt进行延迟精确构造
    typedef Lazy_exact_nt<Gmpq> FT;
};

实现细节

过滤谓词的实现

头文件位置：CGAL/Filtered_kernel/internal/Filtered_predicate.h

// 过滤谓词的简化实现
template < typename EP, typename AP, typename C2E, typename C2A, typename C2F >
class Filtered_predicate {
public:
    typedef typename AP::result_type result_type;
    
private:
    EP exact_predicate_;    // 精确谓词
    AP approx_predicate_;   // 近似谓词（区间算术）
    C2E c2e_;               // 转换到精确内核
    C2A c2a_;               // 转换到近似内核
    C2F c2f_;               // 转换到浮点内核
    
public:
    template < typename ... Args >
    result_type operator()(const Args& ... args) const {
        // 第一步：尝试区间算术计算
        try {
            // 转换参数到近似内核
            auto approx_args = std::make_tuple(c2a_(args)...);
            
            // 执行近似谓词
            result_type result = apply(approx_predicate_, approx_args);
            
            // 检查结果是否确定
            if (is_certain(result)) {
                return result;
            }
        } catch (const Interval_nt<false>::unsafe_comparison&) {
            // 区间算术异常（如除零），继续到精确计算
        }
        
        // 第二步：精确计算
        auto exact_args = std::make_tuple(c2e_(args)...);
        return apply(exact_predicate_, exact_args);
    }
};
 
// 特化：判断结果是否确定
template <>
inline bool is_certain<Sign>(Sign s) {
    return s != ZERO;  // ZERO表示不确定
}
 
template <>
inline bool is_certain<Orientation>(Orientation o) {
    return o != COLLINEAR;  // COLLINEAR可能是不确定的结果
}
 
template <>
inline bool is_certain<Bounded_side>(Bounded_side b) {
    return b != ON_BOUNDARY;
}

对象转换机制

// 内核间对象转换器
// 文件：CGAL/Filtered_kernel/internal/Conversions.h
 
template < typename Source_kernel, typename Target_kernel >
class Kernel_converter {
public:
    // 点转换
    typename Target_kernel::Point_2 operator()(
        const typename Source_kernel::Point_2& p
    ) const {
        return typename Target_kernel::Point_2(
            NT_converter<typename Source_kernel::FT, 
                        typename Target_kernel::FT>()(p.x()),
            NT_converter<typename Source_kernel::FT, 
                        typename Target_kernel::FT>()(p.y())
        );
    }
    
    // 向量转换
    typename Target_kernel::Vector_2 operator()(
        const typename Source_kernel::Vector_2& v
    ) const {
        return typename Target_kernel::Vector_2(
            NT_converter<typename Source_kernel::FT, 
                        typename Target_kernel::FT>()(v.x()),
            NT_converter<typename Source_kernel::FT, 
                        typename Target_kernel::FT>()(v.y())
        );
    }
    
    // 更多转换...
};
 
// 数类型转换器
template < typename From, typename To >
struct NT_converter {
    To operator()(const From& f) const {
        return To(f);  // 默认使用构造函数转换
    }
};
 
// 特化：double到Interval_nt
template <>
struct NT_converter<double, Interval_nt<false>> {
    Interval_nt<false> operator()(double d) const {
        return Interval_nt<false>(d);
    }
};
 
// 特化：Interval_nt到Gmpq
template <>
struct NT_converter<Interval_nt<false>, Gmpq> {
    Gmpq operator()(const Interval_nt<false>& i) const {
        // 使用区间中点作为初始值
        return Gmpq(i.inf()) + Gmpq(i.sup() - i.inf()) / 2;
    }
};

Interval_nt 实现

头文件位置：CGAL/Interval_nt.h

// 区间数类型的简化实现
template < bool Protected = true >
class Interval_nt {
    double inf_, sup_;  // 下界和上界
    
public:
    // 构造函数
    Interval_nt() : inf_(0), sup_(0) {}
    Interval_nt(double d) : inf_(d), sup_(d) {}
    Interval_nt(double i, double s) : inf_(i), sup_(s) {
        CGAL_assertion(i <= s);
    }
    
    // 访问器
    double inf() const { return inf_; }
    double sup() const { return sup_; }
    double median() const { return (inf_ + sup_) / 2; }
    double width() const { return sup_ - inf_; }
    
    // 是否包含零
    bool contains_zero() const { return inf_ <= 0 && sup_ >= 0; }
    
    // 算术运算（保证包含真实结果）
    Interval_nt operator+(const Interval_nt& other) const {
        return Interval_nt(
            CGAL_IA_SUB_DOWN(inf_, other.inf_),
            CGAL_IA_ADD_UP(sup_, other.sup_)
        );
    }
    
    Interval_nt operator-(const Interval_nt& other) const {
        return Interval_nt(
            CGAL_IA_SUB_DOWN(inf_, other.sup_),
            CGAL_IA_SUB_UP(sup_, other.inf_)
        );
    }
    
    Interval_nt operator*(const Interval_nt& other) const {
        double a = inf_, b = sup_, c = other.inf_, d = other.sup_;
        return Interval_nt(
            CGAL_IA_MIN(CGAL_IA_MUL_DOWN(a,c), CGAL_IA_MUL_DOWN(a,d),
                       CGAL_IA_MUL_DOWN(b,c), CGAL_IA_MUL_DOWN(b,d)),
            CGAL_IA_MAX(CGAL_IA_MUL_UP(a,c), CGAL_IA_MUL_UP(a,d),
                       CGAL_IA_MUL_UP(b,c), CGAL_IA_MUL_UP(b,d))
        );
    }
    
    // 比较运算（可能抛出异常表示不确定）
    bool operator<(const Interval_nt& other) const {
        if (sup_ < other.inf_) return true;
        if (inf_ >= other.sup_) return false;
        throw unsafe_comparison("Uncertain comparison");
    }
    
    // 异常类型
    struct unsafe_comparison : public std::exception {
        const char* what() const throw() { return "Unsafe interval comparison"; }
    };
};

使用示例

示例1：基本过滤内核使用

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <iostream>
#include <vector>
 
// 定义两种常用的过滤内核
typedef CGAL::Exact_predicates_inexact_constructions_kernel EPICK;
typedef CGAL::Exact_predicates_exact_constructions_kernel EPECK;
 
void test_epick() {
    std::cout << "=== EPICK Test ===" << std::endl;
    
    EPICK::Point_2 p(0.0, 0.0);
    EPICK::Point_2 q(1.0, 0.0);
    EPICK::Point_2 r(0.5, 0.5);
    
    // 谓词是精确的（使用过滤机制）
    auto orient = CGAL::orientation(p, q, r);
    std::cout << "Orientation: " << orient << std::endl;
    
    // 构造是非精确的（使用double）
    EPICK::Point_2 mid = CGAL::midpoint(p, q);
    std::cout << "Midpoint: (" << mid.x() << ", " << mid.y() << ")" << std::endl;
}
 
void test_epeck() {
    std::cout << "\n=== EPECK Test ===" << std::endl;
    
    EPECK::Point_2 p(0.0, 0.0);
    EPECK::Point_2 q(1.0, 0.0);
    EPECK::Point_2 r(0.5, 0.5);
    
    // 谓词是精确的
    auto orient = CGAL::orientation(p, q, r);
    std::cout << "Orientation: " << orient << std::endl;
    
    // 构造也是精确的（使用Lazy_exact_nt）
    EPECK::Point_2 mid = CGAL::midpoint(p, q);
    std::cout << "Midpoint: (" << mid.x() << ", " << mid.y() << ")" << std::endl;
    
    // 验证精确性：中点应该正好是(0.5, 0)
    EPECK::FT expected_x(0.5);
    if (mid.x() == expected_x) {
        std::cout << "Midpoint x-coordinate is exactly 0.5" << std::endl;
    }
}
 
int main() {
    test_epick();
    test_epeck();
    return 0;
}

示例2：自定义过滤内核

#include <CGAL/Filtered_kernel.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Interval_nt.h>
#include <CGAL/Gmpq.h>
#include <iostream>
 
// 定义自定义数类型
typedef CGAL::Interval_nt<false> Interval;
typedef CGAL::Gmpq Exact;
 
// 自定义过滤内核
typedef CGAL::Cartesian<Interval> CK;
typedef CGAL::Cartesian<Exact> EK;
typedef CGAL::Cartesian<double> FK;
 
typedef CGAL::Filtered_kernel<CK, EK, FK> MyFilteredKernel;
 
typedef MyFilteredKernel::Point_2 Point_2;
typedef MyFilteredKernel::Point_3 Point_3;
 
void test_2d() {
    std::cout << "=== 2D Tests ===" << std::endl;
    
    Point_2 p(0, 0);
    Point_2 q(1, 0);
    Point_2 r(0, 1);
    
    // 方向测试
    auto orient = CGAL::orientation(p, q, r);
    std::cout << "Orientation of (0,0), (1,0), (0,1): " << orient << std::endl;
    
    // 共线点测试
    Point_2 s(2, 0);
    auto orient2 = CGAL::orientation(p, q, s);
    std::cout << "Orientation of (0,0), (1,0), (2,0): " << orient2 << std::endl;
}
 
void test_3d() {
    std::cout << "\n=== 3D Tests ===" << std::endl;
    
    Point_3 p(0, 0, 0);
    Point_3 q(1, 0, 0);
    Point_3 r(0, 1, 0);
    Point_3 s(0, 0, 1);
    
    // 3D方向测试（四面体方向）
    auto orient = CGAL::orientation(p, q, r, s);
    std::cout << "3D Orientation: " << orient << std::endl;
}
 
int main() {
    test_2d();
    test_3d();
    return 0;
}

示例3：Lazy_exact_nt 深入使用

#include <CGAL/Lazy_exact_nt.h>
#include <CGAL/Gmpq.h>
#include <iostream>
#include <chrono>
 
// 定义延迟精确数类型
typedef CGAL::Lazy_exact_nt<CGAL::Gmpq> Lazy_exact;
 
// 计算斐波那契数列（用于产生复杂计算）
Lazy_exact fibonacci(int n) {
    if (n <= 1) return Lazy_exact(n);
    
    Lazy_exact a(0), b(1);
    for (int i = 2; i <= n; ++i) {
        Lazy_exact next = a + b;
        a = b;
        b = next;
    }
    return b;
}
 
void demo_lazy_evaluation() {
    std::cout << "=== Lazy Evaluation Demo ===" << std::endl;
    
    // 创建延迟精确数
    Lazy_exact a(1);
    Lazy_exact b(3);
    
    // 这些操作只构建计算图，不执行精确计算
    Lazy_exact c = a / b;  // 1/3
    Lazy_exact d = c * 3;  // (1/3) * 3
    
    // 此时d的精确值还未计算
    std::cout << "Before exact evaluation:" << std::endl;
    std::cout << "  Interval for d: [" << d.interval().inf() 
              << ", " << d.interval().sup() << "]" << std::endl;
    
    // 强制精确计算
    const CGAL::Gmpq& exact_d = d.exact();
    std::cout << "  Exact value: " << exact_d << std::endl;
    
    // 验证 (1/3) * 3 == 1
    if (d == Lazy_exact(1)) {
        std::cout << "  (1/3) * 3 == 1: true (exact arithmetic)" << std::endl;
    }
}
 
void benchmark_comparison() {
    std::cout << "\n=== Benchmark ===" << std::endl;
    
    const int N = 1000;
    
    // 使用Lazy_exact_nt
    auto start = std::chrono::high_resolution_clock::now();
    Lazy_exact sum_lazy(0);
    for (int i = 1; i <= N; ++i) {
        sum_lazy = sum_lazy + Lazy_exact(1) / Lazy_exact(i);
    }
    // 强制一次精确计算
    volatile auto exact_sum = sum_lazy.exact();
    auto end = std::chrono::high_resolution_clock::now();
    auto lazy_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    // 使用纯Gmpq（立即精确计算）
    start = std::chrono::high_resolution_clock::now();
    CGAL::Gmpq sum_exact(0);
    for (int i = 1; i <= N; ++i) {
        sum_exact = sum_exact + CGAL::Gmpq(1) / CGAL::Gmpq(i);
    }
    end = std::chrono::high_resolution_clock::now();
    auto exact_time = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
    
    std::cout << "Lazy_exact_nt time: " << lazy_time << " us" << std::endl;
    std::cout << "Pure Gmpq time: " << exact_time << " us" << std::endl;
    std::cout << "Speedup: " << (double)exact_time / lazy_time << "x" << std::endl;
}
 
int main() {
    demo_lazy_evaluation();
    benchmark_comparison();
    return 0;
}

示例4：谓词过滤性能测试

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Timer.h>
#include <vector>
#include <random>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel EPICK;
typedef CGAL::Exact_predicates_exact_constructions_kernel EPECK;
typedef CGAL::Cartesian<double> Simple_cartesian;
 
// 生成随机点
template <typename Kernel>
std::vector<typename Kernel::Point_2> generate_points(int n, unsigned seed) {
    std::mt19937 gen(seed);
    std::uniform_real_distribution<> dis(0.0, 1.0);
    
    std::vector<typename Kernel::Point_2> points;
    points.reserve(n);
    
    for (int i = 0; i < n; ++i) {
        points.emplace_back(dis(gen), dis(gen));
    }
    return points;
}
 
// 测试方向谓词
template <typename Kernel>
void benchmark_orientation(const std::vector<typename Kernel::Point_2>& points) {
    CGAL::Timer timer;
    timer.start();
    
    int left = 0, right = 0, collinear = 0;
    const int m = points.size();
    
    for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
            for (int k = j + 1; k < m && k < j + 100; ++k) {
                auto o = CGAL::orientation(points[i], points[j], points[k]);
                if (o == CGAL::LEFT_TURN) left++;
                else if (o == CGAL::RIGHT_TURN) right++;
                else collinear++;
            }
        }
    }
    
    timer.stop();
    std::cout << "  Time: " << timer.time() << "s" << std::endl;
    std::cout << "  Left: " << left << ", Right: " << right 
              << ", Collinear: " << collinear << std::endl;
}
 
// 测试点位置谓词
template <typename Kernel>
void benchmark_side_of_oriented_circle(const std::vector<typename Kernel::Point_2>& points) {
    CGAL::Timer timer;
    timer.start();
    
    int inside = 0, outside = 0, on = 0;
    const int m = std::min((int)points.size(), 1000);
    
    for (int i = 0; i < m; ++i) {
        for (int j = i + 1; j < m; ++j) {
            for (int k = j + 1; k < m; ++k) {
                for (int l = k + 1; l < m && l < k + 10; ++l) {
                    auto s = CGAL::side_of_oriented_circle(
                        points[i], points[j], points[k], points[l]);
                    if (s == CGAL::ON_POSITIVE_SIDE) inside++;
                    else if (s == CGAL::ON_NEGATIVE_SIDE) outside++;
                    else on++;
                }
            }
        }
    }
    
    timer.stop();
    std::cout << "  Time: " << timer.time() << "s" << std::endl;
    std::cout << "  Inside: " << inside << ", Outside: " << outside 
              << ", On: " << on << std::endl;
}
 
int main() {
    const int N = 500;
    const unsigned SEED = 42;
    
    std::cout << "=== Predicate Benchmark (N=" << N << ") ===" << std::endl;
    
    // 生成测试数据
    auto points_epick = generate_points<EPICK>(N, SEED);
    auto points_epeck = generate_points<EPECK>(N, SEED);
    auto points_simple = generate_points<Simple_cartesian>(N, SEED);
    
    std::cout << "\nOrientation tests:" << std::endl;
    
    std::cout << "EPICK:" << std::endl;
    benchmark_orientation<EPICK>(points_epick);
    
    std::cout << "EPECK:" << std::endl;
    benchmark_orientation<EPECK>(points_epeck);
    
    std::cout << "Simple Cartesian (double):" << std::endl;
    benchmark_orientation<Simple_cartesian>(points_simple);
    
    std::cout << "\nSide of oriented circle tests:" << std::endl;
    
    std::cout << "EPICK:" << std::endl;
    benchmark_side_of_oriented_circle<EPICK>(points_epick);
    
    std::cout << "EPECK:" << std::endl;
    benchmark_side_of_oriented_circle<EPECK>(points_epeck);
    
    return 0;
}

复杂度分析

时间复杂度

操作	简单浮点	区间算术	精确计算
基本运算	O(1)	O(1)	O(M)
谓词评估（成功过滤）	-	O(1)	-
谓词评估（失败过滤）	-	O(1) + O(M)	O(M)
构造（EPICK）	O(1)	-	-
构造（EPECK，延迟）	O(1)	-	-
构造（EPECK，强制精确）	-	-	O(M)

其中 M 是精确数运算的复杂度（对于GMP，通常是字长相关的函数）。

空间复杂度

组件	空间开销	说明
Interval_nt	2 × sizeof(double)	存储上下界
Lazy_exact_nt	2 × sizeof(double) + 指针	区间 + DAG节点引用
Filtered_predicate	3×谓词对象 + 3×转换器	三层内核的谓词

过滤效率分析

过滤成功率取决于输入数据的特性：

数据类型	典型过滤成功率	说明
随机均匀分布	99.9%+	极少退化情况
网格/规则数据	95-99%	部分共线/共面点
退化数据	50-90%	大量共线/共面点
病态输入	<50%	设计用于触发精确计算

性能对比总结

内核	谓词速度	构造精度	内存使用	适用场景
Cartesian	最快	低	最小	快速原型、可视化
EPICK	快	精确	中等	大多数几何算法
EPECK	中等	完全精确	较大	需要精确构造的算法
Homogeneous	慢	完全精确	最大	纯精确计算需求

关键文件位置

文件路径	说明
`CGAL/Filtered_kernel.h`	过滤内核主头文件
`CGAL/Filtered_kernel/Cartesian.h`	笛卡尔过滤内核实现
`CGAL/Filtered_kernel/internal/Filtered_predicate.h`	过滤谓词实现
`CGAL/Filtered_kernel/internal/Conversions.h`	内核间转换
`CGAL/Lazy_exact_nt.h`	延迟精确数类型
`CGAL/Interval_nt.h`	区间数类型
`CGAL/Exact_predicates_inexact_constructions_kernel.h`	EPICK预定义
`CGAL/Exact_predicates_exact_constructions_kernel.h`	EPECK预定义
`CGAL/Kernel/function_objects.h`	谓词函数对象

Chunibyo

Explorer

2.2 过滤内核与精确谓词

2.2 过滤内核与精确谓词

理论基础

区间算术原理

过滤机制原理

谓词过滤的数学基础

架构分析

Filtered_kernel 类层次

Filtered_kernel 实现

Lazy_exact_nt 架构

预定义过滤内核

实现细节

过滤谓词的实现

对象转换机制

Interval_nt 实现

使用示例

示例1：基本过滤内核使用

示例2：自定义过滤内核

示例3：Lazy_exact_nt 深入使用

示例4：谓词过滤性能测试

复杂度分析

时间复杂度

空间复杂度

过滤效率分析

性能对比总结

关键文件位置

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

2.2 过滤内核与精确谓词

2.2 过滤内核与精确谓词 §

理论基础 §

区间算术原理 §

过滤机制原理 §

谓词过滤的数学基础 §

架构分析 §

Filtered_kernel 类层次 §

Filtered_kernel 实现 §

Lazy_exact_nt 架构 §

预定义过滤内核 §

实现细节 §

过滤谓词的实现 §

对象转换机制 §

Interval_nt 实现 §

使用示例 §

示例1：基本过滤内核使用 §

示例2：自定义过滤内核 §

示例3：Lazy_exact_nt 深入使用 §

示例4：谓词过滤性能测试 §

复杂度分析 §

时间复杂度 §

空间复杂度 §

过滤效率分析 §

性能对比总结 §

关键文件位置 §

Graph View

Table of Contents

Backlinks

2.2 过滤内核与精确谓词

理论基础

区间算术原理

过滤机制原理

谓词过滤的数学基础

架构分析

Filtered_kernel 类层次

Filtered_kernel 实现

Lazy_exact_nt 架构

预定义过滤内核

实现细节

过滤谓词的实现

对象转换机制

Interval_nt 实现

使用示例

示例1：基本过滤内核使用

示例2：自定义过滤内核

示例3：Lazy_exact_nt 深入使用

示例4：谓词过滤性能测试

复杂度分析

时间复杂度

空间复杂度

过滤效率分析

性能对比总结

关键文件位置