如何从坐标列表中计算到给定点的最近坐标
基本上我有一个用户当前位置。然后我有一个坐标列表。
我将如何根据用户当前位置计算列表中最近的一组坐标。我的应用程序是用 java 编写的，适用于 android 平台
Basically i have a users current location. i then have a list of co-ordinates.
How would i go about calculating the nearest set of co-ordinates from the list against the users current location. My application is written in java for hthe android platform
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
http://developer.android.com/reference/android/location/Location.html
检查 distanceTo 或 distanceBetween 方法。
或者您可以手动计算坐标之间的距离并找到计算距离的最小距离，您可以参考以下链接 http://www.zipcodeworld.com/samples/distance.java.html
http://developer.android.com/reference/android/location/Location.html
check for distanceTo or distanceBetween methods.
Or you can manually calculate the distance among the coordinates and find the smallest distance for calculating distance you can refer following link http://www.zipcodeworld.com/samples/distance.java.html
如果列表上的点在该区域中分布相当均匀，那么这应该可行：
将区域划分为一定大小的象限。保留并更新每个象限中的点列表。
给定一个坐标x，找到它所属的象限，仅计算同一象限内的点的距离（如果没有，则添加相邻象限的点，直到成功），选择k个最接近的点p_i。
检查圆 c(center=x,radius=max(p_i-x)) 是否穿过任何尚未检查的象限，如果穿过，则计算从这些象限到点的距离。返回最接近的 k 个点的集合。
您可能需要检查 c 内包含点的最近象限，而不是选择圆 c 中的所有象限，直到找到 k 个最接近的点 p_i ，以便 c(x,max(p_i-x)) 中的所有象限为空或选中。
将最近象限搜索速度从 O(n) 加速到 O(log n)：您需要实现一个树状结构：4 个象限的象限等，跟踪每个象限中的点数。当点移动时，更新它（O(log)）。无论如何，对于200分来说，这可能有点过大了。
编辑：而不是“树状结构”，只需使用哈希表和简单的哈希函数，例如： (x div 10^p, y div 10^p)
If points on the list are rather uniformly distributed in the area, this should work:
Divide the area into quadrants of a certain size. Keep and update a list of points which reside in each quadrant.
Given a coordinate x, find the quadrant it belongs to, compute distances only for points in the same quadrant (if none there, add points from neighboring quadrants, until success), choose k closest points p_i.
Check if the circle c(center=x,radius=max(p_i-x)) crosses any quadrants that were not checked yet, and if it does, compute distances to points from those quadrants. Return the set of closest k points altogether.
Instead of selecting all quadrants in a circle c, you may want check closest quadrants inside c that contain points, until you find k closest points p_i so that all quadrants in c(x,max(p_i-x)) are empty or checked.
Speed up the nearest quadrant search from O(n) to O(log n): you need to implement a tree-like structure: quadrants of 4 quadrants, etc. which tracks the number of points in each quadrant. When points move, update it (O(log)). Anyway, for 200 points this is probably an overkill.
edit: instead of a "tree-like structure" just use hash table and an easy hash function, like: (x div 10^p, y div 10^p)
有一种分治算法可以在 O(nlogn) 中找到最接近的点对。尽管这对于您的数据集大小来说可能有点过大了。更多信息此处
There is a divide and conquer algorithm to find the closes pair of points in O(nlogn). Although it may be a but overkill for your data set size. More info on it here