Basic Data Types for Two-Dimensional Geometry

LEDA provides a collection of simple data types for computational geometry, such as points, vectors, directions, hyperplanes, segments, rays, lines, affine transformations, circles, polygons, and operations connecting these types.

The computational geometry kernel has evolved over time. The first kernel
(types *point*, *line*, ...) was restricted to two-dimensional
geometry and used floating point arithmetic as the underlying arithmetic. We
found it very difficult to implement reliable geometric algorithms based on
this kernel. See the chapter on computational geometry of [64] for
some examples of the danger of floating point arithmetic in geometric
computations. Starting with version 3.2 we therefore also provided a kernel
based on exact rational arithmetic (types
*rat_point*, *rat_segment* ...).
(This kernel is still restricted to two dimensions.)

From version 4.5 on we offer a two-dimensional kernel based on the type
*real*, which also guarantees exact results. The corresponding data types
are named *real_point*, *real_segment*, ...

All two-dimensional object types defined in this section support the following operations:

**Equality and Identity Tests**

bool |
identical(object p, object q) |
Test for identity. |

bool |
p = = q |
Test for equality. |

bool |
p! = q |
Test for inequality. |

**I/O Operators**

ostream& |
ostream& O < < object x |
writes the object x to output stream O. |

istream& |
istream& I > > object& x |
reads an object from input stream I into variable x. |

- Points ( point )
- Segments ( segment )
- Straight Rays ( ray )
- Straight Lines ( line )
- Circles ( circle )
- Polygons ( POLYGON )
- Generalized Polygons ( GEN_POLYGON )
- Triangles ( triangle )
- Iso-oriented Rectangles ( rectangle )
- Rational Points ( rat_point )
- Rational Segments ( rat_segment )
- Rational Rays ( rat_ray )
- Straight Rational Lines ( rat_line )
- Rational Circles ( rat_circle )
- Rational Triangles ( rat_triangle )
- Iso-oriented Rational Rectangles ( rat_rectangle )
- Real Points ( real_point )
- Real Segments ( real_segment )
- Real Rays ( real_ray )
- Straight Real Lines ( real_line )
- Real Circles ( real_circle )
- Real Triangles ( real_triangle )
- Iso-oriented Real Rectangles ( real_rectangle )
- Geometry Algorithms ( geo_alg )
- Transformation ( TRANSFORM )
- Point Generators ( point generators )
- Point on Rational Circle ( r_circle_point )
- Segment of Rational Circle ( r_circle_segment )
- Polygons with circular edges ( r_circle_polygon )
- Generalized polygons with circular edges ( r_circle_gen_polygon )
- Parser for well known binary format ( wkb_io )