Package org.locationtech.jts.triangulate

Class ConformingDelaunayTriangulator

  • public class ConformingDelaunayTriangulator
extends java.lang.Object
    Computes a Conforming Delaunay Triangulation over a set of sites and a set of linear constraints.

    A conforming Delaunay triangulation is a true Delaunay triangulation. In it each constraint segment is present as a union of one or more triangulation edges. Constraint segments may be subdivided into two or more triangulation edges by the insertion of additional sites. The additional sites are called Steiner points, and are necessary to allow the segments to be faithfully reflected in the triangulation while maintaining the Delaunay property. Another way of stating this is that in a conforming Delaunay triangulation every constraint segment will be the union of a subset of the triangulation edges (up to tolerance).

    A Conforming Delaunay triangulation is distinct from a Constrained Delaunay triangulation. A Constrained Delaunay triangulation is not necessarily fully Delaunay, and it contains the constraint segments exactly as edges of the triangulation.

    A typical usage pattern for the triangulator is: 

             ConformingDelaunayTriangulator cdt = new ConformingDelaunayTriangulator(sites, tolerance);
 
   // optional  
   cdt.setSplitPointFinder(splitPointFinder);
   cdt.setVertexFactory(vertexFactory);
   
         cdt.setConstraints(segments, new ArrayList(vertexMap.values()));
         cdt.formInitialDelaunay();
         cdt.enforceConstraints();
         subdiv = cdt.getSubdivision();

    • Constructor Detail

      • ConformingDelaunayTriangulator

        public ConformingDelaunayTriangulator​(java.util.Collection initialVertices,
                                      double tolerance)
        Creates a Conforming Delaunay Triangulation based on the given unconstrained initial vertices. The initial vertex set should not contain any vertices which appear in the constraint set.
        Parameters:
        initialVertices - a collection of ConstraintVertex
        tolerance - the distance tolerance below which points are considered identical

    • Method Detail

      • computeVertexEnvelope

        private static Envelope computeVertexEnvelope​(java.util.Collection vertices)

      • setConstraints

        public void setConstraints​(java.util.List segments,
                           java.util.List segVertices)
        Sets the constraints to be conformed to by the computed triangulation. The constraints must not contain duplicate segments (up to orientation). The unique set of vertices (as ConstraintVertexes) forming the constraints must also be supplied. Supplying it explicitly allows the ConstraintVertexes to be initialized appropriately (e.g. with external data), and avoids re-computing the unique set if it is already available.
        Parameters:
        segments - a list of the constraint Segments
        segVertices - the set of unique ConstraintVertexes referenced by the segments

      • setSplitPointFinder

        public void setSplitPointFinder​(ConstraintSplitPointFinder splitFinder)
        Sets the ConstraintSplitPointFinder to be used during constraint enforcement. Different splitting strategies may be appropriate for special situations.
        Parameters:
        splitFinder - the ConstraintSplitPointFinder to be used

      • getTolerance

        public double getTolerance()
        Gets the tolerance value used to construct the triangulation.
        Returns:
        a tolerance value

      • getVertexFactory

        public ConstraintVertexFactory getVertexFactory()
        Gets the ConstraintVertexFactory used to create new constraint vertices at split points.
        Returns:
        a new constraint vertex

      • setVertexFactory

        public void setVertexFactory​(ConstraintVertexFactory vertexFactory)
        Sets a custom ConstraintVertexFactory to be used to allow vertices carrying extra information to be created.
        Parameters:
        vertexFactory - the ConstraintVertexFactory to be used

      • getKDT

        public KdTree getKDT()
        Gets the KdTree which contains the vertices of the triangulation.
        Returns:
        a KdTree

      • getInitialVertices

        public java.util.List getInitialVertices()
        Gets the sites (vertices) used to initialize the triangulation.
        Returns:
        a List of Vertex

      • getConstraintSegments

        public java.util.Collection getConstraintSegments()
        Gets the Segments which represent the constraints.
        Returns:
        a collection of Segments

      • getConvexHull

        public Geometry getConvexHull()
        Gets the convex hull of all the sites in the triangulation, including constraint vertices. Only valid after the constraints have been enforced.
        Returns:
        the convex hull of the sites

      • computeBoundingBox

        private void computeBoundingBox()

      • computeConvexHull

        private void computeConvexHull()

      • getPointArray

        private Coordinate[] getPointArray()

      • createVertex

        private ConstraintVertex createVertex​(Coordinate p,
                                      Segment seg)
        Creates a vertex on a constraint segment
        Parameters:
        p - the location of the vertex to create
        seg - the constraint segment it lies on
        Returns:
        the new constraint vertex

      • insertSites

        private void insertSites​(java.util.Collection vertices)
        Inserts all sites in a collection
        Parameters:
        vertices - a collection of ConstraintVertex

      • insertSite

        public void insertSite​(Coordinate p)
        Inserts a site into the triangulation, maintaining the conformal Delaunay property. This can be used to further refine the triangulation if required (e.g. to approximate the medial axis of the constraints, or to improve the grading of the triangulation).
        Parameters:
        p - the location of the site to insert

      • formInitialDelaunay

        public void formInitialDelaunay()
        Computes the Delaunay triangulation of the initial sites.

      • enforceConstraints

        public void enforceConstraints()
        Enforces the supplied constraints into the triangulation.
        Throws:
        ConstraintEnforcementException - if the constraints cannot be enforced

      • addConstraintVertices

        private void addConstraintVertices()

      • enforceGabriel

        private int enforceGabriel​(java.util.Collection segsToInsert)

      • findNonGabrielPoint

        private Coordinate findNonGabrielPoint​(Segment seg)
        Given a set of points stored in the kd-tree and a line segment defined by two points in this set, finds a Coordinate in the circumcircle of the line segment, if one exists. This is called the Gabriel point - if none exists then the segment is said to have the Gabriel condition. Uses the heuristic of finding the non-Gabriel point closest to the midpoint of the segment.
        Parameters:
        p - start of the line segment
        q - end of the line segment
        Returns:
        a point which is non-Gabriel or null if no point is non-Gabriel