根据经纬度求最近点的三种解法java实现
生活随笔
收集整理的這篇文章主要介紹了
根据经纬度求最近点的三种解法java实现
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
文章目錄
- 1. geoHash
- 2. kdTree算法求最近點
- 3.暴力法
- 4.利用elasticsearch或者lucene
1. geoHash
首先對經緯度點進行編碼：
geohash算法測試結果：
前綴匹配長度為2： (輸入：100個坐標點)正確率 92% 無法計算 0% 平均計算時間：17.5ms (1000)正確率 92.6% 無法計算 0% 平均計算時間：16.4ms 前綴匹配長度為3： (100)正確率 51% 無法計算 35% 平均計算時間：3.784313725490196ms (1000)正確率 58% 無法計算 29% time:2.4ms
2.2083333333333335** 暴力算法測試平均時間2ms geoHash算法java源碼：
根據編碼求最近點：
package net.work.geoHash;import java.io.BufferedReader; import java.io.IOException; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.Map.Entry;import java.util.Scanner; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet;public class InputCity {public static HashMap<Integer, String> decode_map;public static HashMap<Integer, Location> city_map;public GeoHash geoHash = new GeoHash();public LenCompator compator = new LenCompator();static {decode_map = new HashMap<Integer, String>();city_map = new HashMap<Integer, Location>();}class LenCompator implements Comparator<Common>{@Overridepublic int compare(Common o1, Common o2) {return Integer.compare(o2.len, o1.len);}}class Common{Integer id;int len;public Common(Integer id, int len) {this.id = id;this.len = len;}@Overridepublic String toString() {return "Common [id=" + id + ", len=" + len + "]";}}class Location{int id;String full_name;int pid;String name;double x;double y;public Location() {}public Location(int id, String full_name, int pid, String name, double x, double y) {this.id = id;this.full_name = name;this.pid = pid;this.name = name;this.x = x;this.y = y;}@Overridepublic String toString() {return "Location [id=" + id + ", full_name=" + full_name + ", pid=" + pid + ", name=" + name + ", x=" + x+ ", y=" + y + "]";}}class ReturnBean{Location location;double distance;public ReturnBean(Location location, double distance) {this.location = location;this.distance = distance;}}public void init() throws IOException {String data = util.Directory.GetAppPath("data");String decode = data + "decode.txt";String city = data + "行政區劃及經緯.txt";BufferedReader br = util.MyFileTool.GetBufferReader(decode);BufferedReader br1 = util.MyFileTool.GetBufferReader(city);while(br.ready()) {String line = br.readLine();String[] ls = line.split("\t");int id = Integer.parseInt(ls[0]);String code = ls[1];System.out.println("id: " + id + " " + "code: " + code);decode_map.put(id, code);}while(br1.ready()) {String line = br1.readLine();String[] ls = line.split(" ");int id = Integer.parseInt(ls[0]);String full_name = ls[1];int pid = Integer.parseInt(ls[2]);String name = ls[3];double x = Double.parseDouble(ls[4]);double y = Double.parseDouble(ls[5]);city_map.put(id, new Location(id, full_name, pid, name, x, y));}br.close();br1.close();}public int getPreCommonLength(String pre, String las) {int len = 0;for(int i = 0; i < pre.length(); i++) {if(len == i && pre.charAt(i) == las.charAt(i)) {len ++;}else {break;}}return len;}public ArrayList<Common> getNearbyLocations(String code, LenCompator compator){ArrayList<Common> common_list = new ArrayList<Common>();Set<Entry<Integer,String>> set = decode_map.entrySet();int limit = 3;for(Entry<Integer,String> elem : set) {int id = elem.getKey();String encode = elem.getValue();int len = getPreCommonLength(encode, code);if(len < limit) {continue;}common_list.add(new Common(id, len));Collections.sort(common_list, compator);}return common_list;}public Double getTwoPointDistanceSquare(double x1, double y1, double x2, double y2) {return (x1 - x2) * (x1 - x2) + (y1 - y2)*(y1 - y2);}//如果距離相同只顯示一個地點public ReturnBean getSmallestDistanceLocation(double x, double y, ArrayList<Common> common_set, int count) {int i = 0;Integer id;Location minDistanceLocation = null;double minDistance = Double.MAX_VALUE;for(Common com_bean : common_set) {id = com_bean.id;Location location = city_map.get(id);if(location == null) {continue;}Double distance = getTwoPointDistanceSquare(x, y, location.x, location.y);if(distance < minDistance) {minDistance = distance;minDistanceLocation = location;}if(i == count) {break;}}return new ReturnBean(minDistanceLocation, Math.sqrt(minDistance));}public ReturnBean getSmallestDistanceLocation(double x, double y, ArrayList<Common> common_set) {int i = 0;Integer id;Location minDistanceLocation = new Location();double minDistance = Double.MAX_VALUE;for(Common com_bean : common_set) {id = com_bean.id;Location location = city_map.get(id);if(location == null) {continue;}Double distance = getTwoPointDistanceSquare(x, y, location.x, location.y);if(distance < minDistance) {minDistance = distance;minDistanceLocation = location;}}return new ReturnBean(minDistanceLocation, Math.sqrt(minDistance));}public HashMap<String, String> getDistance(double x, double y){long s = System.currentTimeMillis();String encode = geoHash.encode(y, x); // double[] ds = geoHash.decode(encode);ArrayList<Common> common_list = getNearbyLocations(encode, compator);ReturnBean ans = getSmallestDistanceLocation(x, y, common_list, 10); // if(ans == null) { // ans = inputCity.getSmallestDistanceLocation(x, y, common_list); // }HashMap<String, String> map = new HashMap<String, String>();map.put("status", "ok");if(ans.location == null || ans.location.id == 0) {System.out.println("超出定位范圍，無法算出");map.put("status", "error");}else {map.put("id", ans.location.id + "");map.put("path", ans.location.x + "," + ans.location.y);map.put("name", ans.location.name);map.put("len",Math.sqrt(ans.distance) + "");}map.put("input", x + "," + y);map.put("decode", encode);map.put("map_size", common_list.size() + "");long e = System.currentTimeMillis();map.put("time", (e - s) + "");return map;}public static void main(String[] args) throws IOException {GeoHash geoHash = new GeoHash();InputCity inputCity = new InputCity();inputCity.init();LenCompator compator = inputCity.new LenCompator();int count = 10;while(true) {//西城區附近點: 116.368049 39.910508 測試結果：牛街街道//來廣營地鐵十四號線東路： 116.473489 40.026145 結果：//116.498464 39.997745//116.496991 39.999348//116.473489 40.026145//出錯例子:116.013857,29.712846 目標地點:九江市 定位：浙江省 // Scanner sc = new Scanner(System.in); // String[] ss = sc.next().split(",");double x = 56;double y = 78;//double x = Double.parseDouble(ss[0]);//double y = Double.parseDouble(ss[1]);long s = System.currentTimeMillis();//經度、維度String encode = geoHash.encode(y, x);System.out.println("輸入坐標: " + x + " " + y);System.out.println("經緯度編碼： " + encode);double[] ds = geoHash.decode(encode);System.out.println("解碼: " + ds[1] + " " + ds[0]);ArrayList<Common> common_list = inputCity.getNearbyLocations(encode, compator);System.out.println("common_list_size: " + common_list.size());System.out.println("地方編碼距離: " + common_list);ReturnBean ans = inputCity.getSmallestDistanceLocation(x, y, common_list, count); // if(ans == null) { // ans = inputCity.getSmallestDistanceLocation(x, y, common_list); // }if(ans.location == null) {System.out.println("超出定位范圍，無法算出");}else {System.out.println("最近點: " + ans.location);System.out.println("最近點坐標: " + ans.location.x + "," + ans.location.y);System.out.println("距離: " + ans.distance);long e = System.currentTimeMillis();System.out.println("spend time: " + (e - s) + "ms");}System.exit(-1);}} }優秀文章：
https://blog.csdn.net/youhongaa/article/details/78816700
https://blog.csdn.net/u011497262/article/details/81210634
2. kdTree算法求最近點
原理：最近臨點問題
在空間上給出一個點，求解距離該點最近的點。
首先通過二叉樹搜索（比較待查詢節點和分裂節點的分裂維的值，小于等于就進入左子樹分支，等于就進入右子樹分支直到葉子結點），順著“搜索路徑”很快能找到最近鄰的近似點，也就是與待查詢點處于同一個子空間的葉子結點；
然后再回溯搜索路徑，并判斷搜索路徑上的結點的其他子結點空間中是否可能有距離查詢點更近的數據點，如果有可能，則需要跳到其他子結點空間中去搜索（將其他子結點加入到搜索路徑）。
重復這個過程直到搜索路徑為空。
需要用到一個隊列，存儲需要回溯的點，在判斷其他子節點空間中是否有可能有距離查詢點更近的數據點時，做法是以查詢點為圓心，以當前的最近距離為半徑畫圓，這個圓稱為候選超球（candidate hypersphere），如果圓與回溯點的軸相交，則需要將軸另一邊的節點都放到回溯隊列里面來。
KDTree就是超平面都垂直于軸的BSPTree
原文：https://blog.csdn.net/define_us/article/details/79855133
求最近點代碼：
package net.work.kdTree;import java.io.BufferedReader; import java.io.IOException; import java.util.Arrays; import java.util.Collections; import java.util.LinkedList; import java.util.List;public class KDTreeMain {public static int KDTCount = 0; // 統計在kdt 搜索的時候，計算了和幾個點的距離public static Node root;public static int deep = 0;public static int count_point = 0;//樣本點個數(經緯度點的總個數)public static List<Point> pointList;public static KDTreeMain kdt;public static void init(){int xn = 2; // 樣本點維數int deep = 0; // 軸String data = util.Directory.GetAppPath("data") + "行政區劃及經緯.txt";BufferedReader br = util.MyFileTool.GetBufferReader(data);// 準備數據pointList = new LinkedList<Point>();try {while (br.ready()) {String line = br.readLine();String[] ls = line.split(" ");int id = Integer.parseInt(ls[0]);String full_name = ls[1];int pid = Integer.parseInt(ls[2]);String name = ls[3];System.out.println(name);double lnt = Double.parseDouble(ls[4]);double lat = Double.parseDouble(ls[5]);double[] d = new double[xn];d[0] = lnt;d[1] = lat;//擴大十倍for(int i = 0; i < 10; i++) {pointList.add(new Point(id, full_name, pid, name, d));count_point ++;} // pointList.add(new Point(id, full_name, pid, name, d)); // count_point ++;}} catch (NumberFormatException | IOException e) {e.printStackTrace();}try {br.close();} catch (IOException e) {e.printStackTrace();}// build treeSystem.out.println("beging insert...");double t1 = System.currentTimeMillis();kdt = new KDTreeMain();root = new Node();insert(root, pointList, deep);double t2 = System.currentTimeMillis();System.out.println("buld kdt time = " + (t2 - t1));}public static void main(String[] args) throws IOException {init();// 目標點double[] f = new double[2];//87.356426,40.800009f[0] = 87.356426;f[1] = 40.800009;Point p = new Point(f);// KDT搜索double t3 = System.currentTimeMillis();double min_dis = Double.MAX_VALUE;Point result_p;result_p = query(root, p, new Point(min_dis), deep);double t4 = System.currentTimeMillis();System.out.println("查詢時間：" + (t4 - t3));System.out.println("最近點 " + result_p);System.out.println("KDTCount = " + KDTCount);// 暴力法double t5 = System.currentTimeMillis();int index = 0;double best2 = Double.MAX_VALUE;for (int i = 0; i < count_point; i++) {double dist = getDist(p, pointList.get(i));if (dist < best2) {best2 = dist;index = i;}}double t6 = System.currentTimeMillis();System.out.println("暴力時間： " + (t6 - t5));System.out.println("最短距離： " + best2);// System.out.println("goal point = " + p.x[0] + " , " + p.x[1]);// System.out.println("neast point = " + pointList.get(index).x[0] + " , " + pointList.get(index).x[1]);}// build kdtreestatic private void insert(Node root, List<Point> pointList, int deep) {System.out.println("構建樹....");System.out.println(3);int mid = pointList.size() / 2;// 排序后拿到中位數Point.deep = deep;Collections.sort(pointList);// 類似快排的方法拿到中位數// getMedian(pointList, 0, pointList.size() - 1, mid, deep);// showList(pointList);// System.out.println("=========================");int pl = mid;int pr = mid;while(pl >= 0 && pointList.get(pl).x[deep] == pointList.get(mid).x[deep]) pl--;while(pr < pointList.size() && pointList.get(pr).x[deep] == pointList.get(mid).x[deep]) pr++;List<Point> pointListLeft = pointList.subList(0, pl + 1);List<Point> pointListMid = pointList.subList(pl + 1, pr);List<Point> pointListRight = pointList.subList(pr, pointList.size());root.pointList = pointListMid;if (pointListLeft.size() > 0) {root.l = new Node();System.out.println(1);insert(root.l, pointListLeft, (deep + 1) % pointList.get(0).x.length);}System.out.println(1);if (pointListRight.size() > 0) {root.r = new Node();System.out.println(2);insert(root.r, pointListRight, (deep + 1) % pointList.get(0).x.length);}}// search the nearest point to p in KDTreestatic Point query(Node root, Point p, Point best_p, int deep) {if (root == null) return best_p; double dist; if (root.l == null && root.r == null) { for (int i = 0; i < root.pointList.size(); i++) { KDTCount++; dist = getDist(root.pointList.get(i), p); if(dist < best_p.len) {best_p = root.pointList.get(i);best_p.len = dist;}} return best_p; } // left or right if (p.x[deep] <= root.pointList.get(0).x[deep]) { best_p = query(root.l, p, best_p, (deep + 1) % p.x.length);} else { best_p = query(root.r, p, best_p, (deep + 1) % p.x.length);} // cur for (int i = 0; i < root.pointList.size(); i++) { KDTCount++; dist = getDist(root.pointList.get(i), p); if(dist < best_p.len) {best_p = root.pointList.get(i);best_p.len = dist;}} // another side if (best_p.len >= Math.abs(p.x[deep] - root.pointList.get(0).x[deep])) { Point another_p = new Point(Double.MAX_VALUE);if (p.x[deep] <= root.pointList.get(0).x[deep]) { another_p = query(root.r, p, best_p, (deep + 1) % p.x.length);} else { another_p = query(root.l, p, best_p, (deep + 1) % p.x.length);} if (another_p.len < best_p.len) { best_p = another_p;best_p.len = another_p.len;} } return best_p; }// print kdtree@SuppressWarnings("unused")private static void showKDTree(Node root, char[] path, int pi) {if (root == null) return;System.out.print(pi + "# ");for (int i = 0; i < pi; i++) {System.out.print(path[i] + " ");}// midshowList(root.pointList);// leftpath[pi++] = 'L';showKDTree(root.l, path, pi);pi--;// rightpath[pi++] = 'R';showKDTree(root.r, path, pi);pi--;}// 歐式距離private static double getDist(Point p1, Point p2) {double sum = 0;for (int i = 0; i < p1.x.length; i++) {sum += (p1.x[i] - p2.x[i]) * (p1.x[i] - p2.x[i]);}if (sum == 0) return Double.MAX_VALUE;return Math.sqrt(sum);}// 類似快排的思想拿到中位數，O(n)時間復雜度@SuppressWarnings("unused")private void getMedian(List<Point> pointList, int l, int r, int k, int deep) {if (l == r && k == 0) return; int pl = l; int pr = r; double[] tmp = pointList.get(l).x; while (pl < pr) { while (pl < pr && pointList.get(pr).x[deep] > tmp[deep]) pr--; if (pl >= pr) break; pointList.get(pl++).x = pointList.get(pr).x; while (pl < pr && pointList.get(pl).x[deep] < tmp[deep]) pl++; if (pl >= pr) break; pointList.get(pr--).x = pointList.get(pl).x;} pointList.get(pl).x = tmp; if(pl - l == k) return; if(pl - l > k) { getMedian(pointList, l, pl - 1, k, deep); } else { getMedian(pointList, pl + 1, r, k - (pl - l + 1), deep); } }// 打印一個點列表private static void showList(List<Point> pointList) {for (int i = 0; i < pointList.size(); i++) {for( int j = 0; j < pointList.get(i).x.length; j++) {System.out.print(pointList.get(i).x[j] + ",");}System.out.print(" / ");}System.out.println();} } // kdtree里的節點 class Node {List<Point> pointList = new LinkedList<Point>();Node l = null;Node r = null; } // 數據點 class Point implements Comparable<Point>{public static int deep = 0;double[] x;@Overridepublic String toString() {return "Point [x=" + Arrays.toString(x) + ", id=" + id + ", name=" + name + ", full_name=" + full_name+ ", pid=" + pid + ", len=" + len + "]";}int id;String name;String full_name;int pid;double len;public Point() {}public Point(double len) {this.len = len;}public Point(double[] d) {x = new double[d.length];for (int i = 0; i < d.length; i++) {x[i] = d[i];}}public Point(int id, String full_name, int pid, String name, double[] x){this.id = id;this.full_name = full_name;this.pid = pid;this.name = name;this.x = x;}public int compareTo(Point o) {// return (int)(this.x[deep] == other.x[deep]); 出錯，因為x的值在0~1之間，那么int都是0了Point other = (Point)o;if (this.x[deep] == other.x[deep]) return 0;if (this.x[deep] > other.x[deep]) return 1;return -1;} }3.暴力法
package net.work.baoli;import java.io.BufferedReader; import java.io.File; import java.io.FileOutputStream; import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner;/**** 2018年11月29日*/ public class baoli {public static ArrayList<Point> list;static {list = new ArrayList<Point>();String t = util.Directory.GetAppPath("data") + "行政區劃及經緯.txt";BufferedReader br = util.MyFileTool.GetBufferReader(t);try {while(br.ready()) {String line = br.readLine();String[] ls = line.split(" ");int id = Integer.parseInt(ls[0]);String full_name = ls[1];int pid = Integer.parseInt(ls[2]);String name = ls[3];System.out.println(name);double lnt = Double.parseDouble(ls[4]);double lat = Double.parseDouble(ls[5]);//擴大十倍 // for(int i = 0; i < 10; i ++) { // list.add(new Point(id, full_name, pid, name, lnt, lat));list.add(new Point(id, full_name, pid, name, lnt, lat)); // }}} catch (NumberFormatException | IOException e) {e.printStackTrace();}}static class Point{int id;String name;String full_name;int pid;double x,y;public Point(){}public Point(int id, String full_name, int pid, String name, double x, double y){this.id = id;this.full_name = full_name;this.pid = pid;this.name = name;this.x = x;this.y = y;}}public static Double getTwoPointDistanceSquare(double x1, double y1, double x2, double y2) {return (x1 - x2) * (x1 - x2) + (y1 - y2)*(y1 - y2);}public static HashMap<String, String> getDistace(double x, double y) throws IOException {long s = System.currentTimeMillis();double min_x = 0, min_y = 0;double min_dis = Double.MAX_VALUE;String min_name = null;int min_id = 0;for(Point p : list) {Double dis = getTwoPointDistanceSquare(p.x, p.y, x, y);if(min_dis > dis) {min_id = p.id;min_dis = dis;min_x = p.x;min_y = p.y;min_name = p.name;}}HashMap<String, String> map = new HashMap<String, String>();map.put("id", min_id + "");map.put("input", x + ","+ y);map.put("path", min_x + "," + min_y);map.put("len", Math.sqrt(min_dis) + "");map.put("name", min_name);long e = System.currentTimeMillis();map.put("time", (e - s) + "");return map;}public static void main(String[] args) throws NumberFormatException, IOException {while(true){Scanner sc = new Scanner(System.in);String[] ss = sc.next().split(",");double x = Double.parseDouble(ss[0]);double y = Double.parseDouble(ss[1]);HashMap<String, String> map = getDistace(x, y);System.out.println(map);}} } 總結：暴力法：
(1000)正確率 100% 平均計算時間：0.9ms
如果樣本(行政區劃及經緯.txt)擴大十倍：平均時間:3ms
geooHash(不適合計算青海、內蒙古、新疆等點分散比較大的省份，如果其他省份準確率接近99%):
前綴匹配長度為2：
(100)正確率 92% 無法計算 0% 平均計算時間：17.5ms
(1000)正確率 92.6% 無法計算 0% 平均計算時間：16.4ms
前綴匹配長度為3：
(100)正確率 51% 無法計算 35% 平均計算時間：3.784313725490196ms
(1000)正確率 58% 無法計算 29% time:2.4ms 2.2083333333333335ms
如果樣本(行政區劃及經緯.txt)擴大十倍：前綴匹配長度為3：正確率： 54.3% 平均時間：1.8176795580110496ms
優點：當樣本的數據量多的時候可以體現geoHash的優勢
缺點：準確率不是很高
kdTree:
缺點：初始化構建樹的時候花費時間比較長
(1000)正確率 100% 平均計算時間：54ms
樣本數量擴大十倍：平均時間 2523ms
knn算法當取前k個數據為1時候和暴力法原理相同，時間復雜度更高
4.利用elasticsearch或者lucene
如果數據量特別大，錄入到es建立索引，然后利用es提供的求最近距離的API即可
總結
以上是生活随笔為你收集整理的根据经纬度求最近点的三种解法java实现的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 【转载保存】Lucene 实战教程第六章
- 下一篇： sparkSQL操作hiveSQL