Package Overview

Introduction

Preliminaries

Finally, if you want to download and run any of the precompiled demos, here you can find the dlls that are shared by all of them. Note that on computer that does not have Visual C++ 2005 installed, you probably also need the Microsoft Visual C++ 2005 SP1 Redistributable Package (x86).

Algebraic Foundations

Number Types

Polynomial

Modular Arithmetic

Monotone and Sorted Matrix Search

Linear and Quadratic Programming Solver

The resulting solution is certified: along with the claims that the problem under consideration has an optimal solution, is infeasible, or is unbounded, the algorithms also deliver proofs for these facts. These proofs can easily (and independently from the algorithms) be checked for correctness.

The solution algorithms are based on a generalization of the simplex method to quadratic objective functions.

2D and 3D Linear Geometry Kernel

dD Geometry Kernel

2D Circular Geometry Kernel

3D Spherical Geometry Kernel

2D Convex Hulls and Extreme Points

3D Convex Hulls

dD Convex Hulls and Delaunay Triangulations

2D Polygon

This package provides a 2D polygon class and operations on sequences of points, like bounding box, extremal points, signed area, simplicity and convexity test, orientation, and point location.

The demo includes operations on polygons, such as computing a convex partition, and the straight skeleton.

2D Regularized Boolean Set-Operations

2D Boolean Operations on Nef Polygons

2D Boolean Operations on Nef Polygons Embedded on the Sphere

2D Polygon Partitioning

2D Straight Skeleton and Polygon Offsetting

2D Minkowski Sums

3D Polyhedral Surface

Halfedge Data Structures

3D Boolean Operations on Nef Polyhedra

Convex Decomposition of Polyhedra

3D Minkowski Sum of Polyhedra

2D Arrangement

Arrangements and arrangement components can also be extended to store additional data. An important extension stores the construction history of the arrangement, such that it is possible to obtain the originating curve of an arrangement subcurve.

2D Intersection of Curves

2D Snap Rounding

2D Envelopes

3D Envelopes

2D Triangulation

The package provides plain triangulation (whose faces depend on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams.

Finally, constrained and Delaunay constrained triangulations allows to force some constrained segments to appear as edges of the triangulation. Several versions of constrained and Delaunay constrained triangulations are provided: some of them handle intersections between input constraints segment while others do not.

2D Triangulation Data Structure

3D Triangulations

The package provides plain triangulation (whose faces depends on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams.

3D Triangulation Data Structure

3D Periodic Triangulations

The package provides Delaunay triangulations and offers nearest neighbor queries and primitives to build the dual Voronoi diagrams.

2D Alpha Shapes

3D Alpha Shapes

2D Segment Delaunay Graphs

2D Apollonius Graphs (Delaunay Graphs of Disks)

2D Voronoi Diagram Adaptor

2D Conforming Triangulations and Meshes

Conforming Delaunay triangulations are obtained from constrained Delaunay triangulations by refining constrained edges until they are Delaunay edges. Conforming Gabriel triangulations are obtained by further refining constrained edges until they become Gabriel edges.

The package provides also a 2D mesh generator that refines triangles and constrained edges until user defined size and shape criteria on triangles are satisfied. The package can handle intersecting input constraints and set no restriction on the angle formed by two constraints sharing an endpoint.

3D Surface Mesh Generation

Currently, implementations are provided for implicit surfaces described as the zero level set of some function and surfaces described as a gray level set in a three-dimensional image.

Surface Reconstruction from Point Sets

3D Skin Surface Meshing

The construction of a triangular mesh of a smooth skin surface is often necessary for further analysis and for fast visualization. This package provides functions to construct a triangular mesh approximating the skin surface from a set of balls and a shrink factor. It also contains code to subdivide the mesh efficiently.

3D Mesh Generation

3D Surface Subdivision Methods

Triangulated Surface Mesh Simplification

Planar Parameterization of Triangulated Surface Meshes

2D Placement of Streamlines

Approximation of Ridges and Umbilics on Triangulated Surface Meshes

Estimation of Local Differential Properties

Point Set Processing

2D Range and Neighbor Search

Interval Skip List

dD Spatial Searching

This package implements exact and approximate distance browsing by providing exact and approximate algorithms for range searching, k-nearest and k-furthest neighbor searching, as well as incremental nearest and incremental furthest neighbor searching, where the query items are points in dD Euclidean space.

dD Range and Segment Trees

Intersecting Sequences of dD Iso-oriented Boxes

AABB Tree

Spatial Sorting

Bounding Volumes

Inscribed Areas

Optimal Distances

Principal Component Analysis

2D and Surface Function Interpolation

Kinetic Data Structures

Kinetic Framework

STL Extensions for CGAL

CGAL and the Boost Graph Library

CGAL and Boost Property Maps

Handles and Circulators

Geometric Object Generators

Profiling tools, Hash Map, Union-find, Modifiers

IO Streams

Geomview

This package implements an interface to Geomview, an interactive 3D viewing program, originally developed at the Geometry Center in Minneapolis.

CGAL and the Qt Graphics View Framework

CGAL Ipelets