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.
liebe grüße,
vali
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.
Java:
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
