# Closest Pair



## vali9 (9. Nov 2014)

hi.
müssen morgen ne gruppenaufgabe abgeben und kommen ums verrecken nicht weiter. besser gesagt wissen wir nicht, wo wir anfangen sollen. vielleicht kann jemand den ein oder anderen mehr oder weniger ausführlichen Denkanstoß geben. hier sind die aufgabenstellung und der code.


```
import java.util.Arrays;

/**
 * Methods for finding a pair of points in two-dimensional space with a 
 * minimum euclidian distance. 
 * 
 * Nomenclature:
 * 	- p:	a point P(x, y).
 * 			Data type: double[] p = {x, y};
 *  - pd:	a point P(x, y) and a distance d to another point.
 *  		Data type: double[] pd = {x, y, d};
 *  - pp: 	a pair of points P1(x1, y1) and P2(x2, y2).
 *  		Data type: double[] pp = {x1, y1, x2, y2};
 *  - ppd:	a pair of points P1(x1, y1), P2(x2, y2), and a distance d between
 *  			those points.
 *  		Data type: double[] ppd = {x1, y1, x2, y2, d};
 *  - ps:	a list of points P1...Pn.
 *  		Data type: double[][] ps = {{x1, y1}, {x2, y2}, ..., {xn, yn}};
 */
public class ClosestPair
{
	/**
	 * Constant value that represents the 'no result' value of a ppd.
	 */
	public static final double[] PPD_NO_RESULT = {Double.NaN, Double.NaN, Double.NaN, Double.NaN, Double.NaN};

	/**
	 * Compute the euclidian distance between two points P1 and P2.
	 * 
	 * @param p1	First point.
	 * @param p2	Second point.
	 * 
	 * @return		Euclidian distance.
	 */
	public static double distance(double[] p1, double[] p2) {
		return Math.sqrt((p2[0] - p1[0]) * (p2[0] - p1[0]) + (p2[1] - p1[1]) * (p2[1] - p1[1]));
	}

	/**
	 * Append the coordinates of a point to an array.
	 * 
	 * @param array
	 * 			An arbitrary double array {a1, a2, ..., an} with length n.
	 * 
	 * @param p
	 * 			A point P(x, y).
	 * 
	 * @return A double array with length n + 2: {a1, a2, ..., an, x, y}.
	 */
	public static double[] appendPoint(double[] array, double[] p) {
		double[] newArray = Arrays.copyOf(array, array.length + 2);
		newArray[newArray.length - 2] = p[0];
		newArray[newArray.length - 1] = p[1];
		
		return newArray;
	}
	
	/**
	 * Append a distance to an array.
	 * 
	 * @param array
	 * 			An arbitrary double array {a1, a2, ..., an} with length n.
	 * 
	 * @param d
	 * 			A distance.
	 * 
	 * @return A double array with length n + 1: {a1, a2, ..., an, d}.
	 */
	public static double[] appendDistance(double[] array, double d) {
		double[] newArray = Arrays.copyOf(array, array.length + 1);
		newArray[newArray.length - 1] = d;
		
		return newArray;
	}
	
	/**
	 * Skips the first point in a point list.
	 * 
	 * @param ps
	 * 			Arbitrary point list {x1, y1, x2, y2, ..., xn, yn}.
	 * 
	 * @return A new point list: {x2, y2, ..., xn, yn}.
	 */
	public static double[][] skipFirstPoint(double[][] ps) {
		return Arrays.copyOfRange(ps, 1, ps.length);
	}
	
	// ************************************************************************

	/**
	 * A recursive helper method for computing a closest point within a point 
	 * list.
	 * 
	 * The method *recursively* computes a point within ps that 
	 * a) is closest to p and
	 * b) has a shorter euclidian distance than the given point in pd.
	 * 
	 * @param p
	 * 			The start point of the euclidian distance.
	 *  
	 * @param pd
	 * 			The current closest point (and its distance) to p.
	 * 
	 * @param ps
	 * 			The point list to investigate.
	 * 
	 * @return The new closest point (and its distance) to p: pd'
	 */
	public static double[] closestPointHelper(double[] p, double[] pd, double[][] ps) {	
		// TODO
		return null;
	}
	
	/**
	 * Computes the closest point to p in ps.
	 * 
	 * The method has to use closestPointHelper in ordert ot compute the 
	 * result.
	 * 
	 * @param p
	 * 			The start point of the euclidian distance.
	 * 
	 * @param ps
	 * 			The point list to investigate.
	 * 
	 * @return	If ps is empty: {x, y, 0}.
	 * 			otherwise: the closest point to p in ps: pd
	 * 			
	 */
	public static double[] closestPoint(double[] p, double[][] ps) {
		// TODO
		return null;
	}
	
	/**
	 * Computes the closest pair ppd within ps.
	 * 
	 * The method *recursively* computes a pair of points p1 and p2 with a 
	 * minimal euclidian distance. 
	 * The method has to use the method closestPoint.
	 * 
	 * @param ps
	 * 			The point list to investigate.
	 * 
	 * @return	if ps is empty: PPD_NO_RESULT
	 * 			if ps has only one point p1: ppd = {x1, y1, x1, y1, 0}
	 * 			otherwise: ppd.
	 */
	public static double[] closestPair(double[][] ps) {
		// TODO
		return null;
	}
	
	public static void main(String[] args)
	{		
		// a list of points
		double[][] ps = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7}};
		
		// another list of points
		double[][] ps2 = {{1, 1}, {2, 2}, {3, 0.9}, {4, 5}, {5, 6}};
		
		// a single point
		double[] p = {5, 0.5};
		
		// a pair of points
		double[] pp = appendPoint(p, new double[]{1, 1});
		
		/*
		 * Test: distance.
		 */
		System.out.println( distance(new double[]{1, 1}, new double[]{2, 2}) );		// 1.4142135623730951

		/*
		 * Test: appendPoint.
		 */		
		System.out.println( Arrays.toString(appendPoint(p, new double[]{2, 3})) );	// [5.0, 0.5, 2.0, 3.0]
		
		/*
		 * Test: appendDistance.
		 */
		System.out.println( Arrays.toString(appendDistance(p, 1.5)) );				// [5.0, 0.5, 1.5]
		System.out.println( Arrays.toString(appendDistance(pp, 1.5)) );				// [5.0, 0.5, 1.0, 1.0, 1.5]
		
		/*
		 * Test: skipFirstPoint.
		 */
		System.out.println( Arrays.deepToString(skipFirstPoint(ps)) );				// [[2.0, 2.0], [3.0, 3.0], [4.0, 4.0], [5.0, 5.0], [6.0, 6.0], [7.0, 7.0]]
		
		/*
		 * Test: closestPointHelper.
		 */
		System.out.println( Arrays.toString(										// [6.0, 0.5, 1.0]
				ClosestPair.closestPointHelper(p, new double[]{6, 0.5, 1}, new double[][]{})) );
		
		/*
		 * Test: closestPoint.
		 */
		System.out.println( Arrays.toString(closestPoint(p, new double[][]{})) );	// [5.0, 0.5, 0.0]
		
		/*
		 * Test: closestPair.
		 */
		System.out.println( Arrays.toString(closestPair(new double[][]{})) );		// [NaN, NaN, NaN, NaN, NaN]	
	}
}
```

liebe grüße,
vali


----------



## AndiE (9. Nov 2014)

Wo ist das Problem? 

Wenn ich eine Gruppe von n-Punkten habe GP=(P1,P2...PN), und ich will wissen, welcher Punkt am nächsten zu P0 liegt, lege ich doch einfach fest, als 1. sei P1 der dichteste Punkt, den lösche ich aus GP, so dass diese zu GP1 wird und rufe ClosestPointHelper(P0,P1,GP1) auf. Die Methode wird P2 als dichtesten Punkt vermuten, die Distanz zu P0 bestimmen, entweder P2 gegen P1 auswechseln, und ClosestPointHelper wieder aufrufen usw. Ist GP leer, sind also alle Punkte überprüft, enthält der mittlere parameter den Punkt mit der kürzesten Distanz. Allerdings muss man dazu als Testwerte eine vernünftige Punktwolke entwickeln, wo der Auswahlvorgang auch nachvollziehbar ist.


----------

