Fade2D is an easy to use Delaunay triangulation library for C++:

- Fastest Delaunay algorithm
- 2D Delaunay with Polygon support and Constraint Edges
- 2.5D Delaunay for Surfaces and Digital Elevation Models
- Grid Mesher, Delaunay Mesh Generator
- Polygon Clipping, Boolean Operations on Polygons
- Cut and Fill module
- Free for scientific research. Commercial licenses and support are available

## Fade2.5D – Extension for Delaunay triangulations in 2.5D

A 2.5D Delaunay triangulation is a 2D Delaunay triangulation where each point (x,y) has a certain height. 2.5D allows exactly one height value z per (x,y) coordinate pair and that distinguishes it from 3D. It works for surfaces which have an intersection-free projection to the x,y-plane like a terrain. Closed objects such as, for example, a ball do not have such surfaces. Applications for Fade2.5D are surface metrology and terrain triangulation from LiDAR data.

Fade 2.5D supports fast computation of ISO-contours and answers height queries for arbitrary (x,y)-coordinates in an extraordinary fast manner.

## Constrained and Conforming Delaunay

Constraint edges can be inserted. This works also in 2.5D.

## Delaunay mesh generator

The mesh generator creates high quality triangles inside a given area. The quality of the triangular output mesh can be controlled by specification of a minimal interior angle that will be kept by all triangles (as far as existing constraint edges allow). Additionally a target value for the length of the edges can be specified which is often required for simulation purposes. The mesh generator is available in 2D and 2.5D.

## Performance of Fade

Fade is very fast. One million points take 0.6 seconds. The diagram below shows that the practical run-time grows only linearly with the number of input points (uniformly distributed in a rectangular area for this benchmark).

## 15 Comments