gpt4 book ai didi

java - 找到每个点的最近点(Nearest Neighbor)

转载 作者:塔克拉玛干 更新时间:2023-11-01 22:34:12 24 4
gpt4 key购买 nike

我正在编写一个方法,它将一个点数组作为输入,并为数组中的每个点找到除它本身之外离它最近的点。我目前正在以蛮力方式执行此操作(检查每个点与其他点)。我当前的实现没有对数组进行排序,但我可以使用 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));
}
}

最佳答案

最近邻搜索的蛮力仅适用于少量点。

您可能想研究一下 kd 树或空间数据结构。

Here is a demo for kd-Tree. This is what wikipedia says.

关于java - 找到每个点的最近点(Nearest Neighbor),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5174143/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com