Namespace NetTopologySuite.Triangulate.QuadEdge

Classes to implement a topological subdivision of quadeges, to support creating triangulations and Voronoi diagrams.

Classes

EdgeConnectedTriangleTraversal

A framework to visit sets of edge-connected QuadEdgeTriangles in breadth-first order

LastFoundQuadEdgeLocator

Locates QuadEdges in a QuadEdgeSubdivision, optimizing the search by starting in the locality of the last edge found.

A class that represents the edge data structure which implements the quadedge algebra. The quadedge algebra was described in a well-known paper by Guibas and Stolfi, "Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", ACM Transactions on Graphics, 4(2), 1985, 75-123.

Each edge object is part of a quartet of 4 edges, linked via their Rot references. Any edge in the group may be accessed using a series of Rot operations. Quadedges in a subdivision are linked together via their Next references. The linkage between the quadedge quartets determines the topology of the subdivision.

The edge class does not contain separate information for vertices or faces; a vertex is implicitly defined as a ring of edges (created using the Next field).

QuadEdgeSubdivision

A class that contains the QuadEdges representing a planar subdivision that models a triangulation. The subdivision is constructed using the quadedge algebra defined in the class QuadEdge. All metric calculations are done in the Vertex class. In addition to a triangulation, subdivisions support extraction of Voronoi diagrams. This is easily accomplished, since the Voronoi diagram is the dual of the Delaunay triangulation.

Subdivisions can be provided with a tolerance value. Inserted vertices which are closer than this value to vertices already in the subdivision will be ignored. Using a suitable tolerance value can prevent robustness failures from happening during Delaunay triangulation.

Subdivisions maintain a frame triangle around the client-created edges. The frame is used to provide a bounded "container" for all edges within a TIN. Normally the frame edges, frame connecting edges, and frame triangles are not included in client processing.

QuadEdgeTriangle

Models a triangle formed from QuadEdges in a QuadEdgeSubdivision which forms a triangulation. The class provides methods to access the topological and geometric properties of the triangle and its neighbours in the triangulation. Triangle vertices are ordered in CCW orientation in the structure.

QuadEdgeUtil

TrianglePredicate

Algorithms for computing values and predicates associated with triangles.

Vertex

Models a site (node) in a QuadEdgeSubdivision. The sites can be points on a line string representing a linear site.

The vertex can be considered as a vector with a norm, length, inner product, cross product, etc. Additionally, point relations (e.g., is a point to the left of a line, the circle defined by this point and two others, etc.) are also defined in this class.

It is common to want to attach user-defined data to the vertices of a subdivision. One way to do this is to subclass Vertex to carry any desired information.

Interfaces

IQuadEdgeLocator

An interface for classes which locate an edge in a QuadEdgeSubdivision which either contains a given Vertex V or is an edge of a triangle which contains V. Implementors may utilized different strategies for optimizing locating containing edges/triangles.

ITraversalVisitor

Interface for classes which process triangles visited during traversals of a QuadEdgeSubdivision

ITriangleVisitor

An interface for algorithms which process the triangles in a QuadEdgeSubdivision.