Download the Triangulation Solver Package (Requires Manifold System 4.50)

The first two solvers create a Delaunay triangulation on a point set or on other objects. The Delaunay triangulation may be created as an combination of points, lines, or areas.  The illustrations at right show the solver working to create a triangulation on a point set (upper right), first as lines only and then as lines and areas.  The areas example has been colored to show how the solver creates different triangular area polygons.

The latter two, "Select" solvers are used to locate significant features in data sets. They may be used for data mining, or to "thin" sets of data points to achieve a fewer number of points that nonetheless retain significant features. These are conceptually related to the Delaunay solvers, since Delaunay triangulations are often the starting point for approximations.

Installation: Place the triangulation.mxz solver package file in a convenient folder, such as the Manifold System installation directory (normally C:\Program Files\Manifold System). Launch Manifold, choose Tools - Install Package and browse over to the folder where triangulation.mxz is found. Install the package. There is no need to reboot.

Delaunay Triangulation 

If unfamiliar with networks, please read the introductory network topics in the 4.50 Help system. Also, please read the topics in the Solver Reference book for Voronoi solvers and for the Network creation solvers (e.g., Gabriel network and relative neighborhood network).

Delaunay triangulations are best described in terms of a Voronoi diagram. Suppose we have a point set for which we have created a Voronoi diagram. The Voronoi diagram creates a Voronoi cell (or "domain") about each point. If we draw a line between any two points whose Voronoi domains touch we create a set of triangles known as the Delaunay triangulation. Generally, this triangulation is unique. One of its properties is that the minimum enclosing circle of every triangle does not contain any other data point. 

Delaunay triangulations are often used to construct an approximation for a continuous range of x,y values when data points are available only for a discrete, limited range of points. For example, the Akima interpolation used in Manifold's smooth surface interpolation solvers can create a smooth surface from a fixed point set. The internal algorithm begins by creating a Delaunay triangulation and then computes interpolants using the triangulation.

Manifold's Delaunay solvers are unusually strong in that they can create a triangulation on areas or lines as well as on points. A "points only" version of the solver is provided since an especially fast algorithm may be used when the data set consists only of points. Both solvers can create either lines or areas or both for the triangulation.  The illustrations at left shows a Delaunay triangulation created for a polygonal area (top) with the result of the triangulation shown as well (bottom). Note that the edges of the triangulation may or may not coincide with the edges of the source polygon.
 
Select Points Solvers

It's often the case where we have large data sets that consist mainly of repetitive data, with only a few data points representing significant departures from the rest. For example, terrain elevation data sets often contain huge numbers of points even though only a few of them are necessary to show visibly different features in the terrain. These solvers allow "thinning" of the data set by retaining only significant points.  

The Select Points solvers provide two different methods:

Select Points by Threshold will select points where the "threshold" difference between the point and its neighbor exceeds a particular threshold value. This solver might have better been named "Select Points by Threshold Delta," but that would have been too long for the menu. The illustrations inserted "in-line" show the progressive selection of more significant points.  The original point set is in blue.  Each illustration in the sequence increases the significance threshold to select fewer and more significant points from the data set, with selected points colored in red.

Select Significant Points uses a more sophisticated algorithm to select the "most significant" given percentage of points. For example, if we use 50%, the solver will select only half of the points given and will choose only the most significant 50%.

The main usage of the Select Points solvers will be to "thin" data sets used for displaying data in 3D View Studio. 

However, numerous other data sets will benefit from "thinning" or from the extraction of significant features. For example, one might thin data on counties to find the most significant changes in terms of crime rate or social services benefits utilization. Note that this will find counties that most stand out from surrounding counties and so reflect significant changes from county to county. If one is searching for significant changes or "features" this is one method to use. 

Download the Solver Package Today 

To repeat, this solver package is a free download for Manifold System Release 4.50 users.  We value your patronage and hope you enjoy these cool new solvers we have created for you.

Download the Triangulation Solver Package (Requires Manifold System 4.50)

Don't have Manifold System yet?  Visit the Manifold.net Online Store right now and get a copy for only $145.