Module org.dyn4j

Class DivideAndConquer

  • All Implemented Interfaces:
    HullGenerator

    public class DivideAndConquer
    extends java.lang.Object
    implements HullGenerator
    Implementation of the Divide and Conquer convex hull algorithm.

    This algorithm handles coincident and colinear points by ignoring them during processing. This ensures the produced hull will not have coincident or colinear vertices.

    This algorithm is O(n log n) where n is the number of input points.

    Since:
    2.2.0
    Version:
    3.4.0
    Author:
    William Bittle
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) LinkedVertexHull divide​(Vector2[] points, int first, int last)
      Recursive method to subdivide and merge the points.
      Vector2[] generate​(Vector2... points)
      Returns a convex hull generated from the given point set in counter-clockwise point order.
      • Methods inherited from class java.lang.Object

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

      • DivideAndConquer

        public DivideAndConquer()
    • Method Detail

      • generate

        public Vector2[] generate​(Vector2... points)
        Description copied from interface: HullGenerator
        Returns a convex hull generated from the given point set in counter-clockwise point order.

        Returns null if the given points array is null.

        Returns the array unchanged if the length is less than or equal to 2.

        Specified by:
        generate in interface HullGenerator
        Parameters:
        points - the point set or cloud
        Returns:
        Vector2[] the convex hull vertices
      • divide

        final LinkedVertexHull divide​(Vector2[] points,
                                      int first,
                                      int last)
        Recursive method to subdivide and merge the points.
        Parameters:
        points - the array of points
        first - the first index inclusive
        last - the last index exclusive
        Returns:
        LinkedVertexHull the convex hull created