CGAL教程：从Hello World开始学习计算几何基础

前言

计算几何算法库(CGAL)是一个强大的C++库，提供了丰富的几何算法实现。本文将通过"Hello World"式的入门教程，带领读者了解CGAL的基本概念和使用方法。

基本几何元素操作

点与线段的基本操作

在CGAL中，所有头文件都位于include/CGAL目录下，所有类和函数都在CGAL命名空间中。CGAL的命名规范是：类名首字母大写，全局函数小写，常量全大写。

让我们从一个简单的例子开始，展示如何创建点和线段，并对它们进行基本操作：

#include <CGAL/Simple_cartesian.h>

typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;

int main()
{
    Point_2 p(1,1), q(10,10);
    Segment_2 s(p,q);
    
    // 计算两点间距离
    double distance = CGAL::sqrt(CGAL::squared_distance(p,q));
    
    // 计算中点
    Point_2 mid = CGAL::midpoint(p,q);
    
    return 0;
}

浮点数精度问题

使用浮点数进行几何计算可能会带来一些意想不到的结果。考虑以下测试三点共线性的例子：

Point_2 a(0,0), b(1,1), c(2,2);
if(CGAL::collinear(a,b,c)) {
    std::cout << "collinear" << std::endl;
} else {
    std::cout << "not collinear" << std::endl;
}

理论上这三个点应该在一条直线上，但由于浮点数精度限制，实际输出可能是"not collinear"。

精确计算解决方案

对于需要精确计算的场景，CGAL提供了精确计算内核：

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel ExactKernel;
typedef ExactKernel::Point_2 EPoint_2;

int main()
{
    EPoint_2 ea(0,0), eb(1,1), ec(2,2);
    if(CGAL::collinear(ea,eb,ec)) {
        std::cout << "collinear" << std::endl;
    } else {
        std::cout << "not collinear" << std::endl;
    }
    return 0;
}

凸包计算实例

数组中的点集凸包

计算凸包是计算几何中的经典问题。CGAL提供了简单易用的凸包计算函数：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;

int main()
{
    Point_2 points[5] = { Point_2(0,0), Point_2(10,0), 
                         Point_2(10,10), Point_2(6,5), 
                         Point_2(4,1) };
    Point_2 result[5];
    
    Point_2 *ptr = CGAL::convex_hull_2(points, points+5, result);
    std::cout << ptr - result << " points on the convex hull" << std::endl;
    
    return 0;
}

使用STL容器

更现代的方式是使用STL容器如vector：

#include <vector>
#include <algorithm>
#include <CGAL/convex_hull_2.h>

int main()
{
    std::vector<Point_2> points, result;
    points.push_back(Point_2(0,0));
    points.push_back(Point_2(10,0));
    // 添加更多点...
    
    CGAL::convex_hull_2(points.begin(), points.end(), 
                       std::back_inserter(result));
    
    std::cout << result.size() << " points on the convex hull" << std::endl;
    
    return 0;
}

内核与特征类

理解Traits类

CGAL算法通常通过Traits类来抽象几何操作。例如，凸包算法需要知道如何比较点、如何测试方向等。这些操作被封装在Traits类中。

自定义投影平面

我们可以计算3D点在yz平面投影后的凸包：

#include <CGAL/Projection_traits_yz_3.h>

typedef CGAL::Projection_traits_yz_3<K> YZTraits;
typedef YZTraits::Point_2 YZPoint_2;

int main()
{
    std::vector<YZPoint_2> points;
    // 添加3D点(会自动投影到yz平面)
    points.push_back(YZPoint_2(0,1,2));
    points.push_back(YZPoint_2(0,2,4));
    // ...
    
    std::vector<YZPoint_2> result;
    CGAL::convex_hull_2(points.begin(), points.end(), 
                       std::back_inserter(result), YZTraits());
    
    return 0;
}

概念与模型

在CGAL中，概念(Concept)定义了一组类型必须满足的要求，而模型(Model)则是满足这些要求的具体实现。

例如，InputIterator概念要求类型必须支持解引用和递增操作。STL中的vector::iterator就是InputIterator的一个模型。

总结

本文介绍了CGAL的基本使用方法，包括：

1. 基本几何元素的操作
2. 浮点数精度问题及解决方案
3. 凸包计算的实际应用
4. Traits类的设计理念
5. CGAL中的概念与模型

这些基础知识将帮助读者更好地理解和使用CGAL进行更复杂的几何计算。