如何计算地图中不同标记的距离,然后选取最less的一个

我必须从地图上的不同标记距离设备的当前位置,并拿起最短的一个。 我有lat和长的标记和当前的位置lat和long可以dynamic获取。

假设我在地图上有5个标记,class加罗尔(纬度:12.971599,长度:77.594563),德里(纬度:28.635308,长度:77.224960),孟买(纬度:19.075984,长度:72.877656),钦奈(纬度:13.052414, 80.250825),加尔各答(Lat:22.572646,Long:88.363895)。

现在假设用户站在海得拉巴附近(纬度:17.385044,长度:78.486671)。 当用户点击button时,应用程序应计算每个标记的距离,并拿起并返回最短的那个,这里将是class加罗尔。

有一种方法可以在本地数据库的帮助下做到这一点。 任何人都可以帮忙吗?

任何人都可以build议我一个很好的方法来做到这一点,或者如果你愿意可以拿出一个好的代码。 提前感谢。

Solutions Collecting From Web of "如何计算地图中不同标记的距离,然后选取最less的一个"

从你的评论我看到,你期望最多70-80个地点。 这并不多。

你可以简单地对所有标记进行蛮力search,并取最小值。

遍历所有标记,并search最小距离:

List<Marker> markers = createMarkers(); // returns an ArrayList<Markers> from your data source int minIndex = -1; double minDist = 1E38; // initialize with a huge value that will be overwritten int size = markers.size(); for (int i = 0; i < size; i++) { Marker marker = markers.get(i); double curDistance = calcDistance(curLatitude, curLongitude, marker.latitude, marker.longitude); if (curDistance < minDist) { minDist = curDistance; // update neares minIndex = i; // store index of nearest marker in minIndex } } if (minIndex >= 0) { // now nearest maker found: Marker nearestMarker = markers.get(minIndex); // TODO do something with nearesr marker } else { // list of markers was empty } 

对于calcDistance,使用android提供的距离计算方法。 (例如Location.distanceTo()
对于70-80个标记,没有必要使它更快,更复杂。 如果你有几千个点,那么投资一个更快的解决scheme是值得的(使用一个空间索引和一个避免sqrt计算的自己的距离计算)。

只需在最近的制造商search的开始和结束处以毫秒为单位打印当前时间,就可以看到,速度足够快。

如果你想find最短的一个没有列出最接近的,你想过程缩放到大量的位置,你可以做一些过滤,然后再计算距离 ,你可以简化公式加速,因为你不关心实际距离(即去除乘以地球半径)。

筛选algorithm,循环遍历每个位置:

  1. 计算经纬度的差异。
  2. 如果两个差异都比之前处理的一对差,则丢弃它。
  3. 计算距离,保持最小。

你可以进一步帮助algorithm,通过提供可能位于第一位的位置。 例如,如果你知道其中的一点是在同一个国家或国家。


下面是一些Python代码来做到这一点,用它作为您的解决scheme的伪代码:

 locations = { 'Bangalore' : (12.971599, 77.594563), 'Delhi' : (28.635308, 77.224960), 'Mumbai' : (19.075984, 72.877656), 'Chennai' : (13.052414, 80.250825), 'Kolkata' : (22.572646, 88.363895) } from math import sin, cos, atan2, sqrt EARTH_RADIUS = 6373 # km def distance(a, b): # pass tuples (lat1, lon1) = a (lat2, lon2) = b dlon = lon2 - lon1 dlat = lat2 - lat1 a = (sin(dlat/2))**2 + cos(lat1) * cos(lat2) * (sin(dlon/2))**2 c = 2 * atan2( sqrt(a), sqrt(1-a) ) return EARTH_RADIUS * c current = (17.385044, 78.486671) # current lat & lng closest = None closest_name = None for name, cordinates in locations.iteritems(): d = distance(current, cordinates) if closest is None or d < closest: closest = d closest_name = name print "~%dkm (%s)" % (distance(current, cordinates), name) print "\nClosest location is %s, %d km away." % (closest_name, closest) 

输出:

 ~5700km (Kolkata) ~13219km (Chennai) ~12159km (Bangalore) ~7928km (Delhi) ~10921km (Mumbai) Closest location is Kolkata, 5700 km away. 

如何循环所有标记并使用Location.distanceBetween检查距离? 没有魔法介入;)

 List<Marker> markers; LatLng currentPosition; float minDistance = Float.MAX_VALUE; Marker closest = null; float[] currentDistance = new float[1]; for (Marker marker : markers) { LatLng markerPosition = marker.getPosition(); Location.distanceBetween(currentPosition.latitude, currentPosition.longitude, markerPosition.latitude, markerPosition.longitude, currentDistance); if (minDistance > currentDistance[0]) { minDistance = currentDistance[0]; closest = marker; } } 

虽然已经发布了一些答案,我想我会介绍我的实现在Java中。 这已经被包装在AsyncTask中的4000多个标记使用,并且一直没有问题。

首先,计算距离的逻辑(假设你只有标记而不是位置对象,因为那些可以做loc1.distanceTo(loc2)):

 private float distBetween(LatLng pos1, LatLng pos2) { return distBetween(pos1.latitude, pos1.longitude, pos2.latitude, pos2.longitude); } /** distance in meters **/ private float distBetween(double lat1, double lng1, double lat2, double lng2) { double earthRadius = 3958.75; double dLat = Math.toRadians(lat2 - lat1); double dLng = Math.toRadians(lng2 - lng1); double a = Math.sin(dLat / 2) * Math.sin(dLat / 2) + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * Math.sin(dLng / 2) * Math.sin(dLng / 2); double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); double dist = earthRadius * c; int meterConversion = 1609; return (float) (dist * meterConversion); } 

接下来,select最近标记的代码:

 private Marker getNearestMarker(List<Marker> markers, LatLng origin) { Marker nearestMarker = null; double lowestDistance = Double.MAX_VALUE; if (markers != null) { for (Marker marker : markers) { double dist = distBetween(origin, marker.getPosition()); if (dist < lowestDistance) { nearestMarker = marker; lowestDistance = dist; } } } return nearestMarker; } 

也许与您的用例不相关,但我使用该algorithm来select基于预定义距离的最近的标记。 这样我剔除了很多不必要的标记:

 private List<Marker> getSurroundingMarkers(List<Marker> markers, LatLng origin, int maxDistanceMeters) { List<Marker> surroundingMarkers = null; if (markers != null) { surroundingMarkers = new ArrayList<Marker>(); for (Marker marker : markers) { double dist = distBetween(origin, marker.getPosition()); if (dist < maxDistanceMeters) { surroundingMarkers.add(marker); } } } return surroundingMarkers; } 

希望这可以帮助你

这段代码可以帮助你获得距离: https : //github.com/BeyondAR/beyondar/blob/master/android/BeyondAR_Framework/src/com/beyondar/android/util/math/Distance.java

这里是我实现一个所谓的KDTree,由三个类组成:KDTree,KDTNode和KDTResult。 你最终需要的是使用KDTree.createTree()来创buildKDTree,它返回树的根节点并获取所有传入的固定点。然后使用KDTree.findNearestWp()来查找距离给定位置最近的航点。

KDTree:

 public class KDTree { private Comparator<LatLng> latComparator = new LatLonComparator(true); private Comparator<LatLng> lonComparator = new LatLonComparator(false);; /** * Create a KDTree from a list of Destinations. Returns the root-node of the * tree. */ public KDTNode createTree(List<LatLng> recList) { return createTreeRecursive(0, recList); } /** * Traverse the tree and find the nearest WP. * * @param root * @param wp * @return */ static public LatLng findNearestWp(KDTNode root, LatLng wp) { KDTResult result = new KDTResult(); findNearestWpRecursive(root, wp, result); return result.nearestDest; } private static void findNearestWpRecursive(KDTNode node, LatLng wp, KDTResult result) { double lat = wp.latitude; double lon = wp.longitude; /* If a leaf node, calculate distance and return. */ if (node.isLeaf) { LatLng dest = node.wp; double latDiff = dest.latitude - lat; double lonDiff = dest.longitude - lon; double squareDist = latDiff * latDiff + lonDiff * lonDiff; // Replace a previously found nearestDest only if the new one is // nearer. if (result.nearestDest == null || result.squareDistance > squareDist) { result.nearestDest = dest; result.squareDistance = squareDist; } return; } boolean devidedByLat = node.depth % 2 == 0; boolean goLeft; /* Check whether left or right is more promising. */ if (devidedByLat) { goLeft = lat < node.splitValue; } else { goLeft = lon < node.splitValue; } KDTNode child = goLeft ? node.left : node.right; findNearestWpRecursive(child, wp, result); /* * Check whether result needs to be checked also against the less * promising side. */ if (result.squareDistance > node.minSquareDistance) { KDTNode otherChild = goLeft ? node.right : node.left; findNearestWpRecursive(otherChild, wp, result); } } private KDTNode createTreeRecursive(int depth, List<LatLng> recList) { KDTNode node = new KDTNode(); node.depth = depth; if (recList.size() == 1) { // Leafnode found node.isLeaf = true; node.wp = recList.get(0); return node; } boolean divideByLat = node.depth % 2 == 0; sortRecListByDimension(recList, divideByLat); List<LatLng> leftList = getHalfOf(recList, true); List<LatLng> rightList = getHalfOf(recList, false); // Get split point and distance to last left and first right point. LatLng lastLeft = leftList.get(leftList.size() - 1); LatLng firstRight = rightList.get(0); double minDistanceToSplitValue; double splitValue; if (divideByLat) { minDistanceToSplitValue = (firstRight.latitude - lastLeft.latitude) / 2; splitValue = lastLeft.latitude + Math.abs(minDistanceToSplitValue); } else { minDistanceToSplitValue = (firstRight.longitude - lastLeft.longitude) / 2; splitValue = lastLeft.longitude + Math.abs(minDistanceToSplitValue); } node.splitValue = splitValue; node.minSquareDistance = minDistanceToSplitValue * minDistanceToSplitValue; /** Call next level */ depth++; node.left = createTreeRecursive(depth, leftList); node.right = createTreeRecursive(depth, rightList); return node; } /** * Return a sublist representing the left or right half of a List. Size of * recList must be at least 2 ! * * IMPORTANT !!!!! Note: The original list must not be modified after * extracting this sublist, as the returned subList is still backed by the * original list. */ List<LatLng> getHalfOf(List<LatLng> recList, boolean leftHalf) { int mid = recList.size() / 2; if (leftHalf) { return recList.subList(0, mid); } else { return recList.subList(mid, recList.size()); } } private void sortRecListByDimension(List<LatLng> recList, boolean sortByLat) { Comparator<LatLng> comparator = sortByLat ? latComparator : lonComparator; Collections.sort(recList, comparator); } class LatLonComparator implements Comparator<LatLng> { private boolean byLat; public LatLonComparator(boolean sortByLat) { this.byLat = sortByLat; } @Override public int compare(LatLng lhs, LatLng rhs) { double diff; if (byLat) { diff = lhs.latitude - rhs.latitude; } else { diff = lhs.longitude - rhs.longitude; } if (diff > 0) { return 1; } else if (diff < 0) { return -1; } else { return 0; } } } } 

KDTNode:

 /** Node of the KDTree */ public class KDTNode { KDTNode left; KDTNode right; boolean isLeaf; /** latitude or longitude of the nodes division line. */ double splitValue; /** Distance between division line and first point. */ double minSquareDistance; /** * Depth of the node in the tree. An even depth devides the tree in the * latitude-axis, an odd depth devides the tree in the longitude-axis. */ int depth; /** The Waypoint in case the node is a leaf node. */ LatLng wp; } 

KDTResult:

 /** Holds the result of a tree traversal. */ public class KDTResult { LatLng nearestDest; // I use the square of the distance to avoid square-root operations. double squareDistance; } 

请注意,我正在使用简化的距离计算,在我的情况下,因为我只对附近的航点感兴趣。 对于更远的点,这可能导致得不到最近的点。 以米为单位的东西距离表示的两个经度的绝对差异取决于测量该差异的纬度。 这在我的algorithm中没有考虑到,而且我不确定这个效果在你的情况下的相关性。

在二维中search单点(可能频繁变化)和大点集之间的最小距离的有效方法是使用QuadTree 。 开始构buildQuadTree需要花费(即将标记位置添加到数据结构中),因此您只需要执行一次(或尽可能不频繁地执行此操作)。 但是,一旦build立起来,search最接近的点通常会比大型集合中所有点的powershell比较快。

BBN的OpenMap项目有一个开源的QuadTree Java实现 ,我相信应该在Android上有一个get(float lat, float lon)方法来返回最近的点。

Google的android-maps-utils库也有一个开源的QuadTree实现,可以在Android上运行,但是由于目前它只支持search(Bounds bounds)操作来返回给定边界框中的一组点而不是最接近input点的点。 但是,可以修改它来执行最近的点search。

如果你有一个相对较less的点(70-80可能足够小),那么在现实世界的性能比较可能会执行QuadTree解决scheme相似的时间。 但是,这也取决于您计划重新计算最近点的频率 – 如果频繁,QuadTree可能是更好的select。

我认为把我的KDTree(见我的其他答案)扩展到一个3维版本也不是太难,下面是结果。 但是到目前为止,我并没有使用这个版本,所以要小心。 我添加了一个unit testing,这表明它至less可以用于你的例子。

 /** 3 dimensional implementation of a KDTree for LatLng coordinates. */ public class KDTree { private XYZComparator xComparator = new XYZComparator(0); private XYZComparator yComparator = new XYZComparator(1); private XYZComparator zComparator = new XYZComparator(2); private XYZComparator[] comparators = { xComparator, yComparator, zComparator }; /** * Create a KDTree from a list of lat/lon coordinates. Returns the root-node * of the tree. */ public KDTNode createTree(List<LatLng> recList) { List<XYZ> xyzList = convertTo3Dimensions(recList); return createTreeRecursive(0, xyzList); } /** * Traverse the tree and find the point nearest to wp. */ static public LatLng findNearestWp(KDTNode root, LatLng wp) { KDTResult result = new KDTResult(); XYZ xyz = convertTo3Dimensions(wp); findNearestWpRecursive(root, xyz, result); return result.nearestWp; } /** Convert lat/lon coordinates into a 3 dimensional xyz system. */ private static XYZ convertTo3Dimensions(LatLng wp) { // See eg // http://stackoverflow.com/questions/8981943/lat-long-to-xyz-position-in-js-not-working double cosLat = Math.cos(wp.latitude * Math.PI / 180.0); double sinLat = Math.sin(wp.latitude * Math.PI / 180.0); double cosLon = Math.cos(wp.longitude * Math.PI / 180.0); double sinLon = Math.sin(wp.longitude * Math.PI / 180.0); double rad = 6378137.0; double f = 1.0 / 298.257224; double C = 1.0 / Math.sqrt(cosLat * cosLat + (1 - f) * (1 - f) * sinLat * sinLat); double S = (1.0 - f) * (1.0 - f) * C; XYZ result = new XYZ(); result.x = (rad * C) * cosLat * cosLon; result.y = (rad * C) * cosLat * sinLon; result.z = (rad * S) * sinLat; result.wp = wp; return result; } private List<XYZ> convertTo3Dimensions(List<LatLng> recList) { List<XYZ> result = new ArrayList<KDTree.XYZ>(); for (LatLng latLng : recList) { XYZ xyz = convertTo3Dimensions(latLng); result.add(xyz); } return result; } private static void findNearestWpRecursive(KDTNode node, XYZ wp, KDTResult result) { /* If a leaf node, calculate distance and return. */ if (node.isLeaf) { double xDiff = node.xyz.x - wp.x; double yDiff = node.xyz.y - wp.y; double zDiff = node.xyz.z - wp.z; double squareDist = xDiff * xDiff + yDiff * yDiff + zDiff * zDiff; // Replace a previously found nearestDest only if the new one is // nearer. if (result.nearestWp == null || result.squareDistance > squareDist) { result.nearestWp = node.xyz.wp; result.squareDistance = squareDist; } return; } int devidedByDimension = node.depth % 3; boolean goLeft; /* Check whether left or right is more promising. */ if (devidedByDimension == 0) { goLeft = wp.x < node.splitValue; } else if (devidedByDimension == 1) { goLeft = wp.y < node.splitValue; } else { goLeft = wp.z < node.splitValue; } KDTNode child = goLeft ? node.left : node.right; findNearestWpRecursive(child, wp, result); /* * Check whether result needs to be checked also against the less * promising side. */ if (result.squareDistance > node.minSquareDistance) { KDTNode otherChild = goLeft ? node.right : node.left; findNearestWpRecursive(otherChild, wp, result); } } private KDTNode createTreeRecursive(int depth, List<XYZ> recList) { KDTNode node = new KDTNode(); node.depth = depth; if (recList.size() == 1) { // Leafnode found node.isLeaf = true; node.xyz = recList.get(0); return node; } int dimension = node.depth % 3; sortWayPointListByDimension(recList, dimension); List<XYZ> leftList = getHalfOf(recList, true); List<XYZ> rightList = getHalfOf(recList, false); // Get split point and distance to last left and first right point. XYZ lastLeft = leftList.get(leftList.size() - 1); XYZ firstRight = rightList.get(0); double minDistanceToSplitValue; double splitValue; if (dimension == 0) { minDistanceToSplitValue = (firstRight.x - lastLeft.x) / 2; splitValue = lastLeft.x + Math.abs(minDistanceToSplitValue); } else if (dimension == 1) { minDistanceToSplitValue = (firstRight.y - lastLeft.y) / 2; splitValue = lastLeft.y + Math.abs(minDistanceToSplitValue); } else { minDistanceToSplitValue = (firstRight.z - lastLeft.z) / 2; splitValue = lastLeft.z + Math.abs(minDistanceToSplitValue); } node.splitValue = splitValue; node.minSquareDistance = minDistanceToSplitValue * minDistanceToSplitValue; /** Call next level */ depth++; node.left = createTreeRecursive(depth, leftList); node.right = createTreeRecursive(depth, rightList); return node; } /** * Return a sublist representing the left or right half of a List. Size of * recList must be at least 2 ! * * IMPORTANT !!!!! Note: The original list must not be modified after * extracting this sublist, as the returned subList is still backed by the * original list. */ List<XYZ> getHalfOf(List<XYZ> xyzList, boolean leftHalf) { int mid = xyzList.size() / 2; if (leftHalf) { return xyzList.subList(0, mid); } else { return xyzList.subList(mid, xyzList.size()); } } private void sortWayPointListByDimension(List<XYZ> wayPointList, int sortBy) { XYZComparator comparator = comparators[sortBy]; Collections.sort(wayPointList, comparator); } class XYZComparator implements Comparator<XYZ> { private int sortBy; public XYZComparator(int sortBy) { this.sortBy = sortBy; } @Override public int compare(XYZ lhs, XYZ rhs) { double diff; if (sortBy == 0) { diff = lhs.x - rhs.x; } else if (sortBy == 1) { diff = lhs.y - rhs.y; } else { diff = lhs.z - rhs.z; } if (diff > 0) { return 1; } else if (diff < 0) { return -1; } else { return 0; } } } /** 3 Dimensional coordinates of a waypoint. */ static class XYZ { double x; double y; double z; // Keep also the original waypoint LatLng wp; } /** Node of the KDTree */ public static class KDTNode { KDTNode left; KDTNode right; boolean isLeaf; /** latitude or longitude of the nodes division line. */ double splitValue; /** Distance between division line and first point. */ double minSquareDistance; /** * Depth of the node in the tree. Depth 0,3,6.. devides the tree in the * x-axis, depth 1,4,7,.. devides the tree in the y-axis and depth * 2,5,8... devides the tree in the z axis. */ int depth; /** The Waypoint in case the node is a leaf node. */ XYZ xyz; } /** Holds the result of a tree traversal. */ static class KDTResult { LatLng nearestWp; // We use the square of the distance to avoid square-root operations. double squareDistance; } } 

这里是unit testing:

 public void testSOExample() { KDTree tree = new KDTree(); LatLng Bangalore = new LatLng(12.971599, 77.594563); LatLng Delhi = new LatLng(28.635308, 77.224960); LatLng Mumbai = new LatLng(19.075984, 72.877656); LatLng Chennai = new LatLng(13.052414, 80.250825); LatLng Kolkata = new LatLng(22.572646, 88.363895); List<LatLng> cities = Arrays.asList(new LatLng[] { Bangalore, Delhi, Mumbai, Chennai, Kolkata }); KDTree.KDTNode root = tree.createTree(cities); LatLng Hyderabad = new LatLng(17.385044, 78.486671); LatLng nearestWp = tree.findNearestWp(root, Hyderabad); assertEquals(nearestWp, Bangalore); } 

在这里,我有办法做到这一点使用数据库。 这是一个计算距离函数:

 public void calculateDistance() { if (latitude != 0.0 && longitude != 0.0) { for(int i=0;i<97;i++) { Location myTargetLocation=new Location(""); myTargetLocation.setLatitude(targetLatitude[i]); myTargetLocation.setLongitude(targetLongitude[i]); distance[i]=myCurrentLocation.distanceTo(myTargetLocation); distance[i]=distance[i]/1000; mdb.insertDetails(name[i],targetLatitude[i], targetLongitude[i], distance[i]); } Cursor c1= mdb.getallDetail(); while (c1.moveToNext()) { String station_name=c1.getString(1); double latitude=c1.getDouble(2); double longitude=c1.getDouble(3); double dis=c1.getDouble(4); //Toast.makeText(getApplicationContext(),station_name+" & "+latitude+" & "+longitude+" & "+dis,1).show(); } Arrays.sort(distance); double nearest_distance=distance[0]; Cursor c2=mdb.getNearestStationName(); { while (c2.moveToNext()) { double min_dis=c2.getDouble(4); if(min_dis==nearest_distance) { String nearest_stationName=c2.getString(1); if(btn_clicked.equals("source")) { source.setText(nearest_stationName); break; } else if(btn_clicked.equals("dest")) { destination.setText(nearest_stationName); break; } else { } } } } } else { Toast.makeText(this, "GPS is Not Working Properly,, please check Gps and Wait for few second", 1).show(); } } 

我们所要做的就是创build一个名为targetLatitude [i]和targetLongitude [i]的数组,其中包含您要计算距离的所有地点的Lats和Longs。 然后创build一个数据库,如下所示:

 public class MyDataBase { SQLiteDatabase sdb; MyHelper mh; MyDataBase(Context con) { mh = new MyHelper(con, "Metro",null, 1); } public void open() { try { sdb=mh.getWritableDatabase(); } catch(Exception e) { } } public void insertDetails(String name,double latitude,double longitude,double distance) { ContentValues cv=new ContentValues(); cv.put("name", name); cv.put("latitude", latitude); cv.put("longitude",longitude); cv.put("distance", distance); sdb.insert("stations", null, cv); } public void insertStops(String stop,double latitude,double logitude) { ContentValues cv=new ContentValues(); cv.put("stop", stop); cv.put("latitude", latitude); cv.put("logitude", logitude); sdb.insert("stops", null, cv); } public Cursor getallDetail() { Cursor c=sdb.query("stations",null,null,null,null,null,null); return c; } public Cursor getNearestStationName() { Cursor c=sdb.query("stations",null,null,null,null,null,null); return c; } public Cursor getStops(String stop) { Cursor c; c=sdb.query("stops",null,"stop=?",new String[]{stop},null, null, null); return c; } class MyHelper extends SQLiteOpenHelper { public MyHelper(Context context, String name, CursorFactory factory, int version) { super(context, name, factory, version); // TODO Auto-generated constructor stub } @Override public void onCreate(SQLiteDatabase db) { // TODO Auto-generated method stub db.execSQL("Create table stations(_id integer primary key,name text," + " latitude double, longitude double, distance double );"); db.execSQL("Create table stops(_id integer primary key,stop text," + "latitude double,logitude double);"); } @Override public void onUpgrade(SQLiteDatabase db, int oldVersion, int newVersion) { // TODO Auto-generated method stub } } public void deleteDetail() { sdb.delete("stations",null,null); sdb.delete("stops",null,null); } public void close() { sdb.close(); } } 

然后执行CalculateDistancefunction,你可以得到最近的站名。