CGAL 5.3  Manual

The layer of geometry kernels provides basic geometric entities of constant sizeIn dimension \( d\), an entity of size \( O(d)\) is considered to be of constant size. and primitive operations on them. Each entity is provided as both a standalone class, which is parameterized by a kernel class, and as a type in the kernel class. Each operation in the kernel is provided via a functor classA class which defines a member operator()
. in the kernel class and also as either a member function or a global function. See [7] for more details about this design. Ideally, if the kernel provides all the primitives required, you can use any kernel as a traits class directly with your algorithm or data structure; see also Chapter Traits Classes . If you need primitives not provided by the kernel (yet), please read Section Missing functionality below.
CGAL provides different kernels, they can differ by internal representation of objects (e.g. cartesian versus homogeneous) or provide different functionalities (e.g. circular kernel). When creating a new package, the authors have to specify clearly the requirements needed by the kernel used. For example they can specify the needs with respect to the arithmetic.
The authors may specify a targeted kernel in the list of predefined kernels (e.g. Exact_predicates_inexact_constructions_kernel
).
Point coordinates can be represented in a homogeneous or cartesian way. The developer of a package can keep in mind that cartesian will be usually more space consuming, while homogeneous can be interesting if exact rational computations are needed. In any way, a package has to work with both representations.
Since CGAL uses homogeneous representation for affine geometry and not for projective geometry, the homogenizing coordinate is non zero. The cartesian representation corresponding to an homogeneous point \( (x_0,x_1,...,x_d,w)\) is \( (x_0/w,x_1/w,...,x_d/w)\). Hence, homogeneous representation is not unique; \( (\alpha x,\alpha y,\alpha z,\alpha w)\) is an alternative representation to \( (x,y,z,w)\) for any \( \alpha\neq 0\). Internally, CGAL always maintains a nonnegative homogenizing coordinate.
Each kernel object is provided as both a standalone class, which is parameterized by a kernel class (Geo_object_D<K>
), and as a type in the kernel class (K::Geo_object_D
). While the former use may be more natural for users not interested in the flexibility of the kernel (and is compatible with the original kernel design [6]), the latter syntax should be used in all code distributed with the library as it allows types in the kernel to be easily exchanged and modified. Similarly, each operation and construction in the kernel is provided via a function object class in the kernel class and also as either a member function or a global function; developers should use the function object classes to gain access to the functionality. See [7] for more details about this design and how it is accomplished.
The classes for the geometric objects in the kernel have a standardized interface.
bbox()
member function computing a bounding box. transform(Aff_transformation_d t)
member function to compute the object transformed by t
. has_on_positive_side(Point_d)
, has_on_boundary(Point_d)
, and has_on_negative_side(Point_d)
. Furthermore, there is a member function oriented_side(Point_d)
returning an object of type CGAL::Oriented_side
. has_on_bounded_side(Point_d)
, has_on_boundary(Point_d)
, and has_on_unbounded_side(Point_d)
. Furthermore, there is a member function bounded_side(Point_d)
returning an object of type CGAL::Bounded_side
. opposite()
returning the same object with opposite orientation. For a number of predicates, there are versions that operate on the coordinates directly, not on the geometric objects. These numbertype based predicates ease reuse with nonCGAL types.
Kernel traits should avoid redundant functionality, or if similar functionality is implemented with a different API, then one should really implement the functionality and the others call that one.
Whenever you need a predicate that is not present in the current kernel traits, you should first try to reuse the available predicates (you might rewrite the code or implement the new predicate using existing ones). If this is not feasible (especially for efficiency reasons), we have to decide on adding the new predicate to the kernel traits. If the new predicate is not too special, it will be added. Otherwise you cannot use the kernel as a traits class, but have to use additional traits.
See Section Cartesian versus homogeneous computation on how to derive the homogeneous version of a predicate from the Cartesian version.
When adding a new function object to the kernel you must:
include/CGAL/Kernel/function_objects.h
to add a new function object builder in namespace internal::
include/CGAL/Kernel/interface_macros.h
to add the actual function object class and its corresponding member function that returns an object of this class test/Kernel/include/CGAL/_test_new_2.h
and/or test/Kernel/include/CGAL/_test_new_3.h
to add the test for this function object. Kernel_23/doc/Kernel_23/Concepts/FunctionObjectConcepts.h
New_function_object
to the set of requirements for the Kernel concept in the file Kernel_23/doc/Kernel_23/Concepts/Kernel.h
Kernel_23/doc/Kernel_23/PackageDescription.txt