G E O M E T R Y

LEDA And Computational Geometry

LEDA provides many two-dimensional as well as three-dimensional basic data types such as points, segments, spheres, circles, planes, polygons, and many more. See in the manual basic data types 1 and basic data types 2.

They all come with an enormous collection of related methods, e.g. cite the binary operations on general polygons (polygons with holes). See in the manual gen_polygon and r_circle_gen_polygon.

Beyond that, it also gives you several advanced data structures that help you answer many typical questions arising in computational geometry, such as delaunay diagrams, voronoi diagrams, and planar subdivisions. See this in the manual advanced data types.

Moreover, there are many helpful functions and algorithms available, such as Minkowski sums, segment intersection algorithms, closest pair computations and many more. Read in the manual about LEDA's geometry algorithms.

The overwhelming strength of LEDA's geometric module is based on three further features:

• First, LEDA's algorithms come along with every possible problem instance, degenerate input data is not a problem for its algorithms.
• Second, the ' basic problem' of exact arithmetic which has to be solved in order to guarantee correct results, namely the must of using exact arithmetic, IS solved in LEDA. There are even several ready-to-use solutions to this problem available. For an example read the manual about circles, rational_circles and real_circles.
• Third, LEDA's geometric data types are sometimes closely related to LEDA's graph and network data types. The segment intersection algorithms can, for instance, associate an underlying graph with the computed arrangement. This is also the case with polygons. Thus, LEDA can do a lot of things with geometric objects that other tools can't because LEDA can make use of structural information.

And last but not least, with LEDA you can display your geometric objects; you can use the standard windows type that provides the necessary functionality. For information on LEDA WIndows see chapter 3.4 in the manual.

There are also very specialized data types available that are tailored to support the visualization of geometric data. For more information see the pages about LEDA's GeoWin and about Windows for 3D Visualization.

LEDA And Exact Arithmetic

If you are familiar with geometric problem solutions you know about the main challenges in this area: Due to the finite precision arithmetic of the standard number types provided by your programming language, you usually get into problems quite frequently. Even well known CAD, CAE or GIS programs crash on several input data.

LEDA has its own geometric kernel! No matter whether the input data is degenerated or the operations require exact computing, with LEDA your tasks can be done! You can choose whether you run LEDA's geometric kernel with doubles, or rational numbers, or algebraic numbers, whatever is required by your concrete problem. There are integers as well as floating numbers with arbitrary precision available. A floating point filter guarantees for efficiency of the methods. For example PolyGIS, the fastest GIS in the German market, is empowered by LEDA's arithmetic.

See for yourself! Read the manual entries for Integers, Bigfloats, Reals, Interval Arithmetic, Floating Point Filter and many more.

LEDA And Curved Geometry

Polygons with Circular Arcs:

The LEDA types polygon and gen_polygon allow only straight line edges. Several of our customers have to compute with polygons where at least some edges are circular arcs. Often approximating such an edge by several straight line segments is not appropriate.

Since version 5.0 LEDA provides two new data types called r_circle_polygon and r_circle_gen_polygon that can handle polygons having straight line segments as well as circular arcs.

With version 5.1 some of our exact computation with circular arcs are now about 10 times faster than before. And approximated computation (= input and output data contain curved segments, only the computation uses straight line approximations) of boolean operations is now as fast as in the case of straight line segments.

>>> click the picture to see details

The type r_circle_gen_polygon allows to model polygons with holes, where straight line segments as well as circular segments are supported. All the usual polygon operations are provided.

In particular, we offer the following boolean operations:

• intersection,
• union,
• difference and
• symmetric difference.

It is important to emphasize that all these computations are exact, i.e. no rounding errors can occur.

Related Subjects:

SWEEP:plane sweep algorithm on circular segments (r_circle_segment).
Data Type Real: with LEDA 5.0 significant speed-up!

Documentation:

Read the manual page on r_circle_gen_polygon.
Read the manual page on r_circle_polygon.
Read the manual page on r_circle_segment and sweep.
Read the manual page on data type real.

LINKS

LEDA product pages
LEDA manual
LEDA tutorial
other LEDA information ressources