Package micycle.pgs.commons

Class ClosestPointPair

java.lang.Object
micycle.pgs.commons.ClosestPointPair
public class ClosestPointPair extends Object
An implementation of a divide-and-conquer algorithm for computing the closest pair of elements of a set of points.

The algorithm consists of constructing an ordered list of points, then recursively dividing the list into a left and right sublist towards finding the closest point pairs for each sublist. The two sub-results are merged by selecting the optimal among them and all closer point pairs that cross the boundary of separation. Happily, only a linear amount of work is required to find all closer point pairs that cross the boundary, giving a total runtime of O(n*log(n)) for the algorithm.

Author:
Kevin L. Stern, Adapted for Processing by Michael Carleton

  • Constructor Details

    • ClosestPointPair

      public ClosestPointPair(Collection<processing.core.PVector> points)
      Construct an instance of the algorithm for the specified point Collection.
      Parameters:
      points - the Collection of points through which to search for the closest pair.

  • Method Details

    • execute

      public List<processing.core.PVector> execute()
      Execute the algorithm.
      Returns:
      a List containing exactly two elements which are the closest pair of points among those in the collection used to construct this instance.