Divide and Conquer convex hull algorithm

The Divide and Conquer Convex Hull Algorithm is a powerful method for finding the convex hull of a set of 2-dimensional points. Let’s dive into the details:

1. What is the Convex Hull?

• The convex hull of a set of points is the smallest convex polygon that encloses all the given points.

• It’s a fundamental concept in computational geometry with applications in computer graphics, robotics, and image processing.

1. Algorithm Overview:

• The divide and conquer algorithm for the convex hull has three major steps:

• Divide: Split the set of n points into left and right halves using a vertical line.

• Conquer: Recursively find the convex hull for the left and right halves.

• Merge: Combine the convex hulls of the left and right halves to obtain the overall convex hull.

1. Divide and Conquer Steps:

• Divide:

• Divide the set of points into two halves using a vertical line (e.g., by sorting the points by their x-coordinates).

• Conquer:

• Recursively compute the convex hull for the left and right halves.

• Merge:

• Combine the convex hulls of the left and right halves.

• To merge them, find the upper and lower tangents between the two convex hulls.

• The upper tangent connects the topmost points of both hulls, and the lower tangent connects the bottommost points.

• The merged convex hull includes the points lying between these tangents.

1. Complexity:

• The divide and conquer convex hull algorithm takes O(n log n) time.

• While the recursive steps involve sorting and merging, the overall complexity remains efficient.

1. Special Considerations:

• For small sets of points (e.g., 5 or fewer), a brute-force algorithm can be used to find the convex hull.

• Some variations handle the base case differently (e.g., considering 3 or fewer points as the complete convex hull).

/*
 * Copyright (c) 2010-2022 William Bittle  http://www.dyn4j.org/
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification, are permitted 
 * provided that the following conditions are met:
 * 
 *   * Redistributions of source code must retain the above copyright notice, this list of conditions 
 *     and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above copyright notice, this list of conditions 
 *     and the following disclaimer in the documentation and/or other materials provided with the 
 *     distribution.
 *   * Neither the name of the copyright holder nor the names of its contributors may be used to endorse or 
 *     promote products derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR 
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 
 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER 
 * IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package org.dyn4j.geometry.hull;

import java.util.Arrays;

import org.dyn4j.exception.ArgumentNullException;
import org.dyn4j.exception.NullElementException;
import org.dyn4j.geometry.Vector2;

/**
 * Implementation of the Divide and Conquer convex hull algorithm.
 * <p>
 * This algorithm handles coincident and colinear points by ignoring them during processing. This ensures
 * the produced hull will not have coincident or colinear vertices.
 * <p>
 * This algorithm is O(n log n) where n is the number of input points.
 * @author William Bittle
 * @version 5.0.0
 * @since 2.2.0
 */
public class DivideAndConquer extends AbstractHullGenerator implements HullGenerator {
	/* (non-Javadoc)
	 * @see org.dyn4j.geometry.hull.HullGenerator#generate(org.dyn4j.geometry.Vector2[])
	 */
	@Override
	public Vector2[] generate(Vector2... points) {
		// check for a null array of points
		if (points == null) 
			throw new ArgumentNullException("points");
		
		// get the size
		int size = points.length;
		// check the size
		if (size <= 2) return points;
		
		try {
			// sort the points by the x coordinate, then the y coordinate
			Arrays.sort(points, new MinXYPointComparator());
		} catch (NullPointerException e) {
			// this will be hit if any of the points are null
			throw new NullElementException("points");
		}
		
		// No need to pre-process the input and remove coincident points
		// Those are gracefully handled and removed in the main algorithm 
		
		// perform the divide and conquer algorithm on the point cloud
		LinkedVertexHull hull = this.divide(points, 0, size);
		
		// return the array
		return hull.toArray();
	}
	
	/**
	 * Recursive method to subdivide and merge the points.
	 * @param points the array of points
	 * @param first the first index inclusive
	 * @param last the last index exclusive
	 * @return {@link LinkedVertexHull} the convex hull created
	 */
	final LinkedVertexHull divide(Vector2[] points, int first, int last) {
		// compute the size of the hull we need to create
		int size = last - first;
		if (size == 1) {
			// if we only have one point create a hull containing the one point
			return new LinkedVertexHull(points[first]);
		} else {
			// otherwise find the middle index
			int mid = (first + last) / 2;
			// create the left convex hull
			LinkedVertexHull left = divide(points, first, mid);
			// create the right convex hull
			LinkedVertexHull right = divide(points, mid, last);
			// merge the two convex hulls
			return LinkedVertexHull.merge(left, right);
		}
	}
}