简单例子code

CGAL有神秘的面纱，让我不断想看清其真面目。开始吧！

 

1 Three Points and One Segment
第一个例子是创建3个点和一条线段，并且在其上进行一些操作。

所有的CGAL头文件都在CGAL目录下。所有的CGAL类和函数都在CGAL的命名空间。类以大写字母开头，常量全大写，全局函数名小写。对象的空间维度由后缀给出。

几何元，如点，在一个kernel中定义。第一个例子中我们选择的kernel采用double精度的浮点数作为笛卡尔空间坐标。

另外，我们有predicate（断言），如位置测试断言，我们有construction（构建），如距离和中点的计算，都是construction。一个predicate的结果是一个离散集，一个construction产生一个值，也可能产生一个新的几何实体。

File Kernel_23/points_and_segment.cpp

#include <iostream>
#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);
 
std::cout << "p = " << p << std::endl;
std::cout << "q = " << q.x() << " " << q.y() << std::endl;
 
std::cout << "sqdist(p,q) = "
<< CGAL::squared_distance(p,q) << std::endl;
 
Segment_2 s(p,q);
Point_2 m(5, 9);
 
std::cout << "m = " << m << std::endl;
std::cout << "sqdist(Segment_2(p,q), m) = "
<< CGAL::squared_distance(s,m) << std::endl;
 
std::cout << "p, q, and m ";
switch (CGAL::orientation(p,q,m)){
case CGAL::COLLINEAR:
std::cout << "are collinear\n";
break;
case CGAL::LEFT_TURN:
std::cout << "make a left turn\n";
break;
case CGAL::RIGHT_TURN:
std::cout << "make a right turn\n";
break;
}
 
std::cout << " midpoint(p,q) = " << CGAL::midpoint(p,q) << std::endl;
return 0;
}
 
下面采用浮点数进行的几何运行让我们吃惊。
File Kernel_23/surprising.cpp

#include <iostream>
#include <CGAL/Simple_cartesian.h>
 
typedef CGAL::Simple_cartesian<double> Kernel;
typedef Kernel::Point_2 Point_2;
 
int main()
{
{
Point_2 p(0, 0.3), q(1, 0.6), r(2, 0.9);
std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
}
{
Point_2 p(0, 1.0/3.0), q(1, 2.0/3.0), r(2, 1);
std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
}
{
Point_2 p(0,0), q(1, 1), r(2, 2);
std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
}
return 0;
}
如果只从代码上看，我们会发现前两种情况也应当是共线的，但实际的结果是：

not collinear
not collinear
collinear
因为分数作为双精度数是不可被描述的，共线测试内部的计算是一个3X3行列式（determinant），它可以得到近似值，但不能得到误差为0的精确值。所以得出前两种情况为不花线的结论。
其他的predicate也会有同样的问题，如CGAL::orientation(p,q,m)运算可能会由于舍入误差，可能得出不同实际的结论。
如果你需要使数被全精度解析，你可以使用精确断言和精确构建的CGAL kernel。 
File Kernel_23/exact.cpp

#include <iostream>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <sstream>
 
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
 
int main()
{
Point_2 p(0, 0.3), q, r(2, 0.9);
{
q = Point_2(1, 0.6);
std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
}
 
{
std::istringstream input("0 0.3 1 0.6 2 0.9");
input >> p >> q >> r;
std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
}
 
{
q = CGAL::midpoint(p,r);
std::cout << (CGAL::collinear(p,q,r) ? "collinear\n" : "not collinear\n");
}
 
return 0;
}
这里的结果仍然让我们吃惊：

not collinear
collinear
collinear
第一个结果仍然是错的，原因与前面相同，它们仍然是浮点运算。第二个结果不同，它由字符串生成（construct），则精确地代表了字符串所表示的数。第三个结果通过构建（construct)中点得到第三个点，构建操作是精确的，所以结果也是正确的。

在很多情况下，你操作“精确”浮点数据，认为它们是由应用计算得到或由传感器得到的。它们不是象“0.1”这样的字符串，也不是象"1.0/10.0"这样动态（ on the fly）生成的，它是一个全精度的浮点数。如果它们只是被传递入某个算法并且没有构建（construct）操作时，你可以使用支持精确断言（predicate）和非精确构建（construct）的kernel。这样的例子包括下一节我们看到的“凸包”算法。它的输出是输入的一个子集，这个算法只进行坐标比较和位置测试。

由于高精度的计算需要消耗比普通计算多的资源，内存、时间等，所以使用时需要考虑。

大部分CGAL包说明它们需要或支持哪种kernel。

2 The Convex Hull of a Sequence of Points
 本节所有例子都是凸包算法。输入一个点序列，输出所有凸包边界上的点序列。

下面的例子输入和输出的都是一个坐标数组。

File Convex_hull_2/array_convex_hull_2.cpp

#include <iostream>
#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;
for(int i = 0; i < ptr - result; i++){
std::cout << result[i] << std::endl;
}
return 0;
}
如同上节所说，我们采用了精确断言和非精确构建的kernel来生成程序。
下面的例子则采用了标准库中的vector类来进行输入和输出。
File Convex_hull_2/vector_convex_hull_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/convex_hull_2.h>
 
#include <vector>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef std::vector<Point_2> Points;
 
int main()
{
Points points, result;
points.push_back(Point_2(0,0));
points.push_back(Point_2(10,0));
points.push_back(Point_2(10,10));
points.push_back(Point_2(6,5));
points.push_back(Point_2(4,1));
 
 
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;
}
3 About Kernels and Traits Classes
 本节简介traits的内涵和意义.

在上个例子中，如果我们阅读convex_hull_2()的手册时，会发现它及其他2D convex_hull_2()算法都有两个版本。其中一个版本包含了traits参数。

template<class InputIterator , class OutputIterator , class Traits >
OutputIterator
convex_hull_2(InputIterator first,
InputIterator beyond,
OutputIterator result,
const Traits & ch_traits)
什么原因要我们使用traits呢？泛型编程需要使用抽象元语对算法进行抽象，而在实现中将元语变为实际的类型和算法。那么convex hull算法需要哪些元语（primitive）呢？最简单的"Graham/Andrew Scan"算法过程是：（1)将所有输入的点进行从左到右排序；（2）从左向右顺序加入，逐步形成convex hull。这个过程(ch_graham_andrew())需要的元语包括：

Traits::Point_2
Traits::Less_xy_2
Traits::Left_turn_2
Traits::Equal_2
可以看出，Left_turn_2负责位置测试，Less_xy_2用于点的排序（这些类型需要满足的要求在概论念ConvexHullTraits_2中进行详细说明）。

从泛型概念的要求出发，这些元语需要抽象形成模板，所以下面是新的算法形式：

template <class InputIterator, class OutputIterator, class Point_2, class Less_xy_2, class Left_turn_2, class Equal_2>
OutputIterator
ch_graham_andrew( InputIterator first,
InputIterator beyond,
OutputIterator result);
每一种类型必须对模板中的所有类型进行定义。可以看出，这个模板参数有一点复杂。
有两个问题需要我们回答：（1）哪些类型需要进入模板参数列表？（2）我们为什么要用这些模板参数？
对第一个问题：ConvexHullTraits_2所要求的任何模型，这些模型由CGAL概念Kernel提供。
对第二个问题：如果我们将来需要计算投影到yz平面上的的3D点集的convex hull时，我们设计一个新的traits——Projection_traits_yz_3，这样前面的例子就不需要进行大的修改。
File Convex_hull_2/convex_hull_yz.cpp

#include <iostream>
#include <iterator>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Projection_traits_yz_3.h>
#include <CGAL/convex_hull_2.h>
 
typedef CGAL::Exact_predicates_inexact_constructions_kernel K3;
typedef CGAL::Projection_traits_yz_3<K3> K;
typedef K::Point_2 Point_2;
 
int main()
{
std::istream_iterator< Point_2 > input_begin( std::cin );
std::istream_iterator< Point_2 > input_end;
std::ostream_iterator< Point_2 > output( std::cout, "\n" );
CGAL::convex_hull_2( input_begin, input_end, output, K() );
return 0;
}
另一个例子是关于使用已经定义的空间点类型，或者来自非CGAL库中的点类型，将这些点类型及其相应的断言（predicates）加入类范围，然后你就可以基于新的点类型运行convex_hull_2。
最后，为什么需要将一个traits对象作为参数传入该方法呢？主要原因在于我们可以用一个更加一般的投影特征对象（projection trait）来保存状态。例子：如果这个投影平面是由一个向量给出的方向，而且是通过硬编码的方式加入Projection_traits_yz_3。
 
4 Concepts and Models
一个概念（concept）是一个类型的一个需求集（requirment set），它包括一些内嵌的类型，成员函数或一些处理该类型自由函数。

一个概念的模型（model of a concept）是一个用于实现概念所有需求的一个类。

下面有一个函数：

template <typename T>
T
duplicate(T t)
{
return t;
}
如果你用一个类C来实例化该函数，则C必须提供一个复制构造函数（copy constructor），我们称类C必须是“可复制构造的”（CopyConstructible）。

另一个例子：

template <typename T>
T& std::min(const T& a, const T& b)
{
return (a<b)?a:b;
}
这个函数只有在类型T的operator<(..)有定义时才能编译。我们称类C必须是“小于关系可比较的”（LessThanComparable）

关于自由函数的一个例子：CGAL包和Boost Graph库中的HalfedgeListGraph概念。如果一个类G要成为HalfedgeListGraph的一个模型，必须有一个全局函数halfedges(const G&)处理该类。

关于带有traits需求的概念的一个例子是InputIterator。对于一个InputIterator的模型，一个特化的std::iterator_traits类必须存在（或其通用的模板必须可用）。

5 Further Reading
阅读：

 "The C++ Standard Library, A Tutorial and Reference" by Nicolai M. Josuttis from Addison-Wesley, or "Generic Programming and the STL" by Matthew H. Austern for the STL and its notion of concepts and models.

Other resources for CGAL are the rest of the tutorials and the user support page at https://www.cgal.org/.

// gmptest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "gmp.h"
#pragma comment(lib,"libgmp-10.lib")

#include <iostream>
#include "CGAL/Simple_cartesian.h"

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

int _tmain(int argc, _TCHAR* argv[])
{
	//return 0;
	mpz_t t; //mpz_t 为GMP内置大数类型
	mpz_init(t); //大数t使用前要进行初始化，以便动态分配空间
	mpz_ui_pow_ui(t, 2, 100); //GMP所有函数基本都是以mpz打头
	gmp_printf("2^100=%Zd\n", t); //输出大数，大数的格式化标志为%Zd
	mpz_clear(t);
	scanf_s("%s");


	Point_2 p(1,1), q(10,10);

	std::cout << "p = " << p << std::endl;
	std::cout << "q = " << q.x() << " " << q.y() << std::endl;

	std::cout << "sqdist(p,q) = "<< CGAL::squared_distance(p,q) << std::endl;

	Segment_2 s(p,q);


	return 0;
}

最近在新的 Windows 系统下使用 CMake+Boost，不慎踩了好多坑，浪费不少时间。备忘如下：

前文曾经介绍过，安装使用 Boost 本来是很简单的，只要执行booststrap.bat和b2.exe即可。注意：一定要仔细看二者的执行结果，b2.exe好像依赖 python，如果没有安装 python，这个编译会报错。python 安装完成后要把python.exe的路径添加到环境变量PATH中。

编译 Boost
编译参数形式如下：

1
b2.exe --build-dir=build --stagedir=./stage/x64 --build-type=complete address-model=64 threading=multi --toolset=msvc-14.0 runtime-link=static -j 12
参数	说明
variant=debug/release	编译版本类型，debug 版文件名有_d，release 版没有，生成_d 也必然使用 debug 版的 C++ 运行时库，因此_gd 是同时出现的
link=static/shared	编译为静态库还是动态库，生成.lib 还是.dll，对应文件中的 BOOST_LIB_PREFIX
threading=single/multi	使用单线程还是多线程 CRT，多线程版文件名有_mt，单线程版没有。对应文件中的 BOOST_LIB_THREAD_OPT
runtime-link=static/shared	静态还是动态链接 CRT，静态链接文件名有_s，对应文件中的 BOOST_LIB_THREAD_OPT
address-model=32/64	32 位或 64 位编译
—toolset	C++ 编译器
—build-dir=[builddir]	存放编译的临时文件
—stagedir=[stagedir]	存放编译后的库文件，默认是 stage
—build-type=complete	编译所有版本，否则只编译一小部分版本（相当于:variant=release, threading=multi;link=shared/static;runtime-link=shared）
—with-[library]	只编译指定的库，如输入—with-regex 就只编译 regex 库了。
—show-libraries	显示需要编译的库名称
生成文件的命名规则
以libboost_regex-vc71-mt-d-1_34.lib为例：

lib 前缀：除了 Microsoft Windows 之外，每一个 Boost 库的名字都以此字符串开始。在 Windows 上，只有普通的静态库使用 lib 前缀；导入库和 DLL 不使用。
boost_regex 库名称：所有 boost 库名文件以 boost_开头。
-vc71 Toolset 标记：标识了构建该库所用的 toolset 和版本。
-mt Threading 标记：标识构建该库启用了多线程支持。不支持多线程的库没有-mt。
-d ABI 标记：对于每一种特性，向标记中添加一个字母：
标记	含义
s	静态链接 CRT
g	使用调试版本的 CRT
d	构建调试版本的 Boost
y	使用 Python 的特殊调试构建
p	使用 STLPort 标准库而不是编译器提供的默认库
n	使用 STLPort 已被弃用的 “native iostreams”
-1_34
版本标记：完整的 Boost 发布号，下划线代替点。例如，1.31.1 版本将被标记为 “-1_31_1”。
.lib
扩展名：取决于操作系统。在大多数 unix 平台上，.a 是静态库，.so 是共享库。在 Windows 上，.dll 表示共享库，.lib 是静态或导入库。
可见，32 位或 64 位信息并不体现在文件命名中，因此需要分目录存放。通常在生成库文件时，要执行如下两条命令：

1
2
b2.exe --build-dir=build --stagedir=./stage/x64 --build-type=complete address-model=64 threading=multi --toolset=msvc-14.0 runtime-link=static -j 12
b2.exe --build-dir=build --stagedir=./stage/win32 --build-type=complete address-model=32 threading=multi --toolset=msvc-14.0 runtime-link=static -j 12
使用 Boost
使用 32/64 位版本
可以在 CMake 中加入如下判断并设置Boost_LIBRARY_DIR：

1
2
3
4
5
6
7
8
9
10
11

if(CMAKE_SIZEOF_VOID_P EQUAL 8)
  set(Boost_LIBRARY_DIR "$ENV{BOOST_ROOT}\stage\x64\lib")
elseif(CMAKE_SIZEOF_VOID_P EQUAL 4)
  set(Boost_LIBRARY_DIR "$ENV{BOOST_ROOT}\stage\win32\lib")
endif()

set(Boost_USE_STATIC_LIBS ON)
find_package(Boost COMPONENTS program_options log REQUIRED)

message(STATUS "Boost_LIBRARIES:${Boost_LIBRARIES}")
执行
cmake -G "Visual Studio 14 Win64" ..
输出Boost_LIBRARIES为：

1
-- Boost_LIBRARIES:.../stage/x64/lib/libboost_xxx-mt-s-1_62.lib;...
执行
cmake -G "Visual Studio 14" ..
输出Boost_LIBRARIES为：

1
-- Boost_LIBRARIES:.../stage/Win32/lib/libboost_xxx-mt-s-1_62.lib;...
多线程、CRT 开关
使用 Boost 时，在 CMake 中有相应的选项对应不同的 Boost 生成库：

选项	说明
Boost_USE_MULTITHREADED	使用与单线程/多线程链接 CRT 的 Boost（_mt），默认 ON
Boost_USE_STATIC_LIBS	使用 Boost 的静态/动态库，默认 OFF
Boost_USE_STATIC_RUNTIME	使用静态/动态链接 CRT 的 Boost（_s），默认值依赖平台
Boost_USE_DEBUG_RUNTIME	使用链接了 debug/release 版 CRT 的 Boost（_g)，默认为 ON
但我发现这几个开关实际上并不是平行的各管各的，比如：

1
2
3
4
5
6
7
8
9

set(Boost_USE_STATIC_LIBS ON)
set(Boost_USE_STATIC_RUNTIME ON)
set(Boost_USE_DEBUG_RUNTIME ON)
set(Boost_USE_MULTITHREADED ON)

find_package(Boost COMPONENTS log REQUIRED)

message(STATUS "Boost_LIBRARIES:${Boost_LIBRARIES}")
执行
cmake -G "Visual Studio 14" ..

Boost_USE_STATIC_LIBS=ON ，输出的Boost_LIBRARIES为：

1
...libboost_xxx-mt-s-1_62.lib;...
Boost_USE_STATIC_RUNTIME=ON ，Boost_LIBRARIES为：

1
2
optimized;...libboost_xxx-mt-s-1_62.lib;
debug;...libboost_xxx-mt-sgd-1_62.lib;
此时如果Boost_USE_DEBUG_RUNTIME=OFF则不生成 sgd 版本。
如果Boost_USE_STATIC_RUNTIME=OFF，开关Boost_USE_DEBUG_RUNTIME将不起作用，Boost_LIBRARIES总是为：

1
optimized;...libboost_xxx-mt-s-1_62.lib;
所以一般静态链接 Boost 时，使用如下两行即可满足 Debug 和 Release 版本的链接：

1
2
set(Boost_USE_STATIC_LIBS ON)
set(Boost_USE_STATIC_RUNTIME ON)
Release 版使用：

编译 Boost 使用的 VS 要和 CMake 编译工程使用的 VS 版本一致
来boost_1_62_0stagelib下，可以看到编译出来的 lib 文件名是包含 VC 版本号的，如：
libboost_atomic-vc140-mt-1_62.lib。
vc140对应 Visual Studio 2015，如果此时 CMake 编译 project 的 Visual Studio 版本不是 2015，而又依赖了 Boost：

1
2
set(Boost_USE_STATIC_LIBS ON) 
find_package(Boost COMPONENTS program_options log REQUIRED)
这会导致 CMake 能找到 Boost，却找不到需要的program_options和log组件，这是因为 CMake 要找与指定 Visual Studio 版本对应的 libboost 库文件。报出的错是找不到指定的 Boost 版本，其实跟 Boost 版本无关，跟编译它使用的 VS 版本有关。

环境变量 BOOST_ROOT
如果指定环境变量，BOOST_ROOT 的值为 boost 所在的上一级目录，比如我的目录如下：

1
2
3
4
5
6
7
8
9
10
c:boost_1_62_0   <-- BOOST_ROOT指向这里
    ├─bin.v2
    ├─boost
    ├─doc
    ├─libs
    ├─more
    ├─stage
    ├─status
    ├─tools
    └─...
环境变量应设为：BOOST_ROOT=c:boost_1_62_0。

我尝试不写这个环境变量，发现 CMake 依然能找到 Boost，那就不要写了吧~