3
我正在寫一個方法，它將一個點數組作爲輸入，併爲數組中的每個點找到除它自身以外的最近點。我目前正在以一種蠻橫的方式來做這件事（每隔一點就對每一點都進行討論）。我目前的implimentation沒有數組排序，但我可以使用CompareByX方法通過p.x值進行排序。我非常喜歡算法的運行時間，而且它的n值很大，所以非常耗時。我對這個主題並不十分了解，並且對不同類型的數據結構非常瞭解，任何簡單的幫助都會很棒！找到每個點的最近點（最近的鄰居）
我當前的代碼是：
import java.util.*;
import java.lang.*;
import java.io.*;
class My2dPoint {
double x;
double y;
public My2dPoint(double x1, double y1) {
x=x1;
y=y1;
}
}
class CompareByX implements Comparator<My2dPoint> {
public int compare(My2dPoint p1, My2dPoint p2) {
if (p1.x < p2.x) return -1;
if (p1.x == p2.x) return 0;
return 1;
}
}
/* An object of the above comparator class is used by java.util.Arrays.sort() in main to sort an array of points by x-coordinates */
class Auxiliaries {
public static double distSquared(My2dPoint p1, My2dPoint p2) {
double result;
result = (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
return result;
}
}
public class HW3 {
public static void main (String argv []) throws IOException {
int range = 1000000; // Range of x and y coordinates in points
System.out.println("Enter the number of points");
InputStreamReader reader1 = new InputStreamReader(System.in);
BufferedReader buffer1 = new BufferedReader(reader1);
String npoints = buffer1.readLine();
int numpoints = Integer.parseInt(npoints);
// numpoints is now the number of points we wish to generate
My2dPoint inputpoints [] = new My2dPoint [numpoints];
// array to hold points
int closest [] = new int [numpoints];
// array to record soln; closest[i] is index of point closest to i'th
int px, py;
double dx, dy, dist;
int i,j;
double currbest;
int closestPointIndex;
long tStart, tEnd;
for (i = 0; i < numpoints; i++) {
px = (int) (range * Math.random());
dx = (double) px;
py = (int) (range * Math.random());
dy = (double) py;
inputpoints[i] = new My2dPoint(dx, dy);
}
// array inputpoints has now been filled
tStart = System.currentTimeMillis();
// find closest [0]
closest[0] = 1;
currbest = Auxiliaries.distSquared(inputpoints[0],inputpoints[1]);
for (j = 2; j < numpoints; j++) {
dist = Auxiliaries.distSquared(inputpoints[0],inputpoints[j]);
if (dist < currbest) {
closest[0] = j;
currbest = dist;
}
}
// now find closest[i] for every other i
for (i = 1; i < numpoints; i++) {
closest[i] = 0;
currbest = Auxiliaries.distSquared(inputpoints[i],inputpoints[0]);
for (j = 1; j < i; j++) {
dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
if (dist < currbest) {
closest[i] = j;
currbest = dist;
}
}
for (j = i+1; j < numpoints; j++) {
dist = Auxiliaries.distSquared(inputpoints[i],inputpoints[j]);
if (dist < currbest) {
closest[i] = j;
currbest = dist;
}
}
}
tEnd = System.currentTimeMillis();
System.out.println("Time taken in Milliseconds: " + (tEnd - tStart));
}
}
Nearest Neighbor - > kd-Tree。對。 – Waldheinz 2011-03-02 22:20:11