What this program does is to incrementally create the Delauney graph of a given set of sites. The Delauney graph consists of all tetrahedrons of the Delauney diagram, with two tetrahedrons being linked together if they share a common triangle. In this implementation we use the concept of "infinite tetrahedrons", being the "convex hull" of a triangle on the convex hull of the sites together with the point at infinity.

This code is a replacement for previous versions of Triangulate3D (IRIS Explorer release 3.0 and previous). It shares an engine with Triangulate2D, and it now produces a correct triangulation of regular data.

The engine is an incremental point-insertion algorithm. This is ideally O(n log n) but may be up to O(n2) depending on the distribution of points.

The effect of the jitter widget has been removed as it is no longer necessary.


Port: Input Data
Type: Lattice
Constraints: curvilinear
Constraints: 3-cD
The input lattice of curvilinear points to be triangulated.


Port: jitter
Type: Radio Box
Menu Item: Actual data
Menu Item: Add jitter to data
This widget does nothing but is retained for compatibility with previous releases.


Port: Output Pyramid
Type: Pyramid
Constraints: 3-layer
Constraints: 1..-baseLat
Constraints: 3-D compression
Constraints: unique-compression type
The resultant pyramid of tetrahedras.


The module may produce 'Degenerate Tetrahedra' warnings, particularly when the input data is regular. These can usually be ignored.


Triangulate2D, LatToPyr.
[Documentation Home]
© The Numerical Algorithms Group Ltd, Oxford UK. 2000