做项目优化的时候有个过滤逻辑耗时严重，因此写了个算法进行优化。
在此记录一下实现的过程和思路历程。
需求：有一条导航规划路线集合listA和一个poi点集合listB，所有点集合均为地图坐标，需要拿到在listA一定范围内所有poi点的集合，需求规定为3km。
当前业务逻辑是拿点listB与listA集合中每个点位用高德api进行距离计算，但是此方法耗时比较大，1000公里距离耗时达到了15分钟，10公里的耗时也有30秒左右，耗时惊人，所以我就自己写了个算法实现，结果为1000公里耗时2秒左右。
算法实现的初步想法：
点位的比较其实主要是计算listB中点位距离listA的距离是否在指定范围内。
所以我们从listB中取出一个点位C。
第一步：取点C上下左右3公里的经纬度。4个经纬度可以围成一个正方形，然后判断正方形里面是否存在listA集合中的点，如果正方形里面没有，则判断不在范围内，然后用正方形里面的poi点集合listPa进行第二步。
第二步：此时取点C为中心，指定范围的圆圈，判断范围内是否有listPa的点位，有则判断在范围内，没有则进行第三步。
第三步：此时listPa集合数据是正方形与圆形相切之后部分的位置里面，此时需判断listPa集合里面的点与其前后相邻点位的切线是否与圆相交，相交则判断在范围内。此过程中需要判断多个边界值问题，比如点位是否第一个或者最后一个，2个点位可能不在正方形内，但是切线在范围内，因为导航路径如果是一条直线可能只会给2个点，而poi点在直线的中间。
以上为分析内容，当然实际开发过程要复杂一点，相关图形分析后续补上。
以下为代码部分：
import java.util.ArrayList;
import java.util.List;
public class PolylineWorker {
private List<LatLng> mLine;
public PolylineWorker(List<LatLng> line) {
mLine = line;
init();
initLatLngD(filterDistance);
initPointDistance();
}
public void unInit() {
if (mPolyline != null) {
mPolyline.remove();
mPolyline = null;
}
}
/** 数据过滤半径 */
private float filterDistance;
/** 路径中2点间最大间隔距离值 */
private double pointMaxDistance;
/** 根据路径中2点间最大间隔距离计算得到的最大过滤范围值 */
private double filterMaxDistance;
/**
* 计算最近点距离--优化算法
*
* @return 结果为1则说明在范围内，为-1则说明超过距离
*/
public int nearestDistanceByFilter(LatLng latLng, float maxDistance) {
//初始化过滤数据量值
initLatLngD(maxDistance);
initPointDistance();
//过滤符合范围内坐标
List<LatLng> backFilter = filterByLatLng(latLng, latD, lngD);
//判断是否在半径内 1在半径内，-1不在半径内
int type = filterAfter(backFilter, latLng);
if (type == 1) {
return 1;
} else {
//如果不在半径内，则获取最大范围内路径点集合
List<LatLng> backs = filterByLatLng(latLng, latDMax, lngDMax);
//判断路径点集合中是否存在切线在范围内的点
return filterNearestPoint(backs, latLng);
}
}
/**
* 初始化路径中2点间最大间隔距离和经纬度偏移值
*/
private void initPointDistance() {
if (pointMaxDistance == 0) {
double dLat = 0;
double dLng = 0;
for (int i = 0; i < mLine.size(); i++) {
if (i < mLine.size() - 2) {
double tmpLat = Math.abs(mLine.get(i).latitude - mLine.get(i + 1).latitude);
double tmpLng = Math.abs(mLine.get(i).longitude - mLine.get(i + 1).longitude);
if (tmpLat > dLat) {
dLat = tmpLat;
}
if (tmpLng > dLng) {
dLng = tmpLng;
}
}
}
double disLat = filterDistance * dLat / latD;
double disLng = filterDistance * dLng / lngD;
pointMaxDistance = Math.max(disLat, disLng);
filterMaxDistance = Math.sqrt((Math.pow(filterDistance, 2) + Math.pow(pointMaxDistance, 2)));
Logger.e("最大偏移量距离:" + filterMaxDistance);
//初始化最大经纬度偏移值
initDlMax();
}
}
/**
* 初始化指定范围对应的经纬度偏移值
*
* @param maxDistance 指定的范围
*/
private void initLatLngD(float maxDistance) {
if ((latD == 0 && lngD == 0) || filterDistance != maxDistance) {
filterDistance = maxDistance;
initDl();
}
}
/**
* 使用圆圈半径的方式进行二次过滤
*/
private int filterAfter(List<LatLng> backFilter, LatLng latLng) {
for (LatLng one : backFilter) {
double tmpDistance = AMapUtils.calculateLineDistance(latLng, one);
if (tmpDistance < filterDistance) {
return 1;
}
}
Logger.e("filterAfter过滤之后数量：----" + backFilter.size());
return -1;
}
/**
* 如果没有符合要求的点，则需要校验是否为沿线点连线中附近距离以内
*/
private int filterNearestPoint(List<LatLng> tmpLine, LatLng latLng) {
if (tmpLine.size() == 0) {
return -1;
}
//根据指定范围点集合，判断是否存在满足条件的最近距离点距离
for (LatLng one : tmpLine) {
double dis = getNearestDistance(one, latLng);
if (dis < filterDistance) {
return 1;
}
}
return -1;
}
/**
* 根据给定点，判断点的前后连线距离过滤点的直线距离
*
* @param one 给定点
* @param latLng 过滤点
* @return 距离
*/
private double getNearestDistance(LatLng one, LatLng latLng) {
int sindex = mLine.indexOf(one);
if (sindex == 0) {
//起始点判断
LatLng right = mLine.get(sindex + 1);
return getDistanceByThreePoint(latLng, one, right);
} else if (sindex == mLine.size() - 1) {
//终点判断
LatLng left = mLine.get(sindex - 1);
return getDistanceByThreePoint(latLng, one, left);
} else {
//中间点判断
LatLng right = mLine.get(sindex + 1);
double rD = getDistanceByThreePoint(latLng, one, right);
LatLng left = mLine.get(sindex - 1);
double lD = getDistanceByThreePoint(latLng, one, left);
return Math.min(rD, lD);
}
}
/**
* 获取点距离另外2个点连线的距离
*
* @param latLng 被过滤点
* @param one 路径上的点
* @param other 路径左右的点
* @return 返回距离
*/
private double getDistanceByThreePoint(LatLng latLng, LatLng one, LatLng other) {
double c = AMapUtils.calculateLineDistance(latLng, one);
//防止经纬度因精度问题导致部分数据未检测到
if (c < filterDistance) {
return c;
}
double a = AMapUtils.calculateLineDistance(one, other);
double b = AMapUtils.calculateLineDistance(latLng, other);
double angleB = Math.acos(((Math.pow(a, 2) + Math.pow(c, 2) - Math.pow(b, 2)) / (2 * a * c))) * 180 / Math.PI;
double angleC = Math.acos(((Math.pow(a, 2) + Math.pow(b, 2) - Math.pow(c, 2)) / (2 * a * b))) * 180 / Math.PI;
if (angleB > 90 || angleC > 90) {
//角度不符合要求，过滤掉
return filterDistance + 1;
} else {
//角度符合要求，计算切线距离
double P = (a + b + c) / 2;
double S = Math.sqrt((P * (P - a) * (P - b) * (P - c)));
return 2 * S / a;
}
}
/** 指定范围对应的经纬度偏差值 */
private double latD = 0;
/** 指定范围对应的经纬度偏差值 */
private double lngD = 0;
/** 最大偏差范围对应的经纬度偏差值 */
private double latDMax = 0;
/** 最大偏差范围对应的经纬度偏差值 */
private double lngDMax = 0;
/**
* 根据坐标经纬度进行第一次过滤
*/
private List<LatLng> filterByLatLng(LatLng poiItem, double latD, double lngD) {
List<LatLng> filterLine = new ArrayList<>();
for (LatLng one : mLine) {
if (Math.abs(one.latitude - poiItem.latitude) <= latD &&
Math.abs(one.longitude - poiItem.longitude) <= lngD) {
filterLine.add(one);
}
}
Logger.e("filterBefor过滤之后数量：----" + filterLine.size());
return filterLine;
}
/**
* 根据需要过滤的距离，计算出偏移指定距离所需要偏移的经纬度量
*/
private void initDl() {
double lngdis = AMapUtils.calculateLineDistance(new LatLng(0, 1), new LatLng(0, 0));
double latdis = AMapUtils.calculateLineDistance(new LatLng(1, 0), new LatLng(0, 0));
lngD = (filterDistance / lngdis) * 1;
latD = (filterDistance / latdis) * 1;
Logger.e("每3km经纬度偏移量结果：lat/lng--->" + latD + "/" + lngD);
}
/**
* 根据最大偏移的距离，计算出偏移指定距离所需要偏移的经纬度量
*/
private void initDlMax() {
double lngdis = AMapUtils.calculateLineDistance(new LatLng(0, 1), new LatLng(0, 0));
double latdis = AMapUtils.calculateLineDistance(new LatLng(1, 0), new LatLng(0, 0));
//一倍范围有遗漏概率，目前使用2倍最大偏移量
lngDMax = ((filterMaxDistance + pointMaxDistance) / lngdis) * 1;
latDMax = ((filterMaxDistance + pointMaxDistance) / latdis) * 1;
Logger.e("最大偏移量结果：lat/lng--->" + latDMax + "/" + lngDMax);
}
}
