Module org.dyn4j

## Class DivideAndConquer

• java.lang.Object
• org.dyn4j.geometry.hull.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
• ### Constructor Summary

Constructors
Constructor Description
`DivideAndConquer()`
• ### Method Summary

All 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