- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在编写一个方法,它将一个点数组作为输入,并为数组中的每个点找到除它本身之外离它最近的点。我目前正在以蛮力方式执行此操作(检查每个点与其他点)。我当前的实现没有对数组进行排序,但我可以使用 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));
}
}
最佳答案
关于java - 找到每个点的最近点(Nearest Neighbor),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5174143/
我有一组 3D 点,每个点都与一个方向相关联(例如单位向量)。给定另一个点 + 方向,我想找出集合中最近的点(使用标准 2 范数),该点也满足方向向量的特定条件(例如,两个方向向量之间的角度在特定角度
局部敏感散列对于 KNN 来说似乎是一种很好的技术,没有任何缺点。但是,如果有人在工业中将其用于实际应用,那么局部敏感散列的缺点是什么? LSH在什么情况下会失败或者做的有些糟糕?还是编码/调整需要很
我在下拉列表中有一个单词列表,并且有一个单词正在寻找合适的合作伙伴(用户正在选择它)为了使用户更容易(因为列表可能很长并且过程必须很快),我想提供一个可能的选项。 我已经了解了如何更改所选单词。 我想
当提到 this ASP.NET github wiki page ,它解释了如何使用“Nearest Win”方案丢弃同名(但不同版本)的包: Nearest wins means that the
基于 calculating average distance of nearest neighbours in pandas dataframe 中的代码,如何调整它以便将第二个和第三个最近邻居返回
我有一个表,存储带有 x、y 和高程的网格。我有一些已知的高程和许多空(NULL)高程。我正在尝试构建一个对缺失值进行插值(简单线性插值)的查询,但我一开始就陷入困境:我什至无法编写一个获取最接近的非
假设我在关注 NSInteger: 111 246 99 82 92 85 是否有一个函数可以像这样转换(四舍五入)这些数字: 110 250 100 80 90 85 最佳答案 查看您要求的结果,小
我将 C++ 与 Armadillo 库结合使用。 假设我有一个按数字顺序排序的 n x 1 列矩阵。例如 mat X; X.randn(100,1); mat X_sorted; X_sorted
我有以下 XML: Name1 LastName1 Name5 LastName5 Name2 LastName2
我的特征向量具有连续(或范围广泛)和二元分量。如果我简单地使用欧几里德距离,连续分量将产生更大的影响: 将对称与不对称表示为 0 和 1 以及从 0 到 100 的一些不太重要的比率,与将比率更改为
我正在编写一个方法,它将一个点数组作为输入,并为数组中的每个点找到除它本身之外离它最近的点。我目前正在以蛮力方式执行此操作(检查每个点与其他点)。我当前的实现没有对数组进行排序,但我可以使用 Comp
我正在尝试找到一种在图像中查找颜色的方法。这是一个简化的示例: tree = ExampleData[{"TestImage", "Tree"}] 我可以看到那里有蓝色,所以我想在像素海洋中的某个地方
如果我的问题没有表述清楚,请告诉我,我会尽力改写! 给定一个大型道路网络(> 1,000,000 个节点,> 3,000,000 条边),该图未加权且无向。在此图中,我们将选择 1000 个随机节点作
假设我有一个程序可以创建 4x8 板。板上的每个单元格要么是彩色对象,要么是空单元格对象。如何找到看板中哪一行是空的并且最接近第 0 行? 我的尝试: public int emptyRow() {
是否有任何方法可以指定最近但仅次要成员的读取首选项模式?我们遇到两个不同的数据中心,我们的主节点是其中之一,而辅助节点位于两个数据中心。我们希望通过将查询路由到最近的可用节点来节省读取操作的网络延迟,
我正在尝试将图像上的颜色聚类到预定义的类别(黑色、白色、蓝色、绿色、红色)。我正在使用以下代码: import numpy as np import cv2 src = cv2.imread('obj
在论文“When Is 'Nearest Neighbor' Meaningful?”中我们读到,“我们表明,在某些广泛的条件下(在数据和查询分布或工作负载方面),随着维度的增加,到最近的距离neig
现在大多数餐馆和其他企业在其网站上都有一个“Find Locations”功能,可以列出给定地址/邮政编码的最近位置。这是如何实现的?将邮政编码与数据库进行匹配是一种简单易行的方法,但可能并不总是有效
我需要在我们的网站上“查找最近的位置”。 访问者在输入他们的邮政编码的地方,然后他们将被重定向到我们最近位置的特定网页。我们在美国和加拿大有四十个地点。 我怎样才能构建这样的东西?我可以使用 Goog
我正在阅读文档:https://docs.flutter.io/flutter/widgets/BuildContext-class.html This can lead to some tricky
我是一名优秀的程序员,十分优秀!