Module org.dyn4j

Class DoubleEdgeList


  • final class DoubleEdgeList
    extends java.lang.Object
    Highly specialized Doubly Connected Edge List (DCEL) used to store vertices of a simple polygon and then be used to create and store triangulations and convex decompositions of that same polygon.

    Upon creation and initialization, the vertices, edges, and faces lists are populated. The vertices list will have the same indexing as the source Vector2[]. The edges list will have edges with the same indexing as the source Vector2[] with the exception that twin vertices are stored in odd indices.

    Since this implementation only handles simple polygons, only one DoubleEdgeListFace will be created when the DCEL is created. As more DoubleEdgeListHalfEdges are added the number of faces will increase.

    DoubleEdgeListHalfEdges are added to the DCEL via the addHalfEdges(DoubleEdgeListVertex, DoubleEdgeListVertex) method. It's the responsibility of the calling class(es) to store references to the DCEL vertices. This can be achieved since the indexing of the vertices list is the same as the source Vector2[]. No check is performed to ensure that a pair of DoubleEdgeListHalfEdges are added that already exist.

    Since:
    2.2.0
    Version:
    3.4.0
    Author:
    William Bittle
    • Constructor Detail

      • DoubleEdgeList

        public DoubleEdgeList​(Vector2[] points)
        Full constructor.
        Parameters:
        points - the points of the simple polygon
    • Method Detail

      • initialize

        public void initialize​(Vector2[] points)
        Initializes the DCEL class given the points of the polygon.
        Parameters:
        points - the points of the polygon
      • addHalfEdges

        public void addHalfEdges​(int i,
                                 int j)
        Adds two half edges to this DCEL object given the vertices to connect.

        This method assumes that no crossing edges will be added.

        Parameters:
        i - the first vertex index
        j - the second vertex index
      • addHalfEdges

        final void addHalfEdges​(DoubleEdgeListVertex v1,
                                DoubleEdgeListVertex v2)
        Adds two half edges to this DCEL object given the vertices to connect.

        This method assumes that no crossing edges will be added.

        Parameters:
        v1 - the first vertex
        v2 - the second vertex
      • getPreviousEdge

        final DoubleEdgeListHalfEdge getPreviousEdge​(DoubleEdgeListVertex vertex,
                                                     DoubleEdgeListFace face)
        Walks around the given face and finds the previous edge for the given vertex.

        This method assumes that the given vertex will be on the given face.

        Parameters:
        vertex - the vertex to find the previous edge for
        face - the face the edge should lie on
        Returns:
        DoubleEdgeListHalfEdge the previous edge
      • getReferenceFace

        final DoubleEdgeListFace getReferenceFace​(DoubleEdgeListVertex v1,
                                                  DoubleEdgeListVertex v2)
        Finds the face that both vertices are on.

        If the given vertices are connected then the first common face is returned.

        If the given vertices do not have a common face the first vertex's leaving edge's face is returned.

        Parameters:
        v1 - the first vertex
        v2 - the second vertex
        Returns:
        DoubleEdgeListFace the face on which both vertices lie
      • removeHalfEdges

        public void removeHalfEdges​(int index)
        Removes the half edges specified by the given interior edge index.

        This method removes both halves of the edge.

        Parameters:
        index - the index of the interior half edge to remove
      • removeHalfEdges

        final void removeHalfEdges​(DoubleEdgeListHalfEdge edge)
        Removes the given half edge and its twin.
        Parameters:
        edge - the half edge to remove
      • removeHalfEdges

        final void removeHalfEdges​(int index,
                                   DoubleEdgeListHalfEdge edge)
        Removes the given half edge and its twin.
        Parameters:
        index - the index of the given edge
        edge - the half edge to remove
      • getConvexDecomposition

        public java.util.List<Convex> getConvexDecomposition()
        Returns the convex decomposition of this DCEL assuming that the remaining faces are all convex polygons.
        Returns:
        List<Convex>
      • getTriangulation

        public java.util.List<Triangle> getTriangulation()
        Returns the triangulation of this DCEL assuming that the remaining faces are all triangles.
        Returns:
        List<Triangle>
        Since:
        3.1.9
      • triangulateYMonotonePolygons

        public void triangulateYMonotonePolygons()
        Performs a triangulation of the DCEL assuming all faces are Monotone Y polygons.
      • triangulateYMonotonePolygon

        final void triangulateYMonotonePolygon​(MonotonePolygon<DoubleEdgeListVertex> monotonePolygon)
        Triangulates the given y-monotone polygon adding the new diagonals to this DCEL.
        Parameters:
        monotonePolygon - the monotone polygon (x or y) to triangulate
      • getYMonotonePolygons

        final java.util.List<MonotonePolygon<DoubleEdgeListVertex>> getYMonotonePolygons()
        Returns a list of y-monotone polygons from the faces of this DCEL.

        This method assumes that all faces within this DCEL are y-monotone and does not perform any verification of this assumption.

        Returns:
        List<MonotonePolygon>
      • hertelMehlhorn

        public void hertelMehlhorn()
        Performs the Hertel-Mehlhorn algorithm on the given DCEL assuming that it is a valid triangulation.

        This method will remove unnecessary diagonals and remove faces that get merged leaving a convex decomposition.

        This method is guaranteed to produce a convex decomposition with no more than 4 times the minimum number of convex pieces.