Package org.tinfour.common

Interface IIncrementalTin

  • All Known Implementing Classes:
    IncrementalTin, SemiVirtualIncrementalTin
    public interface IIncrementalTin
    Defines the primary methods used by an incremental TIN implementation.

    Implementations Currently, the Tinfour software library includes two implementations of this interface: IncrementalTin in the package org.tinfour.standard, and SemiVirtualIncrementalTin in the package org.tinfour.semivirtual. The two classes produce nearly identical output data. The standard IncrementalTin implementation is faster and simpler than its counterpart, but the semi-virtual implementation reduces memory use by a factor of two. Under Java, IncrementalTin requires approximately 244 bytes per vertex while the semi-virtual form requires about 120.

    The main difference between the two implementations is that standard incremental-TIN implementation represents each edge as an explicitly constructed pair of objects (using the QuadEdge class) while the semi-virtual implementation stores the raw data for vertices in memory and constructs edge objects on-the-fly (using the SemiVirtualEdge class). The semi-virtual approach has some processing overhead in that each time an edge is required, it must be constructed and then allowed to go out-of-scope. This approach results in about a 30 percent reduction in the speed at which vertices can be added to the TIN. But by relying on short-persistence edge objects, the semi-virtual class reduces the number of objects kept in memory and the overall memory use. The standard implementation classes uses about 7.005 objects per vertex (including vertices, edges, and collections for management), while the semi-virtual implementation uses about persistent 1.012 objects per vertex.

    Usage Notes

    Purpose of this Interface The intended purpose of this interface is to allow application code to use the two classes interchangeably. Applications may select which implementation is constructed at run-time based on the size of their input data sets.

    Multi-Threading and Concurrency The process of creating a Delaunay Triangulation (TIN) using an incremental-insertion technique is inherently serial. Therefore, application code that creates a TIN should not attempt to access the "add" methods for this interface in parallel threads. However, this API is designed so that once a TIN is complete, it can be accessed by multiple threads on a read-only basis. Multi-threaded access is particularly useful when performing surface-interpolation operations to construct raster (grid) representations of data.

    Constraints and constrained edges Normally, Tinfour is free to choose the geometry of the edges in a triangular mesh based on the Delaunay criterion. But some applications require that certain edges be preserved as specified. Therefore, Tinfour supports the specification of constraint objects to create a Constrained Delaunay Triangulations (CDT). Background information on the CDT is provided at the Tinfour project web article What is the Constrained Delaunay Triangulation and why would you care?.

    • Method Detail

      • clear

        void clear()
        Clears all internal state data of the TIN, preparing any allocated resources for re-use. When processing multiple sets of input data the clear() method has an advantage in that it can be used to reduce the overhead related to multiple edge object implementation.

      • countTriangles

        TriangleCount countTriangles()
        Performs a survey of the TIN to gather statistics about the triangles formed during its construction.
        Returns:
        A valid instance of the TriangleCount class.

      • dispose

        void dispose()
        Nullifies all internal data and references, preparing the instance for garbage collection. Because of the complex relationships between objects in a TIN, Java garbage collection may require an above average number of passes to clean up memory when an instance of this class goes out-of-scope. The dispose() method can be used to expedite garbage collection. Do not confuse the dispose() method with the clear() method. The clear() method prepares a TIN instance for reuse. The dispose() method prepares a TIN instance for garbage collection. Once the dispose() method is called on a TIN, it cannot be reused.

      • getBounds

        Rectangle2D getBounds()
        Gets the bounds of the TIN. If the TIN is not initialized (bootstrapped), this method returns a null.
        Returns:
        if available, a valid rectangle giving the bounds of the TIN; otherwise, a null

      • getEdges

        List<IQuadEdge> getEdges()
        Gets a list of edges currently allocated by an instance. The list may be empty if the TIN is not initialized (bootstrapped).

        Warning: For efficiency purposes, the edges return by this routine are the same objects as those currently being used in the instance. Any modification of the edge objects will damage the TIN. Therefore, applications must not modify the edges returned by this method.

        Returns:
        a valid, potentially empty list.

      • getEdgeIterator

        Iterator<IQuadEdge> getEdgeIterator()
        Gets an iterator for stepping through the collection of edges currently stored in the TIN.

        Note that this loop produces only the "base side" of each edge. To access the counterpart (the side of the edge in the other direction), an application needs to access its dual using the edge's getDual() method.

        Warning: For efficiency purposes, the edges returned by this routine are the same objects as those currently being used in the instance. Any modification of the edge objects will damage the TIN. Therefore, applications must not modify the edges returned by this method. Caution: For reasons of efficiency, the iterator does not offer any protection against concurrent modification. Therefore applications using this iterator must never modify the TIN during iteration.

        Returns:
        a valid iterator.

      • edges

        Iterable<IQuadEdge> edges()
        Provides a convenience implementation that can be used with a Java enhanced-loop statement to access the set of edges that form the structure of the incremental TIN. The edges produced by this Iterator are filtered so that the fictitious edges (ghost edges) are not produced by the iteration.

        For example, this method could be used in the following manner: 

             IIncremntal tin = // some implementation
     for(IQuadEdge e: tin.edges(){
            // some processing logic
     }

        Note that this loop produces only the "base side" of each edge. To access the counterpart (the side of the edge in the other direction), an application needs to access its dual using the edge's getDual() method.

        Please see the API documentation for getEdgeIterator() for cautions regarding the use of this method.

        Returns:
        a valid instance.

      • edgesAndDuals

        Iterable<IQuadEdge> edgesAndDuals()
        Provides a convenience implementation that can be used with a Java enhanced-loop statement to access both sides of each edge in the incremental TIN. This method is similar to the edges() iterator except that it produces both sides of each edge. The edges produced by this Iterator are filtered so that the fictitious edges (ghost edges) are not produced by the iteration.

        For example, this method could be used in the following manner: 

             IIncremntal tin = // some implementation
     for(IQuadEdge e: tin.halfEdges(){
            // some processing logic
     }

        Note that this loop produces both the "base side" and the "dual" of each edge.

        Please see the API documentation for getEdgeIterator() for cautions regarding the use of this method.

        Returns:
        a valid instance.

      • triangles

        Iterable<SimpleTriangle> triangles()
        Provides a convenience implementation that can be used with a Java enhanced-loop statement to access the set of SimpleTriangles implicit in the structure of the incremental TIN. This iterable will produce all SimpleTriangles in the collection with no repeats or omissions.

        For example, this method could be used in the following manner: 

             IIncremntal tin = // a valid instance
     for(SimpleTriangle t: tin.triangles(){
            // some processing logic
     }

        Please see the API documentation for SimpleTriangleIterator for cautions regarding the use of this method.

        Returns:
        a valid instance.

      • getMaximumEdgeAllocationIndex

        int getMaximumEdgeAllocationIndex()
        Gets the maximum index of the currently allocated edges. This method can be used in support of applications that require the need to survey the edge set and maintain a parallel array or collection instance that tracks information about the edges. In such cases, the maximum edge index provides a way of knowing how large to size the array or collection.

        Internally, Tinfour uses edge index values to manage edges in memory. The while there can be small gaps in the indexing sequence, this method provides a way of obtaining the absolute maximum value of currently allocated edges.

        Returns:
        a positive value or zero if the TIN is not bootstrapped.

      • getNominalPointSpacing

        double getNominalPointSpacing()
        Gets the nominal point spacing used to determine numerical thresholds for various proximity and inclusion tests. For best results, it should be within one to two orders of magnitude of the actual value for the samples. In practice, this value is usually chosen to be close to the mean point spacing for a sample. But for samples with varying density, a mean value from the set of smaller point spacings may be used.

        Lidar applications sometimes refer to the point-spacing concept as "nominal pulse spacing", a term that reflects the origin of the data in a laser-based measuring system.

        Returns:
        a positive floating-point value greater than zero.

      • getThresholds

        Thresholds getThresholds()
        Gets the Thresholds object that is associated with this instance. Because all elements in Thresholds are declared final (immutable), it can be shared safely between multiple threads or other classes.
        Returns:
        a valid instance

      • getPerimeter

        List<IQuadEdge> getPerimeter()
        Gets a list of edges currently defining the perimeter of the TIN. The list may be empty if the TIN is not initialized (bootstrapped).

        Warning: For efficiency purposes, the edges return by this routine are the same objects as those currently being used in the instance. Any modification of the edge objects will damage the TIN. Therefore, applications must not modify the edges returned by this method.

        Returns:
        a valid, potentially empty list.

      • getNeighborEdgeLocator

        INeighborEdgeLocator getNeighborEdgeLocator()
        Gets a new instance of the INeighborEdgeLocator interface. Instances observe the contract of the IProcessUsingTin interface in that they access the TIN on a read-only basis and may be used in parallel threads provided that the TIN is not modified.

        This method is obsolete. Use getNavigator instead.

        Returns:
        an edge locator tied to this TIN.

      • getNavigator

        IIncrementalTinNavigator getNavigator()
        Gets a new instance of the IIncrementalTinNavigator interface. The navigator implementations provide utilities to perform geometry-based queries on the TIN. These queries include tests to see if a coordinate point lies within the TIN, tests to get neighboring edges, etc.

        Instances observe the contract of the IProcessUsingTin interface in that they access the TIN on a read-only basis and may be used in parallel threads provided that the TIN is not modified.

        Returns:
        an valid navigator instance or a null if the TIN is not properly bootstrapped.

      • getNeighborhoodPointsCollector

        INeighborhoodPointsCollector getNeighborhoodPointsCollector()
        Gets a new instance of a neighborhood points collector. Instances observe the contract of the IProcessUsingTin interface in that they access the TIN on a readonly basis and may be used in parallel threads provided that the TIN is not modified.
        Returns:
        an points collector tied to this TIN.

      • getIntegrityCheck

        IIntegrityCheck getIntegrityCheck()
        Gets an implementation of the integrity check interface suitable for the referenced TIN implementation.
        Returns:
        a valid integrity check implementation.

      • add

        boolean add​(Vertex v)
        Insert a vertex into the collection of vertices managed by the TIN. If the TIN is not yet bootstrapped, the vertex will be retained in a simple list until enough vertices are received in order to bootstrap the TIN.
        Parameters:
        v - a valid vertex
        Returns:
        true if the TIN is bootstrapped; otherwise false

      • add

        boolean add​(List<Vertex> list,
            IMonitorWithCancellation monitor)
        Inserts a list of vertices into the collection of vertices managed by the TIN. If the TIN is not yet bootstrapped, the vertices will be retained in a simple list until enough vertices are received in order to bootstrap the TIN.

        Performance Consideration Related to List In the bootstrap phase, three points are chosen at random from the vertex list to create the initial triangle for insertion. In the event that the three points are not a suitable choice (as when they are collinear or nearly collinear), the process will be repeated until a valid initial triangle is selected. Thus, there is a small performance advantage in supplying the vertices using a list that can be accessed efficiently in a random order (see the discussion of the Java API for the List and java.util.RandomAccess interfaces). Once the initial triangle is established, the list will be traversed sequentially to build the TIN and random access considerations will no longer apply.

        Performance Consideration Related to Location of Vertices The performance of the insertion process is sensitive to the relative location of vertices. An input data set based on purely random vertex positions represents one of the worst-case input sets in terms of processing time.

        Ordinarily, the most computationally expensive operation for inserting a vertex into the Delaunay triangulation is locating the triangle that contains its coordinates. But Tinfour implements logic to expedite this search operation by taking advantage of a characteristic that occurs in many data sets: the location of one vertex in a sequence is usually close to the location of the vertex that preceded it. By starting each search at the position in the triangulation where a vertex was most recently inserted, the time-to-search can be reduced dramatically. Unfortunately, in vertices generated by a random process, this assumption of sequential proximity (i.e. "spatial autocorrelation") is not true.

        To assist in the case of random or poorly correlated vertex geometries, application can take advantage of the HilbertSort class which is supplied as part of the Core Tinfour module. In the example shown below, the use of the HilbertSort yields a factor of 100 improvement in the time to perform the .add() method. 

              int nVertices = 1_000_000;
      List<Vertex> vertices = new ArrayList<>();
      for (int i = 0; i < nVertices; i++) {
        double x = Math.random() * 1000;
        double y = Math.random() * 1000;
        vertices.add(new Vertex(x, y, 0));
      }

      HilbertSort hs = new HilbertSort();
      hs.sort(vertices);
      IIncrementalTin tin = new IncrementalTin();
      tin.add(vertices, null);
        Parameters:
        list - a valid list of vertices to be added to the TIN.
        monitor - an optional monitoring implementation; null if not used.
        Returns:
        true if the TIN is bootstrapped; otherwise false

      • preAllocateEdges

        void preAllocateEdges​(int nVertices)
        Allocates a number of vertices roughly sufficient to represent a TIN containing the specified number of vertices. This method also serves as a diagnostic tool, allowing a test-application to separate the portion of processing time consumed by Java object construction from that spent on processing the vertex data.
        Parameters:
        nVertices - the number of vertices expected to be added to the TIN.

      • printDiagnostics

        void printDiagnostics​(PrintStream ps)
        Print statistics and diagnostic information collected during the TIN construction process. This information will be removed and reset by a call to the clear() method.
        Parameters:
        ps - A valid instance of a PrintStream to receive the output.

      • getVertices

        List<Vertex> getVertices()
        Gets a list of vertices currently stored in the TIN. This list of objects is not necessarily equivalent to the set of objects that were input because some vertices may have been incorporated into one or more vertex-merger groups. Note that the list of vertices is not sorted and will usually not be returned in the same order as the original input set.

        Note: For efficiency purposes, the vertices return by this routine are the same objects as those currently being used in the instance. The index and "reserved" elements of the Vertex class are not used by the TIN and may be modified by application code as required. However, the geometry related fields must not be modified once a vertex is added to a TIN.

        Returns:
        a valid list of vertices, potentially empty if the TIN has not been initialized.

      • isBootstrapped

        boolean isBootstrapped()
        Indicates whether the instance contains sufficient information to represent a TIN. Bootstrapping requires the input of at least three distinct, non-collinear vertices. If the TIN is not bootstrapped methods that access its content may return empty or null results.
        Returns:
        true if the TIN is successfully initialized; otherwise, false.

      • isConformant

        boolean isConformant()
        Indicates whether the triangulated mesh conforms to the Delaunay criterion. This value is set to true when the triangulated irregular network (TIN) is successfully bootstrapped. This value is set to false when constraints are added to the mesh without the restore-conformity option being enabled.
        Returns:
        true if the TIN conforms to the Delaunay criterion; otherwise, false.

      • printEdges

        void printEdges​(PrintStream ps)
        Provides a diagnostic print out of the edges comprising the TIN.
        Parameters:
        ps - A valid print stream.

      • remove

        boolean remove​(Vertex vRemove)
        Removes the specified vertex from the TIN. If the vertex is part of a merged-group, it is removed from the group by the structure of the TIN is unchanged.

        At this time, vertices cannot be removed from the TIN if constraints are in place. When constraints are added to the TIN, the instance is assumed to be "locked" with regard to vertex removal. This behavior is a limitation of the current implementation and may be revised in future releases.

        Parameters:
        vRemove - the vertex to be removed
        Returns:
        true if the vertex was found in the TIN and removed.

      • setResolutionRuleForMergedVertices

        void setResolutionRuleForMergedVertices​(VertexMergerGroup.ResolutionRule resolutionRule)
        Specifies a rule for interpreting the Z value of a group of vertices that were merged due to being coincident, or nearly coincident.
        Parameters:
        resolutionRule - The rule to be used for interpreting merged vertices.

      • addConstraints

        void addConstraints​(List<IConstraint> constraints,
                    boolean restoreConformity)
        Adds constraints to the TIN.

        Using Constraints

        There are a number of important restrictions to the use of constraints. Constraints must only be added to the TIN once, preferably after non-constraint vertices have already been added. Furthermore, the addConstraint method can only be called once. Logic is implemented as a safety measure to ensure that these restrictions are not accidentally violated.

        There are also important restrictions on the geometry of constraints. Most importantly, constraints must never intersect each other except at the endpoints of the segments that define them (i.e. segments in constraints must never cross each other). Due to the high cost of processing required to check that this restriction is observed, it is not directly enforced by the Tinfour implementations.

        Finally, there is a limit to the number of constraint objects that can be added to the incremental TIN. At this time, the total number of constraint objects is limited to 8190 (2^13-2). A constraint object may contain multiple edges, so the total number of edges is only limited by available memory and processing time. The reason for this restriction is that Tinfour attempts to conserve the amount of memory dedicated to edges and allows only a single 32-bit integer to store constraint references and state data.

        Restoring Conformity

        When constraints are added to a Delaunay triangulation, they often violate the Delaunay criterion and result in a non-conforming mesh. The addConstraint method can optionally restore conformity by inserting synthetic points into the the constraint edges. The cost of this process is additional processing time and an increase in the number of points in the TIN.

        When points are synthesized, it is necessary to interpolate a value for the z-coordinate. At this time, the specific interpolation process is undefined. The current Tinfour implementations use linear interpolation between constraint points. While no viable alternative approach is currently under consideration, the choice of interpolation method is subject to change in the future.

        Parameters:
        constraints - a valid, potentially empty list.
        restoreConformity - restores conformity
        Throws:
        InsufficientConstraintGeometryException - if the input vertices and constraints are insufficient to establish a planar coordinate system.

      • getConstraints

        List<IConstraint> getConstraints()
        Gets a shallow copy of the list of constraints currently stored in the TIN.
        Returns:
        a valid, potentially empty list of constraint instances.

      • getConstraint

        IConstraint getConstraint​(int index)
        Gets the constraint associated with the index, or a null if no such constraint exists. Note that there is no out-of-bounds range for the input index. An invalid index simply yields a null reference.
        Parameters:
        index - an arbitrary integer index
        Returns:
        if found, a valid constraint; otherwise a null.

      • getSyntheticVertexCount

        int getSyntheticVertexCount()
        Gets the number of synthetic vertices added to the TIN. Vertices can be synthesized as part of the Delaunay restoration process when adding constraints. Future implementations of additional functions (such as Delaunay refinement) may also add synthetic points.
        Returns:
        a positive integer, potentially zero.

      • splitEdge

        @Deprecated
Vertex splitEdge​(IQuadEdge eInput,
                 double t,
                 double zSplit,
                 boolean restoreConformity)
        Deprecated.
        Splits an existing edge into two at parametric position t measured from the edge’s origin (A) toward its destination (B).

        The inserted vertex inherits the constraint status of the edge; if the input edge is constrained, the new vertex is marked as a constraint vertex and the edge is subdivided into two constrained edges.

        Implementations may clamp t to an open interval (ε, 1−ε) to avoid creation of zero-length subedges. The z coordinate of the inserted vertex is taken from the supplied zSplit. If an implementation does not support restoring Delaunay conformance at split time, the restoreConformity flag may be ignored.

        Parameters:
        eInput - a valid edge belonging to this TIN instance
        t - the split parameter in [0,1], measured from A toward B; values at or near the endpoints may be clamped by the implementation
        zSplit - the z coordinate for the new vertex
        restoreConformity - obsolete, no longer used
        Returns:
        the insertion vertex (never null if the split succeeds)

      • splitEdge

        Vertex splitEdge​(IQuadEdge eInput,
                 double t,
                 double zSplit)
        Splits an existing edge into two at parametric position t measured from the edge’s origin (A) toward its destination (B).

        The inserted vertex inherits the constraint status of the edge; if the input edge is constrained, the new vertex is marked as a constraint vertex and the edge is subdivided into two constrained edges.

        Implementations may clamp t to an open interval (ε, 1−ε) to avoid creation of zero-length subedges. The z coordinate of the inserted vertex is taken from the supplied zSplit. If an implementation does not support restoring Delaunay conformance at split time, the restoreConformity flag may be ignored.

        Parameters:
        eInput - a valid edge belonging to this TIN instance
        t - the split parameter in [0,1], measured from A toward B; values at or near the endpoints may be clamped by the implementation
        zSplit - the z coordinate for the new vertex
        Returns:
        the insertion vertex (never null if the split succeeds)

      • splitEdge

        default Vertex splitEdge​(IQuadEdge eInput,
                         double zSplit,
                         boolean restoreConformity)
        Split an existing edge into two at the midpoint, using the specified zSplit value as the z coordinate for the new vertex.

        WARNING The restoreConformity feature may not be implemented in all TINs.

        This default implementation delegates to splitEdge(IQuadEdge, double, double) with t = 0.5.

        Parameters:
        eInput - a valid edge
        zSplit - the z coordinate for the new vertex
        restoreConformity - restore Delaunay conformance after insertion
        Returns:
        the insertion vertex

      • getRegionConstraint

        IConstraint getRegionConstraint​(IQuadEdge edge)
        Gets the region constraint associated with the edge, if any. If the edge is on the border of a region, this method will return the constraint to its immediate left side.
        Parameters:
        edge - a valid edge instance.
        Returns:
        if a region constraint is associated with the edge, a valid instance; otherwise, a null.

      • getLinearConstraint

        IConstraint getLinearConstraint​(IQuadEdge edge)
        Gets the linear constraint associated with the edge, if any. In some cases, a linear constraint may lie within a constrained region, but it will not lie on the border of a constrained region.
        Parameters:
        edge - a valid edge instance.
        Returns:
        if a linear constraint is associated with the edge, a valid instance; otherwise, a null.

      • vertices

        Iterable<Vertex> vertices()
        Provides a convenience implementation that can be used with a Java enhanced-loop statement to access the set of vertices stored in an incremental TIN. This iterable will produce all vertices in the collection with no repeats or omissions.

        For example, this method could be used in the following manner: 

             IIncremntal tin = // a valid instance
     for(Vertex v: tin.verticess(){
            // some processing logic
     }

        Please see the API documentation for VertexIterator for cautions regarding the use of this method.

        Returns:
        a valid instance.

      • setVertexAdjustmentEnabled

        void setVertexAdjustmentEnabled​(boolean status)
        Sets an option allowing or disabling Tinfour's ability to make small adjustments in the position of a vertex when constructing a Delaunay triangulation. This option allows the triangulation to avoid cases where the input vertex set would result in undesirable characteristics. When a vertex position is adjusted, it is wrapped in an instance of the VertexAdjustment class which is stored in the triangulation.

        By default, vertex adjustments are enabled.

        At this time, Tinfour only implements one special case where an adjustment is constructed. When a vertex is inserted very close to a constrained segment, its position can be moved onto to the segment. This adjustment avoids a case where restoring Delaunay conformity would require the creation of a large number of densely spaced vertices in the neighborhood of the insertion.

        Parameters:
        status - true if adjustments are enabled; otherwise false.