QuadEdgeSubdivision (org.locationtech.jts:jts-core 1.18.0 API)

java.lang.Object
- org.locationtech.jts.triangulate.quadedge.QuadEdgeSubdivision

```
public class QuadEdgeSubdivision
extends Object
```
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.

Author:

David Skea, Martin Davis

Constructor Summary

Constructors
Constructor and Description
`QuadEdgeSubdivision(Envelope env, double tolerance)` Creates a new instance of a quad-edge subdivision based on a frame triangle that encloses a supplied bounding box.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`QuadEdge`	`connect(QuadEdge a, QuadEdge b)` 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.
`void`	`delete(QuadEdge e)` Deletes a quadedge from the subdivision.
`Collection`	`getEdges()` Gets the collection of base `QuadEdge`s (one for every pair of vertices which is connected).
`Geometry`	`getEdges(GeometryFactory geomFact)` Gets the geometry for the edges in the subdivision as a `MultiLineString` containing 2-point lines.
`Envelope`	`getEnvelope()` Gets the envelope of the Subdivision (including the frame).
`List`	`getPrimaryEdges(boolean includeFrame)` Gets all primary quadedges in the subdivision.
`double`	`getTolerance()` Gets the vertex-equality tolerance value used in this subdivision
`List`	`getTriangleCoordinates(boolean includeFrame)` Gets the coordinates for each triangle in the subdivision as an array.
`List`	`getTriangleEdges(boolean includeFrame)` Gets a list of the triangles in the subdivision, specified as an array of the primary quadedges around the triangle.
`static void`	`getTriangleEdges(QuadEdge startQE, QuadEdge[] triEdge)` Gets the edges for the triangle to the left of the given `QuadEdge`.
`Geometry`	`getTriangles(GeometryFactory geomFact)` Gets the geometry for the triangles in a triangulated subdivision as a `GeometryCollection` of triangular `Polygon`s.
`List`	`getTriangleVertices(boolean includeFrame)` Gets a list of the triangles in the subdivision, specified as an array of the triangle `Vertex`es.
`List`	`getVertexUniqueEdges(boolean includeFrame)` Gets a collection of `QuadEdge`s whose origin vertices are a unique set which includes all vertices in the subdivision.
`Collection`	`getVertices(boolean includeFrame)` Gets the unique `Vertex`es in the subdivision, including the frame vertices if desired.
`Polygon`	`getVoronoiCellPolygon(QuadEdge qe, GeometryFactory geomFact)` Gets the Voronoi cell around a site specified by the origin of a QuadEdge.
`List`	`getVoronoiCellPolygons(GeometryFactory geomFact)` Gets a List of `Polygon`s for the Voronoi cells of this triangulation.
`Geometry`	`getVoronoiDiagram(GeometryFactory geomFact)` Gets the cells in the Voronoi diagram for this triangulation.
`QuadEdge`	`insertSite(Vertex v)` 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).
`boolean`	`isFrameBorderEdge(QuadEdge e)` Tests whether a QuadEdge is an edge on the border of the frame facets and the internal facets.
`boolean`	`isFrameEdge(QuadEdge e)` Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
`boolean`	`isFrameVertex(Vertex v)` Tests whether a vertex is a vertex of the outer triangle.
`boolean`	`isOnEdge(QuadEdge e, Coordinate p)` Tests whether a `Coordinate` lies on a `QuadEdge`, up to a tolerance determined by the subdivision tolerance.
`boolean`	`isVertexOfEdge(QuadEdge e, Vertex v)` Tests whether a `Vertex` is the start or end vertex of a `QuadEdge`, up to the subdivision tolerance distance.
`QuadEdge`	`locate(Coordinate p)` Finds a quadedge of a triangle containing a location specified by a `Coordinate`, if one exists.
`QuadEdge`	`locate(Coordinate p0, Coordinate p1)` Locates the edge between the given vertices, if it exists in the subdivision.
`QuadEdge`	`locate(Vertex v)` Finds a quadedge of a triangle containing a location specified by a `Vertex`, if one exists.
`QuadEdge`	`locateFromEdge(Vertex v, QuadEdge startEdge)` Locates an edge of a triangle which contains a location specified by a Vertex v.
`QuadEdge`	`makeEdge(Vertex o, Vertex d)` Creates a new quadedge, recording it in the edges list.
`void`	`setLocator(QuadEdgeLocator locator)` Sets the `QuadEdgeLocator` to use for locating containing triangles in this subdivision.
`void`	`visitTriangles(TriangleVisitor triVisitor, boolean includeFrame)` Visitors

Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - QuadEdgeSubdivision
```
public QuadEdgeSubdivision(Envelope env,
                           double tolerance)
```
    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.
    
    Parameters:
    
    env - the bounding box to surround
    
    tolerance - the tolerance value for determining if two sites are equal
- Method Detail
  - getTriangleEdges
```
public static void getTriangleEdges(QuadEdge startQE,
                                    QuadEdge[] triEdge)
```
    Gets the edges for the triangle to the left of the given QuadEdge.
    
    Parameters:
    
    startQE -
    
    triEdge -
    
    Throws:
    
    IllegalArgumentException - if the edges do not form a triangle
  - getTolerance
```
public double getTolerance()
```
    Gets the vertex-equality tolerance value used in this subdivision
    
    Returns:
    
    the tolerance value
  - getEnvelope
```
public Envelope getEnvelope()
```
    Gets the envelope of the Subdivision (including the frame).
    
    Returns:
    
    the envelope
  - getEdges
```
public Collection getEdges()
```
    Gets the collection of base QuadEdges (one for every pair of vertices which is connected).
    
    Returns:
    
    a collection of QuadEdges
  - setLocator
```
public void setLocator(QuadEdgeLocator locator)
```
    Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
    
    Parameters:
    
    locator - a QuadEdgeLocator
  - makeEdge
```
public QuadEdge makeEdge(Vertex o,
                         Vertex d)
```
    Creates a new quadedge, recording it in the edges list.
    
    Parameters:
    
    o -
    
    d -
    
    Returns:
    
    a new quadedge
  - connect
```
public QuadEdge connect(QuadEdge a,
                        QuadEdge b)
```
    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.
    
    Parameters:
    
    a -
    
    b -
    
    Returns:
    
    a quadedge
  - delete
```
public void delete(QuadEdge e)
```
    Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.
    
    Parameters:
    
    e - the quadedge to delete
  - locateFromEdge
```
public QuadEdge locateFromEdge(Vertex v,
                               QuadEdge startEdge)
```
    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.
    This locate algorithm relies on the subdivision being Delaunay. For non-Delaunay subdivisions, this may loop for ever.
    
    Parameters:
    
    v - the location to search for
    
    startEdge - an edge of the subdivision to start searching at
    
    Returns:
    
    a QuadEdge which contains v, or is on the edge of a triangle containing v
    
    Throws:
    
    LocateFailureException - if the location algorithm fails to converge in a reasonable number of iterations
  - locate
```
public QuadEdge locate(Vertex v)
```
    Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists.
    
    Parameters:
    
    v - the vertex to locate
    
    Returns:
    
    a quadedge on the edge of a triangle which touches or contains the location or null if no such triangle exists
  - locate
```
public QuadEdge locate(Coordinate p)
```
    Finds a quadedge of a triangle containing a location specified by a Coordinate, if one exists.
    
    Parameters:
    
    p - the Coordinate to locate
    
    Returns:
    
    a quadedge on the edge of a triangle which touches or contains the location or null if no such triangle exists
  - locate
```
public QuadEdge locate(Coordinate p0,
                       Coordinate p1)
```
    Locates the edge between the given vertices, if it exists in the subdivision.
    
    Parameters:
    
    p0 - a coordinate
    
    p1 - another coordinate
    
    Returns:
    
    the edge joining the coordinates, if present or null if no such edge exists
  - insertSite
```
public QuadEdge insertSite(Vertex v)
```
    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).
    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
    
    Parameters:
    
    v - the vertex to insert
    
    Returns:
    
    a new quad edge terminating in v
  - isFrameEdge
```
public boolean isFrameEdge(QuadEdge e)
```
    Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
    
    Parameters:
    
    e - the edge to test
    
    Returns:
    
    true if the edge is connected to the frame triangle
  - isFrameBorderEdge
```
public boolean isFrameBorderEdge(QuadEdge e)
```
    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.
    
    Parameters:
    
    e - the edge to test
    
    Returns:
    
    true if the edge is on the border of the frame
  - isFrameVertex
```
public boolean isFrameVertex(Vertex v)
```
    Tests whether a vertex is a vertex of the outer triangle.
    
    Parameters:
    
    v - the vertex to test
    
    Returns:
    
    true if the vertex is an outer triangle vertex
  - isOnEdge
```
public boolean isOnEdge(QuadEdge e,
                        Coordinate p)
```
    Tests whether a Coordinate lies on a QuadEdge, up to a tolerance determined by the subdivision tolerance.
    
    Parameters:
    
    e - a QuadEdge
    
    p - a point
    
    Returns:
    
    true if the vertex lies on the edge
  - isVertexOfEdge
```
public boolean isVertexOfEdge(QuadEdge e,
                              Vertex v)
```
    Tests whether a Vertex is the start or end vertex of a QuadEdge, up to the subdivision tolerance distance.
    
    Parameters:
    
    e -
    
    v -
    
    Returns:
    
    true if the vertex is a endpoint of the edge
  - getVertices
```
public Collection getVertices(boolean includeFrame)
```
    Gets the unique Vertexes in the subdivision, including the frame vertices if desired.
    
    Parameters:
    
    includeFrame - true if the frame vertices should be included
    
    Returns:
    
    a collection of the subdivision vertices
    
    See Also:
    
    getVertexUniqueEdges(boolean)
  - getVertexUniqueEdges
```
public List getVertexUniqueEdges(boolean includeFrame)
```
    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.
    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(boolean) and then locating quadedges attached to them.
    
    Parameters:
    
    includeFrame - true if the frame vertices should be included
    
    Returns:
    
    a collection of QuadEdge with the vertices of the subdivision as their origins
  - getPrimaryEdges
```
public List getPrimaryEdges(boolean includeFrame)
```
    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.
    
    Parameters:
    
    includeFrame - true if the frame edges are to be included
    
    Returns:
    
    a List of QuadEdges
  - visitTriangles
```
public void visitTriangles(TriangleVisitor triVisitor,
                           boolean includeFrame)
```
    Visitors
  - getTriangleEdges
```
public List getTriangleEdges(boolean includeFrame)
```
    Gets a list of the triangles in the subdivision, specified as an array of the primary quadedges around the triangle.
    
    Parameters:
    
    includeFrame - true if the frame triangles should be included
    
    Returns:
    
    a List of QuadEdge[3] arrays
  - getTriangleVertices
```
public List getTriangleVertices(boolean includeFrame)
```
    Gets a list of the triangles in the subdivision, specified as an array of the triangle Vertexes.
    
    Parameters:
    
    includeFrame - true if the frame triangles should be included
    
    Returns:
    
    a List of Vertex[3] arrays
  - getTriangleCoordinates
```
public List getTriangleCoordinates(boolean includeFrame)
```
    Gets the coordinates for each triangle in the subdivision as an array.
    
    Parameters:
    
    includeFrame - true if the frame triangles should be included
    
    Returns:
    
    a list of Coordinate[4] representing each triangle
  - getEdges
```
public Geometry getEdges(GeometryFactory geomFact)
```
    Gets the geometry for the edges in the subdivision as a MultiLineString containing 2-point lines.
    
    Parameters:
    
    geomFact - the GeometryFactory to use
    
    Returns:
    
    a MultiLineString
  - getTriangles
```
public Geometry getTriangles(GeometryFactory geomFact)
```
    Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangular Polygons.
    
    Parameters:
    
    geomFact - the GeometryFactory to use
    
    Returns:
    
    a GeometryCollection of triangular Polygons
  - getVoronoiDiagram
```
public Geometry getVoronoiDiagram(GeometryFactory geomFact)
```
    Gets the cells in the Voronoi diagram for this triangulation. The cells are returned as a GeometryCollection of Polygons
    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.
    
    Parameters:
    
    geomFact - a geometry factory
    
    Returns:
    
    a GeometryCollection of Polygons
  - getVoronoiCellPolygons
```
public List getVoronoiCellPolygons(GeometryFactory geomFact)
```
    Gets a List of Polygons for the Voronoi cells of this triangulation.
    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.
    
    Parameters:
    
    geomFact - a geometry factory
    
    Returns:
    
    a List of Polygons
  - getVoronoiCellPolygon
```
public Polygon getVoronoiCellPolygon(QuadEdge qe,
                                     GeometryFactory geomFact)
```
    Gets the Voronoi cell around a site specified by the origin of a QuadEdge.
    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.
    
    Parameters:
    
    qe - a quadedge originating at the cell site
    
    geomFact - a factory for building the polygon
    
    Returns:
    
    a polygon indicating the cell extent

Class QuadEdgeSubdivision

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

QuadEdgeSubdivision

Method Detail

getTriangleEdges

getTolerance

getEnvelope

getEdges

setLocator

makeEdge

connect

delete

locateFromEdge

locate

locate

locate

insertSite

isFrameEdge

isFrameBorderEdge

isFrameVertex

isOnEdge

isVertexOfEdge

getVertices

getVertexUniqueEdges

getPrimaryEdges

visitTriangles

getTriangleEdges

getTriangleVertices

getTriangleCoordinates

getEdges

getTriangles

getVoronoiDiagram

getVoronoiCellPolygons

getVoronoiCellPolygon