CGAL计算几何库英文手册

需积分: 9 164 浏览量更新于2024-07-18 收藏 296KB PDF 举报

"CGAL英文手册，是计算几何算法库CGAL的官方文档，适用于Release 2.1，发布于1999年12月。该文档由包括荷兰乌得勒支大学、瑞士苏黎世联邦理工学院、德国柏林自由大学、法国尼斯-索菲亚安提波利斯的INRIA、德国哈勒-维腾贝格马丁-路德大学、德国萨尔布吕肯的马克斯-普朗克计算机科学研究所、奥地利林茨的RISC和以色列特拉维夫大学在内的七家机构合作开发。更多关于CGAL项目的信息可以在其官方网站http://www.cs.uu.nl/CGAL/上找到。此文档包含了一系列示例源代码，可在CGAL分发包的examples/Gettingstarted目录下找到。文档作者是来自荷兰乌得勒支大学计算机科学系的Geert-Jan Giezeman、Remco Veltkamp和Wieger Wesselink。该工作得到了Esprit IV项目No.21957 (CGAL)和Esprit IV项目No.28155 (GALIA)的支持。正文： CGAL（Computational Geometry Algorithms Library）是一个用C++编写的计算几何算法库，提供了广泛的几何数据结构和算法，用于处理点、线、面等几何对象。这个库是面向对象设计的，易于理解和使用，并且遵循C++标准模板库（STL）的原则，使得它能与现代C++编程环境很好地集成。 1.1 Overview of CGAL: CGAL涵盖了以下主要领域： - 几何基础：定义了基本的几何类型，如点、向量、线段、多边形等，并提供了相关的操作和比较函数。 - 几何构造：包括构造几何对象、计算交点、求距离等操作。 - 几何处理：提供如凸包计算、三角剖分、最近点查找、Delaunay三角网生成等功能。 - 多边形和网格操作：支持多边形的操作，如剪切、合并和布尔运算，以及网格的生成和分析。 - 三维几何：扩展到3D空间，包括3D多边形网格、表面建模和体积计算等。 - 计算几何算法：如欧几里得最短路径、平面扫描算法、细分算法等。 CGAL的设计理念是模块化，这意味着用户可以根据需要选择和组合不同的组件。例如，你可以使用CGAL中的数据结构（如kd树或半空间结构）来优化空间搜索，或者利用它的几何算法（如快速最近点查询算法）来提高应用程序的性能。文档中提到的示例源代码是学习和理解CGAL库功能的重要资源。这些示例展示了如何在实际项目中应用CGAL，涵盖了从简单的数据结构初始化到复杂算法的实现。通过阅读和运行这些示例，开发者可以快速掌握CGAL的基本用法和最佳实践。 CGAL广泛应用于图形学、计算机辅助设计（CAD）、地理信息系统（GIS）、机器人路径规划、图像处理等多个领域。由于其开源性质和强大的社区支持，CGAL成为了计算几何领域的首选工具之一。总结CGAL的关键知识点，主要包括： 1. CGAL是一个用C++编写的计算几何库，用于处理几何对象和算法。 2. 它包含了多种几何数据结构和算法，覆盖2D和3D空间。 3. 库设计模块化，允许用户按需选择组件。 4. 提供示例源代码帮助学习和理解。 5. 广泛应用于多个领域，有强大的社区支持。 CGAL的学习和使用需要对C++编程有一定基础，同时对几何概念和算法有一定的了解。对于初次接触CGAL的开发者，建议从文档的"Getting Started"部分开始，逐步了解并实践其提供的各种功能。

Chapter 2

Elementaries

2.1 Points and Vectors

Example ﬁle: examples/Getting started/basic.C

Points and vectors are about the most basic elements in geometry. The ”Hello, Geo” program of this document

shows some operations that can be done on them.

#include "tutorial.h"

#include <CGAL/Point_2.h>

#include <CGAL/Vector_2.h>

#include <iostream>

main()

{

Point p1(1.0, -1.0), p2(4.0, 3.0), p3;

Vector v1(-1, 10);

Vector v2(p2-p1);

v1=v1+v2;

p3 = p2 + v1*2;

std::cout << "Vector v2 has coordinates: ("

<< v2.x() <<", "<<v2.y() <<")\n";

std::cout << "Point p3 has coordinates: ("

<< p3.x() <<", "<<p3.y() <<")\n";

}

When we compile and run the program, the output is:

Vector v2 has coordinates: (3, 4)

Point p3 has coordinates: (8, 31)

Before we have a look at the operations on points and vectors, we consider the structure of the program. First

there are include ﬁles. The ﬁrst include ﬁle is

tutorial.h

. This header ﬁle contains some deﬁnitions that

make our example programs easier to read. In Section 3.2 we will show what it contains. Next we include

some header ﬁles that deﬁne the C

GAL points and vectors. As we want to do some output, we also include the

standard C

IO. The order of inclusion sometimes is important in CGAL. We always include

tutorial.h

the ﬁrst ﬁle. When we explain the contents of this ﬁle, we’ll explain why.

In line 8, three two-dimensional points are declared. The ﬁrst two are initialised with x and y values. The third

is not initialised. In the next two lines, two vectors are declared. The ﬁrst vector is initialised in the same way

as the points. The second vector is initialised with the difference of two points.

In lines 11 and 12 we see some operations on vectors and points. Two vectors can be added, and a new vector

results. A vector can be multiplied with a number. A vector can be added to a point, resulting in another point.

In lines 13 to 16 we print the coordinates of the computed vector and point to standard output. The x and y

coordinates are doubles.

2.1.1 The difference between points and vectors

Points and vectors seem to be very similar. They both have an x and y coordinate. In what way do they differ?

A point is a geometrical object. It has a position in the two dimensional space, or in a higher dimension, if we

have higher dimensional points. A point can lie on a line, or inside a triangle. It has a distance to another point

and to other geometric objects.

Vectors are not geometric objects in this sense. A vector can be thought of as the difference between two points.

Vectors can be added and subtracted. Every vector vec has an inverse −vec. Finally, vectors can be multiplied

by a number, which multiplies all coordinates.

The two concepts should be well separated. This is enforced by typing. Trying to add two points to each other

or taking the distance from a vector to a point will lead to compilation errors.

GAL also knows the concept of an origin. It can be used in cases where the concepts of vector and point

become mingled. In 2D, the origin is a point with coordinates (0,0). However, we use a separate type (Origin)

that has a single value: ORIGIN. This constant can be used to convert between vectors and points in an efﬁcient

way.

Remember that we can subtract two points from each other, in which case we get a vector, and can add a vector

to a point, resulting in a point. In the same way it is possible to subtract the origin from a point, resulting in a

vector with the same coordinates as the point, and we can add a vector to the origin, resulting in a point with the

same coordinates as the vector. The value ORIGIN can be used as the origin in all dimensions.

2.2 Predicates

As we have access to the coordinates, we can do anything with points what we could possibly want to do. But

usually we don’t want to work on such a low level. C

GAL provides predicates that work on a higher level.

2.2.1 Orientation of points

Example ﬁle: examples/Getting started/orientation.C

An important predicate is about the orientation of points. Three points may make a left or a right turn or they

may lie on a line. Figure 2.1 shows the possible orientations of three points, p1, p2 and p3.

In the following program the user is repeatedly prompted to give 3 points. The predicate is used to decode in

what orientation they are.

#include "tutorial.h"

#include <CGAL/Point_2.h>

#include <CGAL/predicates_on_points_2.h>

#include <iostream>

using std::cout;

using std::cin;

main()

{

剩余62页未读，继续阅读

棣莫弗

粉丝: 0
资源: 6

CGAL计算几何库英文手册

CGAL参考手册（CGAL_4.7 Hello World）

CGAL库的文档 说明

CGAL-5.0.2官方文档

cgal_4.4_manual.zip_CGAL 4_CGAL使用手册_cgal 手册_cgal手册_cgal用户手册

cgal学习手册

CGAL编程手册

CGAL开发者手册，英文版

CGAL开发者手册：英文技术文档

cgal学习手册 pdf

CGAL3.8手册 CGAL - Computational Geometry Algorithms Library （计算几何

最新资源

CGAL库的文档说明