Package org.tinfour.edge

Class EdgePool

  • All Implemented Interfaces:
    Iterable<IQuadEdge>
    public class EdgePool
extends Object
implements Iterable<IQuadEdge>
    Provides an object-pool implementation that the manages the allocation, deletion, and reuse of Edges.

    This class is written using a very old-school approach as a way of minimizing the frequency with which objects are garbage collected. Edges are extensively allocated and freed as the TIN is built. Were they simply constructed and put out-of-scope, the resulting garbage collection could degrade performance.

    Note that this class is not thread safe.

    For performance reasons, many of the methods in this class make the assumption that any edges passed into the method are under the management of the current instance. If this assumption is violated, serious errors could occur. For example, if an application uses one edge pool to allocate an edge and then passes it to the deallocEdge method another edge pool instance, both instances could become seriously corrupted.

    • Constructor Detail

      • EdgePool

        public EdgePool()
        Construct a QuadEdge manager allocating a small number of initial edges.

    • Method Detail

      • preAllocateEdges

        public void preAllocateEdges​(int n)
        Pre-allocates the specified number of edges. For a Delaunay Triangulation with n vertices, there should be 3*n edges.
        Parameters:
        n - the number of edge (not vertices) to be allocated.

      • allocateEdge

        public QuadEdge allocateEdge​(Vertex a,
                             Vertex b)
        Allocates an edge with the specified vertices.
        Parameters:
        a - a valid instance.
        b - a valid instance or a null in the event of a ghost edge.
        Returns:
        a valid edge instance.

      • deallocateEdge

        public void deallocateEdge​(QuadEdge e)
        Deallocates the QuadEdge returning it to the QuadEdge pool.
        Parameters:
        e - a valid QuadEdge

      • size

        public int size()
        Get the number of Edges currently stored in the collection
        Returns:
        an integer value of zero or more

      • getStartingEdge

        public QuadEdge getStartingEdge()
        Get first valid, non-ghost QuadEdge in collection
        Returns:
        for a non-empty collection, a valid QuadEdge; otherwise a null

      • getStartingGhostEdge

        public QuadEdge getStartingGhostEdge()
        Gets a ghost edge to be used as a starting edge in a search operation
        Returns:
        a valid edge.

      • getEdgeForIndex

        public IQuadEdge getEdgeForIndex​(int index)
        Gets the edge associated with the specified index, if any. If the index value is out of range, or if the associated edge has been deallocated, this method returns a null reference.
        Parameters:
        index - a positive integer value less than or equal to the maximum allocation index for edges.
        Returns:
        if an edge with a matching index exists, a valid reference; otherwise, a null.

      • getEdges

        public List<IQuadEdge> getEdges()
        Get a list of the Edges currently stored in the collection
        Returns:
        a valid, potentially empty list of edges

      • getEdgeCount

        public int getEdgeCount()
        Gets the number of edges currently allocated by the edge pool. Free edges (those previously allocated and then freed) are not included in the count.
        Returns:
        a positive integer value, potentially zero.

      • dispose

        public void dispose()
        Puts all references used in the collection out-of-scope as a way of simplifying and expediting garbage collection.

      • clear

        public void clear()
        Deallocates all Edges, returning them to the free list. Does not delete any existing objects.

      • printDiagnostics

        public void printDiagnostics​(PrintStream ps)
        Prints diagnostic information about the manager to the specified print stream.
        Parameters:
        ps - a valid print stream.

      • getIterator

        public Iterator<IQuadEdge> getIterator​(boolean includeGhostEdges,
                                       boolean produceDualEdges)
        Constructs an iterator that will optionally skip ghost edges.
        Parameters:
        includeGhostEdges - indicates that ghost edges are to be included in the iterator production.
        produceDualEdges - indicates that both the base and dual edges are to be produced.
        Returns:
        a valid instance of an iterator

      • getMaximumAllocationIndex

        public int getMaximumAllocationIndex()
        Gets the maximum value of an edge index that is currently allocated within the edge pool.
        Returns:
        a positive number or zero if the pool is currently unallocated.

      • splitEdge

        public QuadEdge splitEdge​(QuadEdge e,
                          Vertex m)
        Split the edge e into two by inserting a new vertex m into the edge. The insertion point does not necessarily have to lie on the segment. This method splits the segment into two segments so that edge e(a,b) becomes edges p(a,m) and and e(m,b), with forward and reverse links for both segments being adjusted accordingly. The new segment p(a,m) is returned and the input segment e is adjusted with new vertices (m,b).

        The split edge method preserves constraint flags and other attributes associated with the edge.

        Parameters:
        e - the input segment
        m - the insertion vertex
        Returns:
        a valid instance of a QuadEdge or QuadEdgePartner (depending on the class of the input)

      • addLinearConstraintToMap

        public void addLinearConstraintToMap​(IQuadEdge edge,
                                     IConstraint constraint)
        Adds the specified constraint to the linear constraint map, thus recording which constraint lies to the left side of the edge.
        Parameters:
        edge - a valid edge instance
        constraint - a valid constraint instance

      • getLinearConstraint

        public IConstraint getLinearConstraint​(IQuadEdge edge)
        Gets the linear constraint associated with the edge, if any.
        Parameters:
        edge - a valid edge instance.
        Returns:
        if a linear constraint is associated with the edge, a valid instance; otherwise, a null.