Package org.tinfour.common

Interface IQuadEdge

  • All Known Implementing Classes:
    QuadEdge, SemiVirtualEdge
    public interface IQuadEdge
    Defines methods for accessing the data in a quad-edge implementation.

    Currently, Tinfour implements two kinds of quad-edge objects: standard and semi-virtual. The standard implementation (the QuadEdge class) is based on in-memory references and literal instances of objects. The semi-virtual approach attempts to reduce the amount of memory used by a Delaunay triangulation by maintaining some in-memory data in arrays rather than objects. Edge-related objects are created as needed and discarded when no long required.

    Memory considerations

    For a Delaunay triangulation with a sufficiently large number of vertices, N, the number of edges in the triangular mesh approaches 3*N. Since many of the data sets that Tinfour processes can include millions of vertices, memory management becomes an important issue. Both the standard and semi-virtual edge instances are designed to be conservative in their use of memory. This approach has a significant influence on the organization of the methods in the IQuadEdge interface. It is worth noting that, in Java, an object requires memory for its content (explicitly defined data fields) and also for object-management overhead. In many implementations of the Java Runtime Environment (JRE) running with less than 32 gigabytes of memory, this overhead is about 12 bytes. For JRE's configured with 32 gigabytes or more, that figure doubles.

    Performance considerations

    In general, get operations can be performed without any degradation of performance. However, set operations on quad-edges often require down casting (narrow casting) of object references. In ordinary applications, the performance cost of down casting is small. But for applications that require very large data sets and repeated modifications to the edge structure of the TIN, this cost can degrade processing rates by as much as 25 percent. Thus this interface avoids specifying any methods that set edge relationships (connections).

    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?.

    Tinfour supports two kinds of constraints: region (polygon) constraints, and line constraints (chains of one or more connected edges not forming a closed polygon).

    Constraint assignment to edges

    When constraint objects are added to an incremental TIN instance, Tinfour assigns each object a unique integer index (currently, in the range zero to 8190). IQuadEdge instances can store these indices for internal or application use.

    In a Delaunay triangulation, an edge is either constrained (fixed geometry) or unconstrained (free to be modified to meet the Delaunay criterion). In Tinfour, an can have some combination of the following constraint-related states:

    1. Unconstrained
    2. Border of a constrained region (polygon) or the common border of two adjacent regions (constrained)
    3. The interior of a region constraint (unconstrained)
    4. A member of a line-based constraint (constrained)

    It is possible for an edge to belong to both a region-based constraint (either as its border or its interior) and a line-based constraint. Unfortunately, memory considerations for incremental TIN construction limit the number of references to two. But an edge that is assigned both as the border of two adjacent constraint regions and an independent line constraint would require three. In such cases, the IQuadEdge instances give priority to the region specifications. Tinfour's incremental TIN classes implement logic for maintaining supplemental information so that they can track linear constraint assignments when necessary.

    • Method Detail

      • getA

        Vertex getA()
        Gets the initial vertex for this edge.
        Returns:
        a valid reference.

      • getB

        Vertex getB()
        Gets the second vertex for this edge.
        Returns:
        a valid reference or a null for a ghost edge.

      • getBaseReference

        IQuadEdge getBaseReference()
        Gets the reference to the side-zero edge of the pair.

        From the perspective of application code, the Tinfour implementations of the two elements associated with a bi-directional edge are symmetrical. Neither side of an edge is more significant than the other.

        Returns:
        a reference to the side-zero edge of the pair.

      • getDual

        IQuadEdge getDual()
        Gets the dual edge to this instance.
        Returns:
        a valid edge.

      • getForwardFromDual

        IQuadEdge getForwardFromDual()
        Gets the forward reference of the dual.
        Returns:
        a valid reference

      • getReverseFromDual

        IQuadEdge getReverseFromDual()
        Gets the reverse link of the dual.
        Returns:
        a valid reference

      • getIndex

        int getIndex()
        Gets the index value for this edge. In general, the index value is intended for memory management and edge pools. So while application code may read index values, it is not generally enabled to set them.

        In Tinfour implementations, edges are bi-directional. In effect, the edge is implemented as a pair of unidirectional elements. Each element is assigned a separate index.

        One common use for the index code by applications is to main a record of processing performed using edge-traversal operations. For example, some applications use the index to maintain a bitmap of visited edges when performing surface analysis.

        When an edge is allocated, it is set with an arbitrary index value. This value will not change while the edge remains allocated by and edge-pool instance. As soon as the edge is released, it is likely to have its index value reassigned.

        Returns:
        a positive integer value

      • getBaseIndex

        int getBaseIndex()
        Gets the index of the "base" side of a bi-directional edge. In Tinfour implementations, edges are bi-directional. In effect, the edge is implemented as a pair of unidirectional elements. Each element is assigned a separate index. The first element in the pair is designated as the "base" and is assigned an even-valued index. Its dual is assigned a value one greater than the base index. This method always returns an even value.

        This method can be useful in cases where an application needs to track a complete edge without regard to which side of the edge is being considered.

        Returns:
        a positive, even value.

      • getSide

        int getSide()
        Indicates which side of an edge a particular IQuadEdge instance is attached to. The side value is a strictly arbitrary index used for algorithms that need to be able to assign a unique index to both sides of an edge.
        Returns:
        a value of 0 or 1.

      • getLength

        double getLength()
        Gets the length of the edge.
        Returns:
        a positive floating point value

      • getLengthSq

        double getLengthSq()
        Gets the squared length of the edge.
        Returns:
        a positive floating point value

      • getForward

        IQuadEdge getForward()
        Gets the forward reference of the edge.
        Returns:
        a valid reference.

      • getReverse

        IQuadEdge getReverse()
        Gets the reverse reference of the edge.
        Returns:
        a valid reference.

      • getDualFromReverse

        IQuadEdge getDualFromReverse()
        Gets the dual of the reverse reference of the edge.
        Returns:
        a valid reference.

      • getConstraintIndex

        int getConstraintIndex()
        Gets the index of the constraint associated with this edge.
        Returns:
        a positive value; may be zero if not specified.

      • setConstraintIndex

        void setConstraintIndex​(int constraintIndex)
        Sets the constraint index for this edge. This method does not necessarily set an edge to a constrained status. In some implementations the constraint index may be used as a way of associating ordinary edges with a neighboring constraint. Constraint index values must be positive integers. The range of supported values will depend on the specific class that implements this interface. Please refer to the class documentation for specific values.
        Parameters:
        constraintIndex - a positive number indicating which constraint a particular edge is associated with.

      • isConstrained

        boolean isConstrained()
        Indicates whether an edge is constrained.
        Returns:
        true if the edge is constrained; otherwise, false.

      • isConstraintRegionMember

        boolean isConstraintRegionMember()
        Indicates whether the edge is a member of a constrained region (is in the interior or serves as the border of a polygon-based constraint). A constrained region member is not necessarily a constrained edge.
        Returns:
        true if the edge is a member of an region; otherwise false.

      • isConstraintLineMember

        boolean isConstraintLineMember()
        Indicates whether the edge is a member of a constraint line, In some cases, a constraint line member edge may lie within a constrained region but will not lie on one of its borders.
        Returns:
        true if the edge is a member of an region; otherwise false.

      • setConstraintLineMemberFlag

        void setConstraintLineMemberFlag()
        Sets the constraint-line member flag for the edge to true.

      • isConstraintRegionInterior

        boolean isConstraintRegionInterior()
        Indicates whether the edge is in the interior of a constrained region. Both sides of the edge lie within the interior of the region. All points along the edge will lie within the interior of the region with the possible exception of the endpoints. The endpoints may lie on the border of the region. An interior edge for a constrained region is not a constrained edge. Interior edges are also classified as "member" edges of a constrained region.
        Returns:
        true if the edge is in the interior of an region; otherwise false.

      • isConstraintRegionBorder

        boolean isConstraintRegionBorder()
        Indicates whether an edge represents the border of a constrained region. Border edges will always be constrained. Border edges are also classified as "member" edges of a constrained region.
        Returns:
        true if the edge is the border of the constrained region; otherwise, false.

      • setConstraintRegionBorderFlag

        void setConstraintRegionBorderFlag()
        Sets a flag indicating that the edge is an edge of a constrained region.

      • setSynthetic

        void setSynthetic​(boolean status)
        Sets the synthetic flag for the edge. Synthetic edges are those that do not arise naturally from the TIN-building logic but are created by special operations.
        Parameters:
        status - true if the edge is synthetic; otherwise, false.

      • isSynthetic

        boolean isSynthetic()
        Indicates whether the synthetic flag is set for the edge.
        Returns:
        true if the edge is synthetic; otherwise, false.

      • pinwheel

        Iterable<IQuadEdge> pinwheel()
        Gets an instance of an iterable that performs a pinwheel operation. This instance may be used in a Java for statement 
            for(IQuadEdge e: startingEdge.pinwheel()){
    }

        About the pinwheel operation: In the Tinfour library, a pinwheel operation interates over the set of edges that connect to the initial vertex of the current edge. The initial vertex is the one returned from a call to getA(). Connected vertices may be obtained through a call to getB().

        Null references for vertex:If vertex A lies on the perimeter of the Delaunay mesh, one or more of the connected edges may terminate on the "ghost vertex" which is used by Tinfour to complete the triangulation. The ghost vertex is represented by a null reference. So applications performing a pinwheel on an arbitrary edge should include logic to handle a null return from the getB() method. 

            for(IQuadEdge e: startingEdge.pinwheel()){
        Vertex B = e.getB();
        if(B == null){
             // skip processing
        }else {
             // perform processing using B
        }
    }
        Returns:
        a valid Iterable.

      • setLine2D

        @Deprecated
void setLine2D​(AffineTransform transform,
               Line2D l2d)
        Deprecated.
        A deprecated method replaced by the equivalent transcribeToLine2D().
        Parameters:
        transform - a valid affine transform
        l2d - a valid Line2D instance to receive the geometry data from the edge.

      • transcribeToLine2D

        void transcribeToLine2D​(AffineTransform transform,
                        Line2D l2d)
        Provides a convenience method for rendering edges by setting the Line2D argument with the transformed coordinates of the edge. The affine transform is used to map vertex A and B of the edge to the specified coordinate system. The transformed coordinates are then stored in the application-supplied Line2D object. If a null reference is supplied for the transform, this method treats it as the identity transform.

        This method is intended to support rendering operations that may render a large number of edges using Java's Line2D class. In such cases, this method avoids the overhead involved in creating multiple Line2D instances by allowing an application to reuse a single instance multiple times.

        Parameters:
        transform - a valid affine transform
        l2d - a valid Line2D instance to receive the geometry data from the edge.

      • setConstraintBorderIndex

        void setConstraintBorderIndex​(int constraintIndex)
        Sets a flag identifying the edge as the border of a region-based constraint and stores the index for that constraint.
        Parameters:
        constraintIndex - a positive integer in the range zero to 8190, or -1 for a null constraint.

      • setConstraintLineIndex

        void setConstraintLineIndex​(int constraintIndex)
        Sets a flag identifying the edge as the border of a line-based constraint and stores the index for that constraint.
        Parameters:
        constraintIndex - a positive integer in range zero to 8190

      • setConstraintRegionInteriorIndex

        void setConstraintRegionInteriorIndex​(int constraintIndex)
        Sets a flag identifying the edge as an interior member of a region-based constraint and stores the index for that constraint.
        Parameters:
        constraintIndex - a positive integer in the range 0 to 8190, or -1 for a null value

      • getConstraintBorderIndex

        int getConstraintBorderIndex()
        Gets the index of the region-based constraint associated with an edge that serves as part of the polygon bounding that region.
        Returns:
        a positive integer or -1 if no constraint is specified.

      • getConstraintRegionInteriorIndex

        int getConstraintRegionInteriorIndex()
        Gets the index of the region-based constraint associated with an edge contained in the interior of a constraint polygon. The edge itself is not necessarily constrained and is not part of the definition for the polygon.
        Returns:
        a positive integer or -1 if no constraint is specified.

      • getConstraintLineIndex

        int getConstraintLineIndex()
        Gets the index of a line-based constraint associated with an edge. The edge is constrained. Due to limitations of memory, the Tinfour implementation cannot support an index for an edge that happens to be a member of multiple constraints (as in the case of an edge that is also part of a border constraint).
        Returns:
        a positive integer or -1 is no constraint index is available.