Class Dwyer

Builds a delaunay triangulation using the divide-and-conquer algorithm.

Inheritance

System.Object

Dwyer

Inherited Members

System.Object.ToString()

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

Namespace: UnityEngine.Experimental.U2D.TriangleNet.Meshing.Algorithm

Syntax

public class Dwyer : ITriangulator

Remarks

The divide-and-conquer bounding box

I originally implemented the divide-and-conquer and incremental Delaunay triangulations using the edge-based data structure presented by Guibas and Stolfi. Switching to a triangle-based data structure doubled the speed. However, I had to think of a few extra tricks to maintain the elegance of the original algorithms.

The "bounding box" used by my variant of the divide-and-conquer algorithm uses one triangle for each edge of the convex hull of the triangulation. These bounding triangles all share a common apical vertex, which is represented by NULL and which represents nothing. The bounding triangles are linked in a circular fan about this NULL vertex, and the edges on the convex hull of the triangulation appear opposite the NULL vertex. You might find it easiest to imagine that the NULL vertex is a point in 3D space behind the center of the triangulation, and that the bounding triangles form a sort of cone.

This bounding box makes it easy to represent degenerate cases. For instance, the triangulation of two vertices is a single edge. This edge is represented by two bounding box triangles, one on each "side" of the edge. These triangles are also linked together in a fan about the NULL vertex.

The bounding box also makes it easy to traverse the convex hull, as the divide-and-conquer algorithm needs to do.

Fields

UseDwyer

Declaration

public bool UseDwyer

Field Value

Type	Description
System.Boolean

Methods

Triangulate(IList<Vertex>, Configuration)

Form a Delaunay triangulation by the divide-and-conquer method.

Declaration

public IMesh Triangulate(IList<Vertex> points, Configuration config)

Parameters

Type	Name	Description
System.Collections.Generic.IList<Vertex>	points
Configuration	config

Returns

Type	Description
IMesh

Implements

ITriangulator.Triangulate(IList<Vertex>, Configuration)

Remarks

Sorts the vertices, calls a recursive procedure to triangulate them, and removes the bounding box, setting boundary markers as appropriate.