Class 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.

Inheritance

object

QuadEdgeSubdivision

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: NetTopologySuite.Triangulate.QuadEdge

Assembly: NetTopologySuite.dll

Syntax

public class QuadEdgeSubdivision

Constructors

QuadEdgeSubdivision(Envelope, double)

Creates a new instance of a quad-edge subdivision based on a frame triangle that encloses a supplied bounding box. A new super-bounding box that contains the triangle is computed and stored.

Declaration

public QuadEdgeSubdivision(Envelope env, double tolerance)

Parameters

Type	Name	Description
Envelope	env	the bounding box to surround
double	tolerance	the tolerance value for determining if two sites are equal

Properties

Envelope

Gets the envelope of the Subdivision (including the frame).

Declaration

public Envelope Envelope { get; }

Property Value

Type	Description
Envelope

Remarks

Gets the envelope

Tolerance

Gets the vertex-equality tolerance value used in this subdivision

Declaration

public double Tolerance { get; }

Property Value

Type	Description
double

Remarks

Gets the tolerance value

Methods

Connect(QuadEdge, QuadEdge)

Creates a new QuadEdge connecting the destination of a to the origin of b, in such a way that all three have the same left face after the connection is complete. The quadedge is recorded in the edges list.

Declaration

public QuadEdge Connect(QuadEdge a, QuadEdge b)

Parameters

Type	Name	Description
QuadEdge	a	A quadedge
QuadEdge	b	A quadedge

Returns

Type	Description
QuadEdge	A quadedge

Delete(QuadEdge)

Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.

Declaration

public void Delete(QuadEdge e)

Parameters

Type	Name	Description
QuadEdge	e	the quadedge to delete

GetEdges()

Gets the collection of base QuadEdges (one for every pair of vertices which is connected).

Declaration

public IList<QuadEdge> GetEdges()

Returns

Type	Description
IList<QuadEdge>	a collection of QuadEdges

GetEdges(GeometryFactory)

Gets the geometry for the edges in the subdivision as a MultiLineString containing 2-point lines.

Declaration

public MultiLineString GetEdges(GeometryFactory geomFact)

Parameters

Type	Name	Description
GeometryFactory	geomFact	the GeometryFactory to use

Returns

Type	Description
MultiLineString	a MultiLineString

GetFrameEdges()

Gets the edges which touch frame vertices. The returned edges are oriented so that their origin is a frame vertex.

Declaration

public IList<QuadEdge> GetFrameEdges()

Returns

Type	Description
IList<QuadEdge>	The edges which touch the frame

GetPrimaryEdges(bool)

Gets all primary quadedges in the subdivision. A primary edge is a QuadEdge which occupies the 0'th position in its array of associated quadedges. These provide the unique geometric edges of the triangulation.

Declaration

public IList<QuadEdge> GetPrimaryEdges(bool includeFrame)

Parameters

Type	Name	Description
bool	includeFrame	true if the frame edges are to be included

Returns

Type	Description
IList<QuadEdge>	a List of QuadEdges

GetTriangleCoordinates(bool)

Gets the coordinates for each triangle in the subdivision as an array.

Declaration

public IList<Coordinate[]> GetTriangleCoordinates(bool includeFrame)

Parameters

Type	Name	Description
bool	includeFrame	true if the frame triangles should be included

Returns

Type	Description
IList<Coordinate[]>	a list of Coordinate[4] representing each triangle

GetTriangleEdges(QuadEdge, QuadEdge[])

Gets the edges for the triangle to the left of the given QuadEdge.

Declaration

public static void GetTriangleEdges(QuadEdge startQE, QuadEdge[] triEdge)

Parameters

Type	Name	Description
QuadEdge	startQE
QuadEdge[]	triEdge

Exceptions

Type	Condition
ArgumentException	if the edges do not form a triangle

GetTriangleEdges(bool)

Gets a list of the triangles in the subdivision, specified as an array of the primary quadedges around the triangle.

Declaration

public IList<QuadEdge[]> GetTriangleEdges(bool includeFrame)

Parameters

Type	Name	Description
bool	includeFrame	true if the frame triangles should be included

Returns

Type	Description
IList<QuadEdge[]>	a List of QuadEdge[3] arrays

GetTriangleVertices(bool)

Gets a list of the triangles in the subdivision, specified as an array of the triangle Vertexes.

Declaration

public IList<Vertex[]> GetTriangleVertices(bool includeFrame)

Parameters

Type	Name	Description
bool	includeFrame	true if the frame triangles should be included

Returns

Type	Description
IList<Vertex[]>	a List of Vertex[3] arrays

GetTriangles(GeometryFactory)

Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangular NetTopologySuite.Triangulate.Polygons.

Declaration

public GeometryCollection GetTriangles(GeometryFactory geomFact)

Parameters

Type	Name	Description
GeometryFactory	geomFact	the GeometryFactory to use

Returns

Type	Description
GeometryCollection	a GeometryCollection of triangular Polygons

GetTriangles(bool, GeometryFactory)

Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangular Polygons, optionally including the frame triangles.

Declaration

public GeometryCollection GetTriangles(bool includeFrame, GeometryFactory geomFact)

Parameters

Type	Name	Description
bool	includeFrame	A flag indicating if the frame triangles should be included
GeometryFactory	geomFact	The GeometryFactory to use

Returns

Type	Description
GeometryCollection	A GeometryCollection of triangular polygons

GetVertexUniqueEdges(bool)

Gets a collection of QuadEdges whose origin vertices are a unique set which includes all vertices in the subdivision. The frame vertices can be included if required.

Declaration

public IList<QuadEdge> GetVertexUniqueEdges(bool includeFrame)

Parameters

Type	Name	Description
bool	includeFrame	true if the frame vertices should be included

Returns

Type	Description
IList<QuadEdge>	a collection of QuadEdge with the vertices of the subdivision as their origins

Remarks

This is useful for algorithms which require traversing the subdivision starting at all vertices. Returning a quadedge for each vertex is more efficient than the alternative of finding the actual vertices using GetVertices(bool) and then locating quadedges attached to them.

GetVertices(bool)

Gets the unique Vertexes in the subdivision, including the frame vertices if desired.

Declaration

public IEnumerable<Vertex> GetVertices(bool includeFrame)

Parameters

Type	Name	Description
bool	includeFrame	true if the frame vertices should be included

Returns

Type	Description
IEnumerable<Vertex>	a collection of the subdivision vertices

GetVoronoiCellPolygon(QuadEdge, GeometryFactory)

Gets the Voronoi cell around a site specified by the origin of a QuadEdge.

Declaration

public Polygon GetVoronoiCellPolygon(QuadEdge qe, GeometryFactory geomFact)

Parameters

Type	Name	Description
QuadEdge	qe	a quadedge originating at the cell site
GeometryFactory	geomFact	a factory for building the polygon

Returns

Type	Description
Polygon	a polygon indicating the cell extent

Remarks

The userData of the polygon is set to be the Coordinate of the site. This allows attaching external data associated with the site to this cell polygon.

GetVoronoiCellPolygons(GeometryFactory)

Gets a List of NetTopologySuite.Triangulate.Polygons for the Voronoi cells of this triangulation.

Declaration

public IList<Geometry> GetVoronoiCellPolygons(GeometryFactory geomFact)

Parameters

Type	Name	Description
GeometryFactory	geomFact	a geometry factory

Returns

Type	Description
IList<Geometry>	a List of Polygons

Remarks

The UserData of each polygon is set to be the Coordinate of the cell site. This allows easily associating external data associated with the sites to the cells.

GetVoronoiDiagram(GeometryFactory)

Gets the cells in the Voronoi diagram for this triangulation. The cells are returned as a GeometryCollection of NetTopologySuite.Triangulate.Polygons

Declaration

public GeometryCollection GetVoronoiDiagram(GeometryFactory geomFact)

Parameters

Type	Name	Description
GeometryFactory	geomFact	a geometry factory

Returns

Type	Description
GeometryCollection	a GeometryCollection of Polygons

Remarks

The userData of each polygon is set to be the Coordinate of the cell site. This allows easily associating external data associated with the sites to the cells.

InsertSite(Vertex)

Inserts a new site into the Subdivision, connecting it to the vertices of the containing triangle (or quadrilateral, if the split point falls on an existing edge).

Declaration

public QuadEdge InsertSite(Vertex v)

Parameters

Type	Name	Description
Vertex	v	the vertex to insert

Returns

Type	Description
QuadEdge	a new quad edge terminating in v

Remarks

This method does NOT maintain the Delaunay condition. If desired, this must be checked and enforced by the caller.

This method does NOT check if the inserted vertex falls on an edge. This must be checked by the caller, since this situation may cause erroneous triangulation

IsDelaunay()

Tests whether a subdivision is a valid Delaunay Triangulation. This is the case iff every edge is locally Delaunay, meaning that the apex of one adjacent triangle is not inside the circumcircle of the other adjacent triangle.

Declaration

public bool IsDelaunay()

Returns

Type	Description
bool

IsFrameBorderEdge(QuadEdge)

Tests whether a QuadEdge is an edge on the border of the frame facets and the internal facets. E.g. an edge which does not itself touch a frame vertex, but which touches an edge which does.

Declaration

public bool IsFrameBorderEdge(QuadEdge e)

Parameters

Type	Name	Description
QuadEdge	e	the edge to test

Returns

Type	Description
bool	true if the edge is on the border of the frame

IsFrameEdge(QuadEdge)

Tests whether a QuadEdge is an edge incident on a frame triangle vertex.

Declaration

public bool IsFrameEdge(QuadEdge e)

Parameters

Type	Name	Description
QuadEdge	e	the edge to test

Returns

Type	Description
bool	true if the edge is connected to the frame triangle

IsFrameVertex(Vertex)

Tests whether a vertex is a vertex of the outer triangle.

Declaration

public bool IsFrameVertex(Vertex v)

Parameters

Type	Name	Description
Vertex	v	the vertex to test

Returns

Type	Description
bool	true if the vertex is an outer triangle vertex

IsOnEdge(QuadEdge, Coordinate)

Tests whether a {@link Coordinate} lies on a {@link QuadEdge}, up to a tolerance determined by the subdivision tolerance.

Declaration

public bool IsOnEdge(QuadEdge e, Coordinate p)

Parameters

Type	Name	Description
QuadEdge	e	a QuadEdge
Coordinate	p	a point

Returns

Type	Description
bool	true if the vertex lies on the edge

IsVertexOfEdge(QuadEdge, Vertex)

Tests whether a Vertex is the start or end vertex of a QuadEdge, up to the subdivision tolerance distance.

Declaration

public bool IsVertexOfEdge(QuadEdge e, Vertex v)

Parameters

Type	Name	Description
QuadEdge	e
Vertex	v

Returns

Type	Description
bool	true if the vertex is a endpoint of the edge

Locate(Coordinate)

Finds a quadedge of a triangle containing a location specified by a Coordinate, if one exists.

Declaration

public QuadEdge Locate(Coordinate p)

Parameters

Type	Name	Description
Coordinate	p	the Coordinate to locate

Returns

Type	Description
QuadEdge	a quadedge on the edge of a triangle which touches or contains the location, or null if no such triangle exists

Locate(Coordinate, Coordinate)

Locates the edge between the given vertices, if it exists in the subdivision.

Declaration

public QuadEdge Locate(Coordinate p0, Coordinate p1)

Parameters

Type	Name	Description
Coordinate	p0	a coordinate
Coordinate	p1	another coordinate

Returns

Type	Description
QuadEdge	the edge joining the coordinates, if present, or null if no such edge exists

Locate(Vertex)

Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists.

Declaration

public QuadEdge Locate(Vertex v)

Parameters

Type	Name	Description
Vertex	v	the vertex to locate

Returns

Type	Description
QuadEdge	a quadedge on the edge of a triangle which touches or contains the location or null if no such triangle exists

LocateFromEdge(Vertex, QuadEdge)

Locates an edge of a triangle which contains a location specified by a Vertex v. The edge returned has the property that either v is on e, or e is an edge of a triangle containing v. The search starts from startEdge amd proceeds on the general direction of v.

Declaration

public QuadEdge LocateFromEdge(Vertex v, QuadEdge startEdge)

Parameters

Type	Name	Description
Vertex	v	the location to search for
QuadEdge	startEdge	an edge of the subdivision to start searching at

Returns

Type	Description
QuadEdge	a QuadEdge which contains v, or is on the edge of a triangle containing v

Remarks

This locate algorithm relies on the subdivision being Delaunay. For non-Delaunay subdivisions, this may loop for ever.

Exceptions

Type	Condition
LocateFailureException	if the location algorithm fails to converge in a reasonable number of iterations

MakeEdge(Vertex, Vertex)

Creates a new quadedge, recording it in the edges list.

Declaration

public QuadEdge MakeEdge(Vertex o, Vertex d)

Parameters

Type	Name	Description
Vertex	o	The origin vertex
Vertex	d	The destination vertex

Returns

Type	Description
QuadEdge	A new quadedge

SetLocator(IQuadEdgeLocator)

Sets the IQuadEdgeLocator to use for locating containing triangles in this subdivision.

Declaration

public void SetLocator(IQuadEdgeLocator locator)

Parameters

Type	Name	Description
IQuadEdgeLocator	locator	a QuadEdgeLocator

VisitTriangles(ITriangleVisitor, bool)

Declaration

public void VisitTriangles(ITriangleVisitor triVisitor, bool includeFrame)

Parameters

Type	Name	Description
ITriangleVisitor	triVisitor
bool	includeFrame