DungeonArchitect.Triangulator.Delauney Class Reference

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

Static Public Member Functions
static List< Geometry.Triangle >	Triangulate (List< Triangulator.Geometry.Point > Vertex)
	Performs Delauney triangulation on a set of points. More...

Detailed Description

Performs the Delauney triangulation on a set of vertices.

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 19 of file Delauney.cs.

Member Function Documentation

Triangulate()

static List<Geometry.Triangle> DungeonArchitect.Triangulator.Delauney.Triangulate ( List< Triangulator.Geometry.Point >  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 66 of file Delauney.cs.

---

The documentation for this class was generated from the following file:

• C:/gamedev/unity/DA20.1X/Assets/CodeRespawn/DungeonArchitect/Scripts/Core/Frameworks/Triangulator/Delauney.cs