Module org.dyn4j

Class Bayazit

  • All Implemented Interfaces:
    Decomposer

    public class Bayazit
    extends java.lang.Object
    implements Decomposer
    Implementation of the Bayazit convex decomposition algorithm for simple polygons.

    This algorithm is a O(nr) complexity algorithm where n is the number of input vertices and r is the number of output convex polygons. This algorithm can achieve optimal decompositions, however this is not guaranteed.

    Since:
    2.2.0
    Version:
    3.1.10
    Author:
    William Bittle
    See Also:
    Bayazit
    • Constructor Summary

      Constructors 
      Constructor Description
      Bayazit()  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.List<Convex> decompose​(Vector2... points)
      Performs the decomposition on the given polygon returning a list of Convex shapes.
      protected void decomposePolygon​(java.util.List<Vector2> polygon, java.util.List<Convex> polygons)
      Internal recursive method to decompose the given polygon into convex sub-polygons.
      protected boolean getIntersection​(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, Vector2 p)
      Returns true if the given lines intersect and returns the intersection point in the p parameter.
      protected boolean isReflex​(Vector2 p0, Vector2 p, Vector2 p1)
      Returns true if the given vertex, b, is a reflex vertex.
      protected boolean left​(Vector2 a, Vector2 b, Vector2 p)
      Returns true if the given point p is to the left of the line created by a-b.
      protected boolean leftOn​(Vector2 a, Vector2 b, Vector2 p)
      Returns true if the given point p is to the left or on the line created by a-b.
      protected boolean right​(Vector2 a, Vector2 b, Vector2 p)
      Returns true if the given point p is to the right of the line created by a-b.
      protected boolean rightOn​(Vector2 a, Vector2 b, Vector2 p)
      Returns true if the given point p is to the right or on the line created by a-b.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • Bayazit

        public Bayazit()
    • Method Detail

      • decompose

        public java.util.List<Convex> decompose​(Vector2... points)
        Description copied from interface: Decomposer
        Performs the decomposition on the given polygon returning a list of Convex shapes.
        Specified by:
        decompose in interface Decomposer
        Parameters:
        points - the polygon vertices
        Returns:
        List<Convex>
      • decomposePolygon

        protected void decomposePolygon​(java.util.List<Vector2> polygon,
                                        java.util.List<Convex> polygons)
        Internal recursive method to decompose the given polygon into convex sub-polygons.
        Parameters:
        polygon - the polygon to decompose
        polygons - the list to store the convex polygons resulting from the decomposition
      • isReflex

        protected boolean isReflex​(Vector2 p0,
                                   Vector2 p,
                                   Vector2 p1)
        Returns true if the given vertex, b, is a reflex vertex.

        A reflex vertex is a vertex who's interior angle is greater than 180 degrees.

        Parameters:
        p0 - the vertex to test
        p - the previous vertex
        p1 - the next vertex
        Returns:
        boolean
      • left

        protected boolean left​(Vector2 a,
                               Vector2 b,
                               Vector2 p)
        Returns true if the given point p is to the left of the line created by a-b.
        Parameters:
        a - the first point of the line
        b - the second point of the line
        p - the point to test
        Returns:
        boolean
      • leftOn

        protected boolean leftOn​(Vector2 a,
                                 Vector2 b,
                                 Vector2 p)
        Returns true if the given point p is to the left or on the line created by a-b.
        Parameters:
        a - the first point of the line
        b - the second point of the line
        p - the point to test
        Returns:
        boolean
      • right

        protected boolean right​(Vector2 a,
                                Vector2 b,
                                Vector2 p)
        Returns true if the given point p is to the right of the line created by a-b.
        Parameters:
        a - the first point of the line
        b - the second point of the line
        p - the point to test
        Returns:
        boolean
      • rightOn

        protected boolean rightOn​(Vector2 a,
                                  Vector2 b,
                                  Vector2 p)
        Returns true if the given point p is to the right or on the line created by a-b.
        Parameters:
        a - the first point of the line
        b - the second point of the line
        p - the point to test
        Returns:
        boolean
      • getIntersection

        protected boolean getIntersection​(Vector2 a1,
                                          Vector2 a2,
                                          Vector2 b1,
                                          Vector2 b2,
                                          Vector2 p)
        Returns true if the given lines intersect and returns the intersection point in the p parameter.
        Parameters:
        a1 - the first point of the first line
        a2 - the second point of the first line
        b1 - the first point of the second line
        b2 - the second point of the second line
        p - the destination object for the intersection point
        Returns:
        boolean