Class: QuadEdgeSubdivision

jsts.triangulate.quadedge.QuadEdgeSubdivision

new QuadEdgeSubdivision(env, 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:
Name Type Description
env the bouding box to surround.
tolerance the tolerance value for determining if two sites are equal.
Source:

Methods

(static) getTriangleEdges(startQE, triEdge)

Gets the edges for the triangle to the left of the given QuadEdge.
Parameters:
Name Type Description
startQE jsts.triangulate.quadedge.QuadEdge the starting quad-edge.
triEdge Array.<jsts.triangulate.quadedge.QuadEdge> array of quadedges.
Source:
Throws:
IllegalArgumentException if the edges do not form a triangle

connect(a, b) → {jsts.triangulate.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.
Parameters:
Name Type Description
a jsts.triangulate.quadedge.QuadEdge The first quadedge.
b jsts.triangulate.quadedge.QuadEdge The second quadedge.
Source:
Returns:
Type
jsts.triangulate.quadedge.QuadEdge

createFrame(env)

Creates the framing envelope
Parameters:
Name Type Description
env jsts.geom.Envelope an envelope.
Source:

delete_jsts(e)

Deletes a quadedge from the subdivision. Linked quadedges are updated to reflect the deletion.
Parameters:
Name Type Description
e jsts.triangulate.quadedge.QuadEdge the quadedge to delete.
Source:

fetchTriangleToVisit(edge, edgeStack, includeFrame, visitedEdges) → {Array.<jsts.triangulate.quadedge.QuadEdge>}

Stores the edges for a visited triangle. Also pushes sym (neighbour) edges on stack to visit later.
Parameters:
Name Type Description
edge jsts.triangulate.quadedge.QuadEdge the quadedge.
edgeStack Array.<jsts.triangulate.quadedge.QuadEdge> an array used as a stack.
includeFrame boolean true to include frame.
visitedEdges Array.<jsts.traingulate.quadedge.QuadEdge> the edges that are already visited.
Source:
Returns:
the visited triangle edges or null if the triangle should not be visited.
Type
Array.<jsts.triangulate.quadedge.QuadEdge>

getEdges() → {Array.<jsts.triangulate.quadedge.QuadEdge>}

Gets the collection of base Quadedges (one for every pair of vertices which is connected).
Source:
Returns:
a collection of QuadEdges.
Type
Array.<jsts.triangulate.quadedge.QuadEdge>

getEdgesByFactory(geomFact) → {jsts.geom.Geometry}

Gets the geometry for the edges in the subdivision as a MultiLineString containing 2-point lines.
Parameters:
Name Type Description
geomFact jsts.geom.GeometryFactory the GeometryFactory to use.
Source:
Returns:
a MultiLineString.
Type
jsts.geom.Geometry

getEnvelope() → {jsts.geom.Envelope}

Gets the envelope of the Subdivision (including the frame).
Source:
Returns:
the envelope.
Type
jsts.geom.Envelope

getPrimaryEdges(includeFrame) → {Array.<jsts.triangulate.quadedge.QuadEdge>}

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:
Name Type Description
includeFrame boolean true if the frame edges are to be included.
Source:
Returns:
a List of QuadEdges.
Type
Array.<jsts.triangulate.quadedge.QuadEdge>

getTolerance() → {Number}

Gets the vertex-equality tolerance value used in this subdivision
Source:
Returns:
the tolerance value.
Type
Number

getTriangleCoordinates(includeFrame) → {Array.<Array.<jsts.geom.Coordinate>>}

Gets the coordinates for each triangle in the subdivision as an array.
Parameters:
Name Type Description
includeFrame boolean true if the frame triangles should be included.
Source:
Returns:
a list of Coordinate[4] representing each triangle.
Type
Array.<Array.<jsts.geom.Coordinate>>

getTriangleEdges(includeFrame) → {Array.<jsts.triangulate.quadedge.QuadEdge>}

Gets a list of the triangles in the subdivision, specified as an array of the primary quadedges around the triangle.
Parameters:
Name Type Description
includeFrame true if the frame triangles should be included.
Source:
Returns:
a List of QuadEdge[3] arrays.
Type
Array.<jsts.triangulate.quadedge.QuadEdge>

getTriangles(geomFact) → {jsts.geom.Geometry}

Gets the geometry for the triangles in a triangulated subdivision as a GeometryCollection of triangular Polygons.
Parameters:
Name Type Description
geomFact jsts.geom.GeometryFactory the GeometryFactory to use.
Source:
Returns:
a GeometryCollection of triangular Polygons.
Type
jsts.geom.Geometry

getTriangleVertices(includeFrame) → {Array.<Array.<jsts.triangulate.quadedge.Vertex>>}

Gets a list of the triangles in the subdivision, specified as an array of the triangle Vertexes.
Parameters:
Name Type Description
includeFrame boolean true if the frame triangles should be included.
Source:
Returns:
a List of Vertex[3] arrays.
Type
Array.<Array.<jsts.triangulate.quadedge.Vertex>>

getVertexUniqueEdges(includeFrame) → {Array.<jsts.triangulate.quadedge.QuadEdge>}

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 and then locating quadedges attached to them.

Parameters:
Name Type Description
includeFrame boolean true if the frame vertices should be included.
Source:
Returns:
a collection of QuadEdge with the vertices of the subdivision as their origins.
Type
Array.<jsts.triangulate.quadedge.QuadEdge>

getVertices(includeFrame) → {Array.<jsts.triangulate.quadedge.Vertex>

Gets the unique Vertexes in the subdivision, including the frame vertices if desired.
Parameters:
Name Type Description
includeFrame boolean true if the frame vertices should be included.
Source:
See:
Returns:
an array of the subdivision vertices.
Type
Array.<jsts.triangulate.quadedge.Vertex>

getVoronoiCellPolygon(qe, geomFact) → {jsts.geom.Polygon}

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

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

Parameters:
Name Type Description
qe jsts.triangulate.quadedge.QuadEdge a quadedge originating at the cell site.
geomFact jsts.geom.GeometryFactory a factory for building the polygon.
Source:
Returns:
a polygon indicating the cell extent.
Type
jsts.geom.Polygon

getVoronoiCellPolygons(geomFact) → {Array.<jsts.geom.Polygon>

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

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

Parameters:
Name Type Description
geomFact jsts.geom.GeometryFactory a geometry factory.
Source:
Returns:
an array of Polygons.
Type
Array.<jsts.geom.Polygon>

getVoronoiDiagram(geomFact) → {jsts.geom.Geometry

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 of the cell site. This allows easily associating external data associated with the sites to the cells.

Parameters:
Name Type Description
geomFact jsts.geom.GeometryFactory a geometry factory.
Source:
Returns:
a GeometryCollection of Polygons.
Type
jsts.geom.Geometry

initSubdiv() → {jsts.geom.triangulate.quadedge.QuadEdge

Source:
Returns:
The quadedge.
Type
jsts.geom.triangulate.quadedge.QuadEdge

insertSite(v) → {jsts.triangulate.quadedge.QuadEdge}

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:
Name Type Description
v jsts.triangulate.quadedge.Vertex the vertex to insert.
Source:
Returns:
a new quad edge terminating in v.
Type
jsts.triangulate.quadedge.QuadEdge

isFrameBorderEdge(e) → {boolean}

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:
Name Type Description
e jsts.triangulate.quadedge.QuadEdge the edge to test.
Source:
Returns:
true if the edge is on the border of the frame.
Type
boolean

isFrameEdge(e) → {boolean}

Tests whether a QuadEdge is an edge incident on a frame triangle vertex.
Parameters:
Name Type Description
e jsts.triangulate.quadedge.QuadEdge the edge to test.
Source:
Returns:
true if the edge is connected to the frame triangle.
Type
boolean

isFrameVertex(v) → {boolean}

Tests whether a vertex is a vertex of the outer triangle.
Parameters:
Name Type Description
v jsts.triangulate.quadedge.Vertex the vertex to test.
Source:
Returns:
true if the vertex is an outer triangle vertex.
Type
boolean

isOnEdge(e, p) → {boolean}

Tests whether a Coordinate lies on a QuadEdge, up to a tolerance determined by the subdivision tolerance.
Parameters:
Name Type Description
e jsts.triangulate.quadedge.QuadEdge a QuadEdge.
p jsts.geom.Coordinate a point.
Source:
Returns:
true if the vertex lies on the edge.
Type
boolean

isVertexOfEdge(e, v) → {boolean}

Tests whether a Vertex is the start or end vertex of a QuadEdge, up to the subdivision tolerance distance.
Parameters:
Name Type Description
e jsts.triangulate.quadedge.QuadEdge the quadedge to test.
v jsts.triangulate.quadedge.Vertex the vertex to test.
Source:
Returns:
true if the vertex is a endpoint of the edge.
Type
boolean

locate()

Locates a quadedge Will call correct locate* -function based on arguments
Source:

locateByCoordinate(p) → {jsts.triangulate.quadedge.QuadEdge}

Finds a quadedge of a triangle containing a location specified by a Coordinate, if one exists.
Parameters:
Name Type Description
p jsts.geom.Coordinate the Coordinate to locate.
Source:
Returns:
a quadedge on the edge of a triangle which touches or contains the location or null if no such triangle exists.
Type
jsts.triangulate.quadedge.QuadEdge

locateByCoordinates(p0, p1) → {jsts.triangulate.quadedge.QuadEdge}

Locates the edge between the given vertices, if it exists in the subdivision.
Parameters:
Name Type Description
p0 jsts.geom.Coordinate a coordinate.
p1 jsts.geom.Coordinate another coordinate.
Source:
Returns:
the edge joining the coordinates, if present, null if no such edge exists.
Type
jsts.triangulate.quadedge.QuadEdge

locateByVertex(x) → {jsts.triangulate.quadedge.QuadEdge}

Finds a quadedge of a triangle containing a location specified by a Vertex, if one exists.
Parameters:
Name Type Description
x jsts.triangulate.quadedge.Vertex the vertex to locate.
Source:
Returns:
a quadedge on the edge of a triangle which touches or contains the location, null of no such triangle exists.
Type
jsts.triangulate.quadedge.QuadEdge

locateFromEdge(v, startEdge) → {jsts.triangulate.quadedge.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.

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

Parameters:
Name Type Description
v jsts.triangulate.quadedge.Vertex the location to search for.
startEdge jsts.triangulate.quadedge.QuadEdge an edge of the subdivision to start searching at.
Source:
Throws:
jsts.error.LocateFailureError if the location algorithm fails to converge in a reasonable number of iterations
Returns:
a QuadEdge which contains v, or is on the edge of a triangle containing v.
Type
jsts.triangulate.quadedge.QuadEdge

makeEdge(o, d) → {jsts.triangulate.quadedge.QuadEdge}

Creates a new quadedge, recording it in the edges list.
Parameters:
Name Type Description
o jsts.triangulate.quadedge.Vertex a Vertex.
d jsts.triangulate.quadedge.Vertex another Vertex.
Source:
Returns:
Type
jsts.triangulate.quadedge.QuadEdge

setLocator(locator)

Sets the QuadEdgeLocator to use for locating containing triangles in this subdivision.
Parameters:
Name Type Description
locator jsts.triangulate.quadedge.QuadEdgeLocator a QuadEdgeLocator.
Source:

visitTriangles(triVisitor, includeFrame)

Visits all quadedges with the specified visitor.
Parameters:
Name Type Description
triVisitor jsts.triangulate.TriangleVisitor the visitor to use.
includeFrame boolean true to include frame-edges.
Source: