附近点搜索算法

本文主要是介绍附近点搜索算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：

闲来无事，想没事找事，研究个算法玩，前些日子看了knn算法颇有感触，公司有个搜附近电影院功能，是用mysql数据库按经纬度实现的，数据库电影院数据现在只是几千家，以后多了效率就低了吧，不管怎么样想自己写个搜附近的算法，然后开始在网上找，最后想了个算法，虽然也敲出来了，但是漏洞很多，不过也跟大家分享一下。

解决什么问题？

其实就是搜附近点的问题，你旅游想找附近的酒店，想找附近的厕所，都是用的这个算法，那么我们就把问题定义一下，就是在地球上有很多点，你有个小飞镖，啪戳在旋转的地球上，问离着飞镖最近的N个点，这里点用经度和维度表示。

如何解决？

划分格子

最基本的方案肯定是遍历所有点，计算与飞镖的距离，然后排序，取最近的N个，如果有1亿个点要循环一亿次吗？那我们用什么方法过滤肯定离得不进的点，然后找肯定离着近的，计算个距离排个顺序就行了。

那么我们先将地球平铺开如图

经度 -180 到正 180

维度-90到90

按照四象限，平均划分,把区域分成一个一个的小区域，这样我们查飞镖命中在哪个区域，然后再查飞镖附近的格子，就能查出飞镖命中附近的点了

我们用四叉树来存取分出的四个格子，如图

用四叉树存储，将所有的点放到最后的叶子节点中，也就是最后划分的每个小方块中，上面每个节点都存着划分时候的经纬度，这样我们根据小飞镖的经纬度和每个节点的经纬度，都能找到小飞镖该划分到四个格子中的哪个，最后找到小飞镖到底在哪个格子里，这个时候我们就能找离着小飞镖最近的几个点了，也就最后找到这个小格子里的所有有点。（所有的点根据小飞镖划分的方式也能划分到格子中这个就带过不讲了）。

那么我们已经能找到小飞镖在哪个格子中，如果我们想找小飞镖附近的10个点，但是格子里面不够10个点，只有5个点，那我们怎么找格子附近的8个格子，获取他们的点呢？这个就要给每个格子编码，然后算出当前格子四周的格子就行啦。

给格子编码

我们找到了一个格子，那么这个格子中的数据不够我们找附近的点，那们找到这个格子附近的格子，就能找到附近的点，如果不够再一圈圈的扩展，就像在水里滴了一滴水。

每个格子假设有两个值x和y，如图 F的四周 ABCEGIJK 编号A等于f -1 -1 编号 B等于 F 0 -1 编号 K等于 +1+1 不管任意一点，都是这个算法能算出四周的格子

但是我们划分格子的时候格子一开始是不固定的，所以也不好这样编号，我们用二进制编号，而四周的计算方式是不变的，二进制编号如图，这里展示y的划分，x的划分同理，最后就能和上面一样，只不过是二进制的，方便在递归划分的时候分格子

这样我们通过四叉树能找到最近的叶子节点，而每个叶子节点就是一个格子，通过对格子编号，能找到他附近的格子，那么算法到这就能过滤大部分了，不过算法有很多问题，很多 - -

问题1

地球是圆的如果说x的划分也就是纬度的划分格子编号 00...00 和 1111...111这两个边界点可以通过 1111+1的时候溢出编程0000 这样就能接上，就是不至于在分界线，算不出左右的方格子，那么南北极点算附近简直就是噩梦= = ，我至今没想到解决方案，所以这个方案只适用于一块比较小的地区，比如说把整个中国框起来。南北极四周方格如图，蓝色的是中间的点，涂黑的是四周方格。

问题2

在方格子划分的时候，必须是方格子，也就是格子的长宽必须一样，我们最开始的第一个格子必须是方的，如果不是方的会导致画出的格子是长条或者竖条的，在查找算距离之后，不准，会出现别的格子中也有比现有格子近的点。

问题3

格子是方的，范围却是圆的，一个方格子中找的点，有可能格子之外还有比这个近的，如图，A点就比B点更远，但我们很有可能搜索不到B点所在的那个格子就结束了，当然这个问题已经解决了，就是如果搜索附近10个点，在扩展格子直到搜索到的点数>10后，再扩展一圈，然后统一进行排序,FUCK !写到这我发现这个问题没解决，如果层数足够多，多一层是不能弥补这个问题的，而且层数越多这个问题越明显，我方了。。。。

问题4

这个问题就是算法应用问题了，虽然四叉树这个结构，增加删除点非常方便，删除点只要找到对应方格，然后删除，添加只要找到对应方格，添加进去，但是如何划分方格将是个问题，如果划分多了，每个格子里只有很少的点或者甚至没有，导致一直在扩散方格查点，然而跟这个问题类似的就是如果点不是相对均匀分布的，也就是在一片方格子中有很多空格子，这个就很头疼，有可能你已经查了好几层格子却没有一个点。。。如图，所以一个是想好格子划分的粒度，一个是数据最好是相对均匀分布的 = =

如果我要找A点附近的10个点，但是你看大多数点都离着A点很远，需要循环好几层。

代码

代码按照上述基本实现了，但是没有测过，懒得测- -

package 定位电影院;import lombok.Getter;
import lombok.Setter;import java.math.BigDecimal;
import java.util.LinkedList;
import java.util.List;/*** 用于储存经纬度* 电影院id* 电影院名称*/
@Setter
@Getter
public class Area {//经度private BigDecimal x;//纬度private BigDecimal y;private List<Node> nodeList;//第一象限private Area firstQuadrant;//第二象限private Area secondQuadrant;//第三象限private Area thirdQuadrant;//第四象限private Area fourthQuadrant;//记录区域编号 经度private List<Integer> longitudeCode;//记录区域编号 纬度private List<Integer> latitudeCode;public Area(BigDecimal x, BigDecimal y) {this.x = x;this.y = y;createList();}public Area(List<Integer> longitudeCode, List<Integer> latitudeCode) {this.longitudeCode = longitudeCode;this.latitudeCode = latitudeCode;}public Area() {createList();}private void createList(){longitudeCode = new LinkedList<>();latitudeCode = new LinkedList<>();}//加一位public void longitudeCodeAdd(int y){longitudeCode.add(y);}//加一位public void latitudeCodeAdd(int x){latitudeCode.add(x);}//加1private void add(List<Integer> list) {int size = list.size();for (int i = 1; i < size; i++) {Integer position = list.get(size-i);//如果是1就 进位if (position == 1) {list.set(size-i,0);}else{list.set(size-i,1);break;}}}//减1private void minus(List<Integer> list){int size = list.size();for (int i = 1; i < size; i++) {Integer position = list.get(size-i);//如果是0就 就进位去减去if (position == 0) {if (size-i == 0) {//把所有的都为1list.stream().forEach(a->a=1);}}else{list.set(size-i,0);break;}}}//加1public void longitudeCodeAddOne() {add(this.longitudeCode);}//减1public void longitudeCodeMinusOne(){minus(this.longitudeCode);}//加1public void latitudeCodeAddOne() {add(this.latitudeCode);}//减1public void latitudeCodeMinusOne(){minus(this.latitudeCode);}//获取codepublic String getCode(){return "";}}
package 定位电影院;import lombok.Getter;
import lombok.Setter;import java.math.BigDecimal;
@Setter
@Getter
public class Node {//经度private BigDecimal x;//纬度private BigDecimal y;//内容private String name;private Integer id;//距离private BigDecimal distance;public Node(BigDecimal x, BigDecimal y, String name, Integer id) {this.x = x;this.y = y;this.name = name;this.id = id;}
}
package 定位电影院;import java.math.BigDecimal;
import java.util.*;
import java.util.stream.Collectors;/*** 四岔树*/
public class Tree {public static Area areaTree;//每个格子的数量小于几个就不再分private static int count = 5;public static HashMap<String,Area> areaHashMap;//扩展圈数查的最大圈数private static Integer number = 3;public static void createTree(Area areaTree, List<Node> nodeList, Area small, Area big) {if (small == null || big == null) {small = obtainBoundarySmallx(nodeList);big = obtainBoundaryBig(nodeList);}//中线BigDecimal x = getMedianLine(small.getX(), big.getX());BigDecimal y = getMedianLine(small.getY(), big.getY());areaTree.setX(x);areaTree.setY(y);// 象限图  y//        |//    2   |   1//        |//------------------x//        |//    3   |   4//        |//第一象限 >x >yList<Node> firstQuadrant = new ArrayList<>();//第二象限 <x >yList<Node> secondQuadrant = new ArrayList<>();//第三象限 <x <yList<Node> thirdQuadrant = new ArrayList<>();//第四象限 >x <yList<Node> fourthQuadrant = new ArrayList<>();for (Node node : nodeList) {//第一象限 >x >yif (node.getX().compareTo(x) == 1 && node.getY().compareTo(y) == 1) {firstQuadrant.add(node);continue;}//第二象限 <x >yif (node.getX().compareTo(x) == -1 && node.getY().compareTo(y) == 1) {secondQuadrant.add(node);continue;}//第三象限 <x <yif (node.getX().compareTo(x) == -1 && node.getY().compareTo(y) == -1) {thirdQuadrant.add(node);continue;}//第四象限 >x <yif (node.getX().compareTo(x) == 1 && node.getY().compareTo(y) == -1) {fourthQuadrant.add(node);continue;}//如果 相等  按照y划分if (node.getX().compareTo(x) == 0 && node.getY().compareTo(y) == 1) {firstQuadrant.add(node);//secondQuadrant.add(node);}else{thirdQuadrant.add(node);//fourthQuadrant.add(node);}//如果 相等  按照x划分if (node.getX().compareTo(x) == 1 && node.getY().compareTo(y) == 0) {//firstQuadrant.add(node);fourthQuadrant.add(node);}else{//thirdQuadrant.add(node);secondQuadrant.add(node);}}//获取十字线用于分四个格子Area center = new Area(getMedianLine(small.getX(), big.getY()), getMedianLine(small.getY(), big.getY()));//第一象限------------------Area firstNode = new Area();//如果数量大于配置一个格子的数量继续分，如果小于就放进去不再分if (firstQuadrant.size() > count) {//对经纬度划分编码setlongitudeCodeAndlatitudeCode(firstNode, 0, 1);//递归创建createTree(firstNode, firstQuadrant, center, big);} else {firstNode.setNodeList(firstQuadrant);}//建立关联areaTree.setFirstQuadrant(firstNode);//第二象限Area secondNode = new Area();if (secondQuadrant.size() > count) {setlongitudeCodeAndlatitudeCode(secondNode, 0, 0);createTree(secondNode, secondQuadrant,new Area(small.getX(), getMedianLine(small.getY(), big.getY())),new Area(getMedianLine(small.getX(), big.getX()), big.getY()));} else {secondNode.setNodeList(secondQuadrant);}areaTree.setSecondQuadrant(secondNode);//第三象限Area thirdNode = new Area();if (thirdQuadrant.size() > count) {setlongitudeCodeAndlatitudeCode(thirdNode, 1, 0);createTree(thirdNode, thirdQuadrant, small, center);} else {thirdNode.setNodeList(thirdQuadrant);}areaTree.setThirdQuadrant(thirdNode);//第四象限Area fourthNode = new Area();if (fourthQuadrant.size() > count) {setlongitudeCodeAndlatitudeCode(fourthNode, 1, 0);createTree(fourthNode, fourthQuadrant,new Area(getMedianLine(small.getX(), big.getX()), small.getY()),new Area(big.getX(), getMedianLine(small.getY(), big.getY())));} else {fourthNode.setNodeList(fourthQuadrant);}areaTree.setFourthQuadrant(fourthNode);}/*** 获取边界*/private static Area obtainBoundarySmallx(List<Node> nodeList) {BigDecimal smallx = nodeList.stream().map(a -> a.getX()).min(BigDecimal::compareTo).get();BigDecimal smally = nodeList.stream().map(a -> a.getY()).min(BigDecimal::compareTo).get();return new Area(smallx, smally);}/*** 获取边界*/private static Area obtainBoundaryBig(List<Node> nodeList) {BigDecimal bigx = nodeList.stream().map(a -> a.getX()).max(BigDecimal::compareTo).get();BigDecimal bigy = nodeList.stream().map(a -> a.getY()).max(BigDecimal::compareTo).get();return new Area(bigx, bigy);}/*** 放入经纬度编号*/private static void setlongitudeCodeAndlatitudeCode(Area node, int latitudeCode, int longitudeCode) {//经度编码加1位node.longitudeCodeAdd(longitudeCode);//纬度编码加1位node.latitudeCodeAdd(latitudeCode);}/*** 去中间值用于平分** @param small* @param big* @return*/private static BigDecimal getMedianLine(BigDecimal small, BigDecimal big) {return big.subtract(small).divide(new BigDecimal(2));}/*** 获取和当前节点最近的10个节点** @param node* @param i* @return*/public static List<Node> getNear(Node node, int i) {//1找到最近的那个区域Area nearest = getNearest(areaTree, node);//2 对当前区域排序//查出节点List<Node> nearestList = getAreaList(nearest, i);//算距离setDistance(nearestList, node);// 将节点进行插入排序nearestList = insertionSort(nearestList);//获取最近的数据return nearestList.subList(0, i - 1);}/*** 拿到最近的块 找出大于i个点** @param nearest* @param i* @return*/private static List<Node> getAreaList(Area nearest, int i) {Area head = new Area(nearest.getLongitudeCode(),nearest.getLatitudeCode());List<Area> areas = new ArrayList<>();areas.add(nearest);/*String latitudeCode = nearest.getLatitudeCode().toString();String longitudeCode = nearest.getLongitudeCode().toString();*///这里设置最多循环几次for (int j = i; j < number; j++) {int num = areas.stream().map(a -> a.getNodeList().size()).collect(Collectors.summingInt(a -> a));//算出开头点head.latitudeCodeMinusOne();head.longitudeCodeMinusOne();if (num > i) {//执行然后停止areas.addAll(getArea(head,j));break;} else {//执行areas.addAll(getArea(nearest,j));}}List<Node> nodes = new ArrayList<>();areas.stream().forEach(a -> nodes.addAll(a.getNodeList()));return nodes;}/*** 转一圈* @param nearest* @param j* @return*/private static List<Area> getArea(Area nearest,int j) {List<Area> areas = new ArrayList<>();//第一个加上//像右边移动j+1个for (int i = 0; i < j+1; i++) {nearest.latitudeCodeAddOne();Area area = areaHashMap.get(nearest.getCode());if (area != null) {areas.add(area);}}//转像下for (int i = 0; i < j+1; i++) {nearest.longitudeCodeAddOne();Area area = areaHashMap.get(nearest.getCode());if (area != null) {areas.add(area);}}//转左转for (int i = 0; i < j+1; i++) {nearest.latitudeCodeMinusOne();Area area = areaHashMap.get(nearest.getCode());if (area != null) {areas.add(area);}}//转向上for (int i = 0; i < j+1; i++) {nearest.longitudeCodeMinusOne();Area area = areaHashMap.get(nearest.getCode());if (area != null) {areas.add(area);}}return areas;}/*** 算出list中所有点距离node点的距离** @param nodes* @param node*/private static void setDistance(List<Node> nodes, Node node) {nodes.stream().forEach(a -> a.setDistance(getDistance(a, node)));}/*** 计算两点之间 曼哈顿距离** @param a* @param b* @return*/private static BigDecimal getDistance(Node a, Node b) {//a.x-b.x 的绝对值 +  a.y+b.y 的绝对值return a.getX().subtract(b.getX()).abs().add(a.getY().subtract(b.getY()).abs());}/*** @param nearestList 排序的队列*/private static List<Node> insertionSort(List<Node> nearestList) {return nearestList.stream().sorted(Comparator.comparing(Node::getDistance)).collect(Collectors.toList());}/*** 找到离点最近的那个区域** @param nodeTree* @param node* @return*/private static Area getNearest(Area nodeTree, Node node) {//第一象限if (node.getX().compareTo(nodeTree.getX()) == 1 && node.getY().compareTo(nodeTree.getY()) == 1) {if (nodeTree.getFirstQuadrant() != null) {getNearest(nodeTree.getFirstQuadrant(), node);} else {return nodeTree;}}//第二象限if (node.getX().compareTo(nodeTree.getX()) == -1 && node.getY().compareTo(nodeTree.getY()) == 1) {if (nodeTree.getSecondQuadrant() != null) {getNearest(nodeTree.getSecondQuadrant(), node);} else {return nodeTree;}}//第三象限if (node.getX().compareTo(nodeTree.getX()) == -1 && node.getY().compareTo(nodeTree.getY()) == -1) {if (nodeTree.getThirdQuadrant() != null) {getNearest(nodeTree.getThirdQuadrant(), node);} else {return nodeTree;}}//第四象限if (node.getX().compareTo(nodeTree.getX()) == 1 && node.getY().compareTo(nodeTree.getY()) == -1) {if (nodeTree.getFourthQuadrant() != null) {getNearest(nodeTree.getFourthQuadrant(), node);} else {return nodeTree;}}//在象限上if (node.getX().compareTo(nodeTree.getX()) == 0 || node.getY().compareTo(nodeTree.getY()) == 0) {return null;}return null;}}
package 定位电影院;import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;public class maintest {public static void main(String[] args) {//获取数据40.7804854194,92.7684392257List<Node> cinemaList = getData();//构建树Tree.createTree(Tree.areaTree,cinemaList,null,null);//使用树找出离着这个点最近的Node node = new Node(new BigDecimal(1),new BigDecimal(2),"名字",1);List<Node> list = Tree.getNear(node,10);System.out.println(list);}private static List<Node> getData(){List<Node>  nodes =  new ArrayList<>();return nodes;}
}