Chapter 3
Kernel Geometry

3.1   Points and Vectors

^d

^d

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.

  double coord[] = {1.0, 1.0, 1.0, 1.0};
  Point_d< Cartesian_d<double> >  p(4,coord,coord+4), q(4);
  Vector_d< Cartesian_d<double> >  v(4);
  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 $$p₁ and $$p₂, you can write¹

  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_d<R>), vectors (Vector_d<R>), and directions (Direction_d<R>), CGAL provides lines, rays, segments, hyperplanes, and spheres.

Lines (Line_d<R>) in CGAL are oriented. A ray (Ray_d<R>) is a 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_d<R>) 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.

Hyperplanes are affine subspaces of dimension $$d-1 in $$ ^d, passing through $$d points. Hyperplanes are oriented and partition space into a positive side and a negative side. In CGAL, there are no special classes for halfspaces. Halfspaces are supposed to be represented by oriented hyperplanes. All kernel objects are equality comparable via operator== and operator!=. For those oriented objects whose orientation can be reversed (segments, lines, hyperplanes, spheres) there is also a global function weak_equality that allows to test for point set equality disregarding the orientation.

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. Such objects split the ambient space into two full-dimensional parts, a bounded part and an unbounded part (e.g. spheres), 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 segment in $$d-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