Guide > Geometry

Geometry

LEDA offers geometry kernels for two-dimensional geometry and three-dimensional geometry. These kernels come in two kinds each: a rational kernel and a floating point kernel.

Based on the geometry kernels, LEDA offers a wide variety of data types and algorithms for two- and three-dimensional geometry.

What is a Geometry Kernel?

A geometry kernel offers basic geometric objects, such as points, lines, segments, rays, planes, circles, ..., and geometric primitives operating on these objects, e.g., the computation of the area of the triangle defined by three points and the computation of the intersection of two lines.

Difference between Rational and Floating Point Kernel

In the rational kernel the Cartesian coordinates of points are rationals (,i.e., rational numbers in the sense of mathematics) and the geometric primitives are exact, i.e., they always give exact results.

In the floating point kernel the Cartesian coordinates of points are double precision floating point numbers and the geometric primitives are approximate, i.e., they usually give exact results but there is no guarantee. Therefore, the use of the floating point kernel is not without risk.

Examples for the dangers of floating point arithmetic

Why Floating Point at all?

The floating point kernel is contained in LEDA for the following reasons:
  • The "outside world", e.g., graphics systems used to visualize the results of geometric computations, wants floating point numbers.
  • Historical Reasons: The floating point kernel was first.
  • Floating point computation is faster than computing with real numbers. This point is dangerous, because floating point computation is not reliable. Moreover, the overhead of exact computations is small (at most factor three) in practice.

Tip

Use the rational kernel exclusively !

Only when a program is stable and the rational kernel does not give the desired performance consider switching to the floating point kernel. A switch to the floating point kernel should be accompanied by a careful analysis of its limits.

Further Topics:

Geometry Objects

Geometry Basics

Geometric Primitives

Affine Transformations

Generators for Geometric Objects

Writing Kernel Independent Code

See also:

Geometry Algorithms

GeoWin

Number Types