blogspot.software_and_algorithms.stern_library.geometry

Class ClosestPointPairAlgorithm

java.lang.Object

blogspot.software_and_algorithms.stern_library.geometry.ClosestPointPairAlgorithm

public class ClosestPointPairAlgorithm
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

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected static class	ClosestPointPairAlgorithm.PairStructure Convenience data structure to hold a pair of points along with their distance from one another.

Constructor Summary

Constructors

Constructor and Description
ClosestPointPairAlgorithm(Collection<Point2D> points) Construct an instance of the algorithm for the specified point Collection.

Method Summary

Modifier and Type	Method and Description
protected ClosestPointPairAlgorithm.PairStructure	closestPair(int low, int high, List<Point2D> localPointsOrderedByYCoordinate) Internal helper method which implements the closest point pair algorithm.
Point2D[]	execute() Execute the algorithm.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ClosestPointPairAlgorithm

public ClosestPointPairAlgorithm(Collection<Point2D> 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 Detail

closestPair

protected ClosestPointPairAlgorithm.PairStructure closestPair(int low,
                                                              int high,
                                                              List<Point2D> localPointsOrderedByYCoordinate)

Internal helper method which implements the closest point pair algorithm.

Parameters:

low - the starting index, inclusive, of the sublist in which to search for the closest point pair.

high - the ending index, exclusive, of the sublist in which to search for the closest point pair.

localPointsOrderedByYCoordinate - the points from the target sublist, ordered by y coordinate.

Returns:

a PairStructure containing the closest point pair among elements of the target sublist.

execute

public Point2D[] execute()

Execute the algorithm.

Returns:

a Point2D[] containing exactly two elements which are the closest pair of points among those in the collection used to construct this instance.