将基坐标与 n 个坐标列表进行比较并确定最接近的 m 个坐标的最佳算法？
我现在有一些代码正在执行此操作。它适用于中小型列表，但是当我有一个大小为 n > 的列表时，它可以正常工作。 5000 那么我的算法在移动设备上运行大约需要 1 分钟。我基本上将 Java 中的坐标对象与坐标对象列表（向量）进行比较。
这是我的基本算法：
- 遍历列表 nx 中的每个元素，
- 如果“10 个最接近”列表中的项目少于 10 个，则将 nx 添加到列表中 如果“10 最接近”列表已经有 10 个项目，则转到下一个元素
- ，然后计算 nx 与底座之间的距离 则坐标
- 如果距离小于“10 个最近距离”中的最远距离， list”，然后删除最远的项目 从该列表中并将其替换为 nx
我一直在关注这个，并试图找到一种更有效的方法来做到这一点。这有点像排序算法问题，所以必须有更好的方法。
这是我的距离计算方法：
public static double distance(double lat1, double lon1, double lat2, double lon2, char unit) {
double theta = lon1 - lon2;
double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta));
dist = acos(dist);
dist = rad2deg(dist);
dist = dist * 60 * 1.1515;
if (unit == 'K') {
dist = dist * 1.609344;
} else if (unit == 'N') {
dist = dist * 0.8684;
}
return (dist);
}
I have some code doing this right now. It works fine with small to medium sized lists, but when I have a list of size n > 5000 then the my algorithm can take almost 1 minute on a mobile device to run. I'm basically comparing a Coordinate object in Java to a list (Vector) of Coordinate objects.
Here's my basic algorithm:
- traverse each element in the list nx
- if there is less 10 items in the "10 closest" list then add nx to the list
and go to the next element - if the "10 closest" list has 10 items already, then calculate the
distance between nx and the base
Coordinates - if the distance is less than furthest distance in the "10 closest
list" then remove the furthest item
from that list and replace it with nx
I keep looking at this and am trying to find a more efficient way of doing this. It's sort of like a sorting algorithm problem so there must be a better way.
Here is my distance calculation method:
public static double distance(double lat1, double lon1, double lat2, double lon2, char unit) {
double theta = lon1 - lon2;
double dist = Math.sin(deg2rad(lat1)) * Math.sin(deg2rad(lat2)) + Math.cos(deg2rad(lat1)) * Math.cos(deg2rad(lat2)) * Math.cos(deg2rad(theta));
dist = acos(dist);
dist = rad2deg(dist);
dist = dist * 60 * 1.1515;
if (unit == 'K') {
dist = dist * 1.609344;
} else if (unit == 'N') {
dist = dist * 0.8684;
}
return (dist);
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以将坐标存储在某个空间分区树中。
或者，对于更简单的方法，您可以使用二维存储桶数组，并首先检查最近的存储桶，直到找到足够的最近邻居。仅当坐标分布均匀时，此方法才有效。
编辑：要比较距离，您可以预先计算球体上的 3D 坐标，并在比较中使用欧几里得距离的平方：
You could store your coordinates in some space partitioning tree.
Or, for a simpler approach, you could use a two-dimensional array of buckets, and check the closest buckets first, until you found enough nearest neighbors. This only works well if the coordinates are distributed evenly.
Edit: To compare the distances you could precompute 3D coordinates on the sphere and use the square of the Euclidean distance in the comparisons:
好吧，也许用数组来做这件事会更快。您可以比较距离的平方而不是距离，这意味着您不必使用平方根。
最好有实际的代码。
Well, maybe it would be faster to do this with arrays. And you could compare the square of the distance instead of the distance, which means that you don't have to work with square roots.
It would be good to have the actual code.
您也许可以使用类似于此网站的方法来限制实际需要您计算的点数距离。
该网站展示了如何计算点和给定距离的纬度、经度边界坐标。这与您遇到的问题不完全相同，但它可以充当过滤器。在你的例子中，你显然试图找到距离给定点最近的 10 个（或 n 个）点。您可以应用以下算法来查找 10 个（或 n 个）最近的点：
这种方法的好处是您可以避免对大量点进行繁重的计算。根据点的分布，您仍然可能会遇到性能不佳的问题，例如，如果点被排序，使得它们与目标点的距离逐渐减小（点 [0] 是最远的，点 [N]是最接近的））。
You might be able use something like the approach at this website to restrict the number of points that actually require you to compute the distance.
The website shows how to compute the lat, lon bounding coordinates for a point and a given distance. That is not exactly the same problem that you have, but it could serve as a filter. In your case you are apparently trying to find the 10 (or n) closest points to a given point. You could apply the following algorithm to find the 10 (or n) closest points:
The benefit of this approach is that you might be able to avoid heavy calculations for a large number of your points. Depending on the distribution of your points, you could still suffer from poor performance, such as if the points turn out to be ordered such that they are in decreasing distance from your target points (point[0] is the farthest and point[N] is the closest)).