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).