Triangulator.Delaunay Class Reference

Performs the Delauney triangulation on a set of vertices. More...

Static Public Member Functions

static List< Geometry.Triangle > Triangulate (List< ControlMeshVertex > Vertex)

Static Private Member Functions

static bool InCircle (ControlMeshVertex p, ControlMeshVertex p1, ControlMeshVertex p2, ControlMeshVertex p3)

Detailed Description

Based on Paul Bourke's "An Algorithm for Interpolating Irregularly-Spaced Data with Applications in Terrain Modelling" http://astronomy.swin.edu.au/~pbourke/modelling/triangulate/

Definition at line 21 of file Delaunay.cs.

Member Function Documentation

static List<Geometry.Triangle> Triangulator.Delaunay.Triangulate ( List< ControlMeshVertex > Vertex ) [static]

Performs Delauney triangulation on a set of points.

The triangulation doesn't support multiple points with the same planar location. Vertex-lists with duplicate points may result in strange triangulation with intersecting edges. To avoid adding multiple points to your vertex-list you can use the following anonymous predicate method:

      if(!Vertices.Exists(delegate(Triangulator.Geometry.Point p) { return pNew.Equals2D(p); }))
       Vertices.Add(pNew);

The triangulation algorithm may be described in pseudo-code as follows:

      subroutine Triangulate
      input : vertex list
      output : triangle list
         initialize the triangle list
         determine the supertriangle
         add supertriangle vertices to the end of the vertex list
         add the supertriangle to the triangle list
         for each sample point in the vertex list
            initialize the edge buffer
            for each triangle currently in the triangle list
               calculate the triangle circumcircle center and radius
               if the point lies in the triangle circumcircle then
                  add the three triangle edges to the edge buffer
                  remove the triangle from the triangle list
               endif
            endfor
            delete all doubly specified edges from the edge buffer
               this leaves the edges of the enclosing polygon only
            add to the triangle list all triangles formed between the point 
               and the edges of the enclosing polygon
         endfor
         remove any triangles from the triangle list that use the supertriangle vertices
         remove the supertriangle vertices from the vertex list
      end

Parameters:

Vertex

List of vertices to triangulate.

Returns:: Triangles referencing vertex indices arranged in clockwise order

Definition at line 68 of file Delaunay.cs.

static bool Triangulator.Delaunay.InCircle	(	ControlMeshVertex	p,
		ControlMeshVertex	p1,
		ControlMeshVertex	p2,
		ControlMeshVertex	p3
	)			`[static, private]`

Returns true if the point (p) lies inside the circumcircle made up by points (p1,p2,p3).

NOTE: A point on the edge is inside the circumcircle

Parameters:

	p	Point to check
	p1	First point on circle
	p2	Second point on circle
	p3	Third point on circle

Returns:: true if p is inside circle

Definition at line 184 of file Delaunay.cs.