相关章节: 过滤内核与精确谓词 | 代数基础与数类型

2.1 笛卡尔与齐次坐标系统

理论基础

坐标表示的数学原理

在计算几何中，点的坐标表示是构建所有几何算法的基础。CGAL提供了两种主要的坐标表示方式：笛卡尔坐标（Cartesian）和齐次坐标（Homogeneous）。

笛卡尔坐标

笛卡尔坐标使用n个实数表示n维空间中的点。在二维空间中，点表示为 $(x, y)$ ；在三维空间中，点表示为 $(x, y, z)$ 。

数学定义：

点： $P = (x_{1}, x_{2}, ..., x_{n}) \in R^{n}$
向量： $v = (v_{1}, v_{2}, ..., v_{n})$

笛卡尔坐标的优势在于直观性和计算简单性，但在处理投影几何和无穷远点时存在局限。

齐次坐标

齐次坐标通过引入额外的坐标维度，统一了有限点和无穷远点的表示。n维空间中的点用n+1个坐标表示。

数学定义：

二维齐次点： $P = (x, y, w)$ ，对应笛卡尔点 $(x / w, y / w)$ （当 $w \neq = 0$ ）
三维齐次点： $P = (x, y, z, w)$ ，对应笛卡尔点 $(x / w, y / w, z / w)$ （当 $w \neq = 0$ ）
当 $w = 0$ 时，表示无穷远点（方向向量）

齐次坐标的等价性：对于任意非零标量 $λ$ ， $(x, y, w)$ 和 $(λ x, λ y, λ w)$ 表示同一个点。

优势：

统一处理有限点和无穷远点
投影变换可用矩阵乘法表示
避免除法运算，提高数值稳定性

坐标转换

笛卡尔转齐次： $(x, y) \to (x, y, 1)$ $(x, y, z) \to (x, y, z, 1)$

齐次转笛卡尔（归一化）： $(x, y, w) \to (x / w, y / w)$ $(x, y, z, w) \to (x / w, y / w, z / w)$

架构分析

内核类层次结构

CGAL的内核架构采用模板化设计，允许用户选择不同的坐标表示和数类型。

Kernel (概念)
├── Cartesian<FT>      - 笛卡尔坐标实现
└── Homogeneous<RT>    - 齐次坐标实现

Cartesian_kernel 实现

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

#include <CGAL/Cartesian.h>
 
// Cartesian_kernel 的简化定义
template < typename FT_ >
class Cartesian_kernel {
public:
    // 数类型定义
    typedef FT_                    FT;           // 域类型（Field Type）
    typedef FT_                    RT;           // 环类型（Ring Type）
    
    // 几何对象类型
    typedef Cartesian_point_2<Cartesian_kernel>      Point_2;
    typedef Cartesian_point_3<Cartesian_kernel>      Point_3;
    typedef Cartesian_vector_2<Cartesian_kernel>     Vector_2;
    typedef Cartesian_vector_3<Cartesian_kernel>     Vector_3;
    typedef Cartesian_direction_2<Cartesian_kernel>  Direction_2;
    typedef Cartesian_direction_3<Cartesian_kernel>  Direction_3;
    typedef Cartesian_line_2<Cartesian_kernel>       Line_2;
    typedef Cartesian_plane_3<Cartesian_kernel>      Plane_3;
    
    // 更多几何对象类型...
};

Homogeneous_kernel 实现

头文件位置：CGAL/Homogeneous.h, CGAL/Homogeneous/Homogeneous_base.h

#include <CGAL/Homogeneous.h>
 
// Homogeneous_kernel 的简化定义
template < typename RT_ >
class Homogeneous_kernel {
public:
    // 数类型定义
    typedef Quotient<RT_>          FT;           // 域类型（通过商构造）
    typedef RT_                    RT;           // 环类型
    
    // 几何对象类型
    typedef Homogeneous_point_2<Homogeneous_kernel>   Point_2;
    typedef Homogeneous_point_3<Homogeneous_kernel>   Point_3;
    typedef Homogeneous_vector_2<Homogeneous_kernel>  Vector_2;
    typedef Homogeneous_vector_3<Homogeneous_kernel>  Vector_3;
    // ...
};

关键区别

特性	Cartesian_kernel	Homogeneous_kernel
坐标存储	直接存储笛卡尔坐标	存储齐次坐标 (x,y,w) 或 (x,y,z,w)
FT类型	直接使用模板参数	Quotient
RT类型	同FT	模板参数
数运算	直接使用FT的运算	分子分母分别运算
适合场景	浮点近似计算	精确有理数计算

实现细节

笛卡尔点的实现

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

// Cartesian_point_2 的简化实现
template < typename K >
class Cartesian_point_2 {
    typedef typename K::FT FT;
    
private:
    FT x_, y_;  // 直接存储笛卡尔坐标
    
public:
    // 默认构造函数
    Cartesian_point_2() : x_(FT(0)), y_(FT(0)) {}
    
    // 带参数构造函数
    Cartesian_point_2(const FT& x, const FT& y) : x_(x), y_(y) {}
    
    // 坐标访问器
    const FT& x() const { return x_; }
    const FT& y() const { return y_; }
    
    // 齐次坐标访问（用于统一接口）
    FT hx() const { return x_; }
    FT hy() const { return y_; }
    FT hw() const { return FT(1); }
    
    // 类型转换操作符
    operator typename K::Point_2() const;
};

齐次点的实现

// Homogeneous_point_2 的简化实现
template < typename K >
class Homogeneous_point_2 {
    typedef typename K::RT RT;
    
private:
    RT hx_, hy_, hw_;  // 存储齐次坐标
    
public:
    // 默认构造函数（原点）
    Homogeneous_point_2() : hx_(RT(0)), hy_(RT(0)), hw_(RT(1)) {}
    
    // 从笛卡尔坐标构造
    Homogeneous_point_2(const RT& x, const RT& y) 
        : hx_(x), hy_(y), hw_(RT(1)) {}
    
    // 完整齐次坐标构造
    Homogeneous_point_2(const RT& hx, const RT& hy, const RT& hw)
        : hx_(hx), hy_(hy), hw_(hw) {
        CGAL_assertion(hw != RT(0));  // 确保不是未定义的点
    }
    
    // 齐次坐标访问器
    const RT& hx() const { return hx_; }
    const RT& hy() const { return hy_; }
    const RT& hw() const { return hw_; }
    
    // 笛卡尔坐标访问（需要除法）
    typename K::FT x() const { return typename K::FT(hx_, hw_); }
    typename K::FT y() const { return typename K::FT(hy_, hw_); }
    
    // 归一化：使 hw = 1
    void normalize() {
        if (hw_ != RT(1) && hw_ != RT(0)) {
            hx_ /= hw_;
            hy_ /= hw_;
            hw_ = RT(1);
        }
    }
};

类型擦除与几何对象表示

CGAL使用类型擦除技术实现几何对象的统一接口：

// 内核中的类型擦除机制
class Point_2 : public Type_equality_wrapper<
    typename Kernel_base::Point_2, 
    Point_2
> {
public:
    typedef typename Kernel_base::Point_2 Rep;
    
    // 转发构造函数
    Point_2() : Rep() {}
    Point_2(const FT& x, const FT& y) : Rep(x, y) {}
    
    // 坐标访问委托给具体实现
    FT x() const { return Rep::x(); }
    FT y() const { return Rep::y(); }
};

谓词与构造的特化

不同内核的谓词实现有所不同：

// 笛卡尔内核的方向谓词（2D）
template < typename K >
class Cartesian_orientation_2 {
    typedef typename K::Point_2 Point_2;
    typedef typename K::FT FT;
    
public:
    typedef Orientation result_type;
    
    Orientation operator()(const Point_2& p, const Point_2& q, const Point_2& r) const {
        // 计算 (q-p) x (r-p) 的z分量
        FT dx1 = q.x() - p.x();
        FT dy1 = q.y() - p.y();
        FT dx2 = r.x() - p.x();
        FT dy2 = r.y() - p.y();
        
        FT det = dx1 * dy2 - dx2 * dy1;
        
        if (det > FT(0)) return LEFT_TURN;
        if (det < FT(0)) return RIGHT_TURN;
        return COLLINEAR;
    }
};
 
// 齐次内核的方向谓词（2D）
template < typename K >
class Homogeneous_orientation_2 {
    typedef typename K::Point_2 Point_2;
    typedef typename K::RT RT;
    
public:
    typedef Orientation result_type;
    
    Orientation operator()(const Point_2& p, const Point_2& q, const Point_2& r) const {
        // 使用齐次坐标避免除法
        // det = | q.hx()*p.hw()-p.hx()*q.hw()  q.hy()*p.hw()-p.hy()*q.hw() |
        //       | r.hx()*p.hw()-p.hx()*r.hw()  r.hy()*p.hw()-p.hy()*r.hw() |
        
        RT phw = p.hw();
        RT qhx = q.hx() * phw - p.hx() * q.hw();
        RT qhy = q.hy() * phw - p.hy() * q.hw();
        RT rhx = r.hx() * phw - p.hx() * r.hw();
        RT rhy = r.hy() * phw - p.hy() * r.hw();
        
        RT det = qhx * rhy - rhx * qhy;
        
        if (det > RT(0)) return LEFT_TURN;
        if (det < RT(0)) return RIGHT_TURN;
        return COLLINEAR;
    }
};

使用示例

示例1：笛卡尔内核的基本使用

#include <CGAL/Cartesian.h>
#include <CGAL/MP_Float.h>
#include <iostream>
 
// 使用笛卡尔内核与多精度浮点数
typedef CGAL::Cartesian<CGAL::MP_Float> Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Vector_2 Vector_2;
typedef Kernel::Line_2 Line_2;
 
int main() {
    // 创建点
    Point_2 p1(0.0, 0.0);
    Point_2 p2(1.0, 0.0);
    Point_2 p3(0.5, 0.5);
    
    // 创建向量
    Vector_2 v = p2 - p1;
    std::cout << "Vector: (" << v.x() << ", " << v.y() << ")" << std::endl;
    
    // 创建直线
    Line_2 line(p1, p2);
    std::cout << "Line: " << line << std::endl;
    
    // 方向测试
    auto orientation = CGAL::orientation(p1, p2, p3);
    std::cout << "Orientation: " << orientation << std::endl;
    
    return 0;
}

示例2：齐次内核与精确计算

#include <CGAL/Homogeneous.h>
#include <CGAL/Gmpz.h>
#include <iostream>
 
// 使用齐次内核与GMP整数
typedef CGAL::Homogeneous<CGAL::Gmpz> Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Point_3 Point_3;
 
int main() {
    // 使用齐次坐标创建点（自动归一化）
    Point_2 p1(2, 4, 2);  // 等价于 (1, 2)
    Point_2 p2(3, 6, 3);  // 等价于 (1, 2)
    
    std::cout << "p1: (" << p1.x() << ", " << p1.y() << ")" << std::endl;
    std::cout << "p2: (" << p2.x() << ", " << p2.y() << ")" << std::endl;
    
    // 验证等价性
    if (p1 == p2) {
        std::cout << "Points are equal (as expected)" << std::endl;
    }
    
    // 3D点示例
    Point_3 q1(1, 2, 3, 1);   // 有限点 (1, 2, 3)
    Point_3 q2(1, 1, 1, 0);   // 无穷远点（方向向量）
    
    std::cout << "q1 is at infinity: " << q1.is_at_infinity() << std::endl;
    std::cout << "q2 is at infinity: " << q2.is_at_infinity() << std::endl;
    
    return 0;
}

示例3：内核选择与性能比较

#include <CGAL/Cartesian.h>
#include <CGAL/Homogeneous.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Timer.h>
#include <vector>
 
// 不同内核类型定义
typedef CGAL::Exact_predicates_inexact_constructions_kernel EPICK;
typedef CGAL::Exact_predicates_exact_constructions_kernel EPECK;
typedef CGAL::Cartesian<double> Cartesian_double;
typedef CGAL::Homogeneous<CGAL::Gmpz> Homogeneous_gmpz;
 
template <typename Kernel>
void benchmark_orientation(const std::vector<typename Kernel::Point_2>& points) {
    CGAL::Timer timer;
    timer.start();
    
    int left_turns = 0, right_turns = 0, collinear = 0;
    for (size_t i = 0; i < points.size() - 2; ++i) {
        auto o = CGAL::orientation(points[i], points[i+1], points[i+2]);
        if (o == CGAL::LEFT_TURN) left_turns++;
        else if (o == CGAL::RIGHT_TURN) right_turns++;
        else collinear++;
    }
    
    timer.stop();
    std::cout << "Kernel: " << typeid(Kernel).name() << std::endl;
    std::cout << "  Time: " << timer.time() << " seconds" << std::endl;
    std::cout << "  Left turns: " << left_turns << std::endl;
    std::cout << "  Right turns: " << right_turns << std::endl;
    std::cout << "  Collinear: " << collinear << std::endl;
}
 
int main() {
    const int N = 10000;
    
    // 为不同内核生成测试数据
    std::vector<EPICK::Point_2> points_epick;
    std::vector<EPECK::Point_2> points_epeck;
    
    for (int i = 0; i < N; ++i) {
        double x = rand() / (double)RAND_MAX;
        double y = rand() / (double)RAND_MAX;
        points_epick.emplace_back(x, y);
        points_epeck.emplace_back(x, y);
    }
    
    benchmark_orientation<EPICK>(points_epick);
    benchmark_orientation<EPECK>(points_epeck);
    
    return 0;
}

示例4：自定义数类型与内核

#include <CGAL/Cartesian.h>
#include <iostream>
 
// 自定义简单数类型（仅用于演示）
class MyNumber {
    double value;
public:
    MyNumber(double v = 0) : value(v) {}
    double get() const { return value; }
    
    // 必要的算术运算符
    MyNumber operator+(const MyNumber& other) const { return MyNumber(value + other.value); }
    MyNumber operator-(const MyNumber& other) const { return MyNumber(value - other.value); }
    MyNumber operator*(const MyNumber& other) const { return MyNumber(value * other.value); }
    MyNumber operator/(const MyNumber& other) const { return MyNumber(value / other.value); }
    
    bool operator<(const MyNumber& other) const { return value < other.value; }
    bool operator>(const MyNumber& other) const { return value > other.value; }
    bool operator==(const MyNumber& other) const { return value == other.value; }
    bool operator!=(const MyNumber& other) const { return value != other.value; }
};
 
// 特化代数结构特征
namespace CGAL {
template <>
struct Algebraic_structure_traits<MyNumber> {
    typedef MyNumber Type;
    typedef Tag_false Is_exact;
    typedef Tag_true Is_numerical_sensitive;
    typedef Field_with_sqrt_tag Algebraic_category;
};
} // namespace CGAL
 
typedef CGAL::Cartesian<MyNumber> MyKernel;
typedef MyKernel::Point_2 Point_2;
 
int main() {
    Point_2 p(MyNumber(1.0), MyNumber(2.0));
    Point_2 q(MyNumber(3.0), MyNumber(4.0));
    
    auto mid = CGAL::midpoint(p, q);
    std::cout << "Midpoint: (" << mid.x().get() << ", " << mid.y().get() << ")" << std::endl;
    
    return 0;
}

复杂度分析

存储复杂度

几何对象	Cartesian_kernel	Homogeneous_kernel
Point_2	2 × sizeof(FT)	3 × sizeof(RT)
Point_3	3 × sizeof(FT)	4 × sizeof(RT)
Vector_2	2 × sizeof(FT)	3 × sizeof(RT)
Vector_3	3 × sizeof(FT)	4 × sizeof(RT)

分析：

笛卡尔内核存储更紧凑（少一个坐标分量）
当 sizeof(FT) ≈ sizeof(RT) 时，笛卡尔内核节省约 25-33% 内存

时间复杂度

操作	Cartesian	Homogeneous	说明
点构造	O(1)	O(1)	直接赋值
坐标访问	O(1)	O(1)	直接返回引用
笛卡尔坐标计算	-	O(1)*	齐次需要除法（*仅当需要时）
方向测试(2D)	O(M)	O(M)	M为数运算成本
点比较	O(M)	O(M)	可能需要归一化

关键观察：

齐次内核的延迟归一化：齐次坐标避免频繁的除法运算，仅在需要笛卡尔坐标时才进行转换
精确计算场景：当使用GMP等精确数类型时，齐次内核的整数运算通常比笛卡尔内核的浮点运算更快且更精确
内存访问模式：笛卡尔内核的数据更紧凑，可能有更好的缓存局部性

选择建议

场景	推荐内核	理由
浮点近似计算	Cartesian	内存效率高，计算直接
精确有理计算	Homogeneous	避免浮点误差，整数运算更快
需要投影几何	Homogeneous	自然处理无穷远点
混合使用	Filtered_kernel	结合两者优势

关键文件位置

文件路径	说明
`CGAL/Cartesian.h`	笛卡尔内核主头文件
`CGAL/Cartesian/Cartesian_base.h`	笛卡尔内核基础定义
`CGAL/Cartesian/function_objects.h`	笛卡尔谓词与构造
`CGAL/Homogeneous.h`	齐次内核主头文件
`CGAL/Homogeneous/Homogeneous_base.h`	齐次内核基础定义
`CGAL/Homogeneous/function_objects.h`	齐次谓词与构造
`CGAL/Kernel/function_objects.h`	通用谓词定义
`CGAL/Kernel/Type_equality_wrapper.h`	类型擦除机制

Chunibyo

Explorer

2.1 笛卡尔与齐次坐标系统

2.1 笛卡尔与齐次坐标系统

理论基础

坐标表示的数学原理

笛卡尔坐标

齐次坐标

坐标转换

架构分析

内核类层次结构

Cartesian_kernel 实现

Homogeneous_kernel 实现

关键区别

实现细节

笛卡尔点的实现

齐次点的实现

类型擦除与几何对象表示

谓词与构造的特化

使用示例

示例1：笛卡尔内核的基本使用

示例2：齐次内核与精确计算

示例3：内核选择与性能比较

示例4：自定义数类型与内核

复杂度分析

存储复杂度

时间复杂度

选择建议

关键文件位置

Graph View

Table of Contents

Backlinks

Chunibyo

Explorer

2.1 笛卡尔与齐次坐标系统

2.1 笛卡尔与齐次坐标系统 §

理论基础 §

坐标表示的数学原理 §

笛卡尔坐标 §

齐次坐标 §

坐标转换 §

架构分析 §

内核类层次结构 §

Cartesian_kernel 实现 §

Homogeneous_kernel 实现 §

关键区别 §

实现细节 §

笛卡尔点的实现 §

齐次点的实现 §

类型擦除与几何对象表示 §

谓词与构造的特化 §

使用示例 §

示例1：笛卡尔内核的基本使用 §

示例2：齐次内核与精确计算 §

示例3：内核选择与性能比较 §

示例4：自定义数类型与内核 §

复杂度分析 §

存储复杂度 §

时间复杂度 §

选择建议 §

关键文件位置 §

Graph View

Table of Contents

Backlinks

2.1 笛卡尔与齐次坐标系统

理论基础

坐标表示的数学原理

笛卡尔坐标

齐次坐标

坐标转换

架构分析

内核类层次结构

Cartesian_kernel 实现

Homogeneous_kernel 实现

关键区别

实现细节

笛卡尔点的实现

齐次点的实现

类型擦除与几何对象表示

谓词与构造的特化

使用示例

示例1：笛卡尔内核的基本使用

示例2：齐次内核与精确计算

示例3：内核选择与性能比较

示例4：自定义数类型与内核

复杂度分析

存储复杂度

时间复杂度

选择建议

关键文件位置