Navigation: Up, Table of Contents, Bibliography, Index, Title Page

Chapter 3
Kernel Geometry

3.1   Points and Vectors

In CGAL, we strictly distinguish between points, vectors and directions. A point is a point in the Euclidean space d, a vector is the difference of two points p2, p1 and denotes the direction and the distance from p1 to p2 in the vector space d, and a direction is a vector where we forget about its length. They are different mathematical concepts. For example, they behave different under affine transformations and an addition of two points is meaningless in affine geometry. By putting them in different classes we not only get cleaner code, but also type checking by the compiler which avoids ambiguous expressions. Hence, it pays twice to make this distinction.

CGAL defines a symbolic constant ORIGIN of type Origin which denotes the point at the origin. This constant is used in the conversion between points and vectors. Subtracting it from a point p results in the locus vector of p. 

  Point_2< Cartesian<double> >  p(1.0, 1.0), q;
  Vector_2< Cartesian<double> >  v;
  v = p - ORIGIN;
  q = ORIGIN + v;  
  assert( p == q );

In order to obtain the point corresponding to a vector v you simply have to add v to ORIGIN. If you want to determine the point q in the middle between two points p1 and p2, you can write1 

  q = p_1 + (p_2 - p_1) / 2.0;

Note that these constructions do not involve any performance overhead for the conversion with the currently available representation classes.

3.2   Kernel Objects

Besides points (Point_2<Kernel>, Point_3<Kernel>, Point_d<Kernel>), vectors (Vector_2<Kernel>, Vector_3<Kernel>), and directions (Direction_2<Kernel>, Direction_3<Kernel>), CGAL provides lines, rays, segments, planes, triangles, tetrahedra, iso-rectangles, iso-cuboids, circles and spheres.

Lines (Line_2<Kernel>, Line_3<Kernel>) in CGAL are oriented. In two-dimensional space, they induce a partition of the plane into a positive side and a negative side. Any two points on a line induce an orientation of this line. A ray (Ray_2<Kernel>, Ray_3<Kernel>) is semi-infinite interval on a line, and this line is oriented from the finite endpoint of this interval towards any other point in this interval. A segment (Segment_2<Kernel>, Segment_3<Kernel>) is a bounded interval on a directed line, and the endpoints are ordered so that they induce the same direction as that of the line.

Planes are affine subspaces of dimension two in 3, passing through three points, or a point and a line, ray, or segment. CGAL provides a correspondence between any plane in the ambient space 3 and the embedding of 2 in that space. Just like lines, planes are oriented and partition space into a positive side and a negative side. In CGAL, there are no special classes for halfspaces. Halfspaces in 2D and 3D are supposed to be represented by oriented lines and planes, respectively.

Concerning polygons and polyhedra, the kernel provides triangles, iso-oriented rectangles, iso-oriented cuboids and tetrahedra. More complex polygons2 and polyhedra or polyhedral surfaces can be obtained from the basic library (Polygon_2, Polyhedron_3), so they are not part of the kernel. As with any Jordan curves, triangles, iso-oriented rectangles and circles separate the plane into two regions, one bounded and one unbounded.

3.3   Orientation and Relative Position

Geometric objects in CGAL have member functions that test the position of a point relative to the object. Full dimensional objects and their boundaries are represented by the same type, e.g. halfspaces and hyperplanes are not distinguished, neither are balls and spheres and discs and circles. Such objects split the ambient space into two full-dimensional parts, a bounded part and an unbounded part (e.g. circles), or two unbounded parts (e.g. hyperplanes). By default these objects are oriented, i.e., one of the resulting parts is called the positive side, the other one is called the negative side. Both of these may be unbounded.

For these objects there is a function oriented_side() that determines whether a test point is on the positive side, the negative side, or on the oriented boundary. These function returns a value of type Oriented_side.

Those objects that split the space in a bounded and an unbounded part, have a member function bounded_side() with return type Bounded_side.

If an object is lower dimensional, e.g. a triangle in three-dimensional space or a segment in two-dimensional space, there is only a test whether a point belongs to the object or not. This member function, which takes a point as an argument and returns a boolean value, is called has_on()

Footnotes

 1  you might call midpoint(p_1,p_2) instead
 2  Any sequence of points can be seen as a (not necessary simple) polygon or polyline. This view is used frequently in the basic library as well.

Next chapter: Predicates and Constructions
Navigation: Table of Contents, Bibliography, Index, Title Page
The CGAL Project . Tue, December 21, 2004 .