^{Some details of the triangulation}

Principles of creation

There are purposes of Soft creation:

1. Triangulation must be like Delauney one.
2. Calculation time must be close to linear function from number of initial points.
3. The initial data can be one of:

·  points on plane with coordination X, Y and attribute А;

·  edges, that are determined by polylines with attribute A;

·  contour that is determined by poly-polygon (polygon with holes) with attribute A.
4. A kind of triangulation when the triangles edges are build across the points with no equal attributes must exists (NonEqAttr).
5. Triangulation time of 1 000 000 points must be not more some minutes for Pentium-4, 1GHz.

Implementation

Soft was mainly developed in Delphi, but there are fragments on C++. Soft is designed as DLL-library with interface that allows you to use Delphi, Borland Builder and Visual Studio. There are examples of using this program.

Peculiarities

The main peculiarities is presence of NonEqAttr, that is used for triangulation relief by initial izolines. Lower you can see illustrations of working of standard (Delauney) and NonEqAttr.



Рic.1. NonEqAttr triangulation.


Pic.2. Delauney triangulation.

Comment. Initial edges, setting relief izolines, show in red. Edges after triangulation show in blue. In this fragment izolines have different attributes (heights) so NonEqAttr triangulation is executed differently in principle and you can see essential differences between NonEqAttr and Delauney triangulations.
NonEqAttr approximates relief more correct.

Article on this item

Other peculiarity is possibility of triangulation inside a poly-polygon. Fragment of this triangulation you can see on pic.3


Pic.3. Triangulation inside poly-polygon.

Properties

Time function from number of initial points is linear.
Real map with izolines that have 500 000 points was triangulated in 160 sec. with using NonEqAttr (processor Athlon 1.3, Mem 256M). Triangulation time without NonEqAttr is halve. Compare with Jonathan Shewchuk .

On Main