利用道格拉斯-普克算法优化压缩经纬度图形点位数(进阶版)
本帖最后由 三木猿 于 2021-7-2 16:55 编辑代码已更新成进阶版，原版代码太过简陋，让我们的算法工程师看的很不顺眼，所以又更新了一版，这次的10000个点能简化成200多个点，并且不丢失轮廓
分得清吗，前一个图的有1103个点，后一个图有185个点。
道格拉斯-普克算法：懒得解释，请参考：https://zhuanlan.zhihu.com/p/355323735
管你看不看得懂，拿过去用就完了！
优化前：
优化后：
代码：import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import lombok.ToString;
import net.sf.geographiclib.Geodesic;
import org.apache.commons.lang3.StringUtils;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
/**
* @ClassName: DPUtil
* @Package: tos-product
* @Description: 点位数优化
* @Author: sen.yang@youhualin.com
* @Date: 2021/6/25 9:25
* @Copyright: 悠桦林信息科技（上海）有限公司
*/
public class DpUtil {
/**
* 默认的点到轨迹线最大距离误差阈值（单位：米）
*/
private static final double DEFAULTD_MAX = 30.0;
/**
* @param dis 经纬度字符串
* @param range 控制数据经度压缩的极差
*/
public static String smooth(String dis, double range) {
String[] points = dis.split(";");
List<String> strings = Arrays.asList(points);
//拆分list，这里的意思是每10条算一条曲线，利用道格拉斯-普克算法对这条曲线进行优化
List<List<String>> lists = CollectionUtils.splitList(strings, strings.size() / 2);
List<TyPoint> tyPointList = new ArrayList<>();
int id = 0;
for (List<String> stringList : lists) {
List<TyPoint> list = new ArrayList<>();
for (int i = 0; i < stringList.size(); i++) {
if (StringUtils.isNotBlank(stringList.get(i))) {
TyPoint data = new TyPoint();
data.setId(id);
String[] split = stringList.get(i).split(",");
data.setX(Double.parseDouble(split));
data.setY(Double.parseDouble(split));
list.add(data);
id++;
}
}
List<TyPoint> list1 = dpAlgorithm(list, range);
tyPointList.addAll(list1);
}
StringBuilder res = new StringBuilder();
Map<Integer, TyPoint> collect = tyPointList.stream().distinct().collect(Collectors.toMap(TyPoint::getId, Function.identity(), (k1, k2) -> k2));
for (int i = 0; i < strings.size(); i++) {
TyPoint tyPoint = collect.get(i);
if (tyPoint != null) {
res.append(tyPoint.getX()).append(",").append(tyPoint.getY()).append(";");
}
}
res.deleteCharAt(res.lastIndexOf(";"));
return res.toString();
}
/**
* DP算法入口
* 传入压缩前的轨迹点集合
* 输出压缩后的结果轨迹点集合
*
* @param originPoints 压缩前的轨迹点集合
* @param dMax 点到轨迹线最大距离误差阈值
* @return 优化结果
*/
public static List<TyPoint> dpAlgorithm(List<TyPoint> originPoints, Double dMax) {
List<TyPoint> resultPoints = new ArrayList<>();
resultPoints.add(originPoints.get(0));//获取第一个原始经纬度点坐标并添加到过滤后的数组中
resultPoints.add(originPoints.get(originPoints.size() - 1));//获取最后一个原始经纬度点坐标并添加到过滤后的数组中
//最大距离误差阈值
if (dMax == null) {
dMax = DEFAULTD_MAX;
}
int start = 0;
int end = originPoints.size() - 1;
compression(originPoints, resultPoints, start, end, dMax);
return resultPoints;
}
/**
* 函数功能：根据最大距离限制，采用DP方法递归的对原始轨迹进行采样，得到压缩后的轨迹
*
* @param originPoints：原始经纬度坐标点数组
* @param resultPoints：保持过滤后的点坐标数组
* @param start：起始下标
* @param end：终点下标
* @param dMax：预先指定好的最大距离误差 计算
*/
public static void compression(List<TyPoint> originPoints, List<TyPoint> resultPoints,
int start, int end, double dMax) {
if (start < end) {//递归进行的条件
double maxDist = 0;//最大距离
int curPt = 0;//当前下标
for (int i = start + 1; i < end; i++) {
//当前点到对应线段的距离
double curDist = distToSegment(originPoints.get(start), originPoints.get(end), originPoints.get(i));
if (curDist > maxDist) {
maxDist = curDist;
curPt = i;
}//求出最大距离及最大距离对应点的下标
}
//若当前最大距离大于最大距离误差
if (maxDist >= dMax) {
resultPoints.add(originPoints.get(curPt));//将当前点加入到过滤数组中
//将原来的线段以当前点为中心拆成两段，分别进行递归处理
compression(originPoints, resultPoints, start, curPt, dMax);
compression(originPoints, resultPoints, curPt, end, dMax);
}
}
}
/**
* 函数功能：使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离
*
* @param pA：起始点
* @param pB：结束点
* @param pX：第三个点
* @return distance：点pX到pA和pB所在直线的距离
*/
public static double distToSegment(TyPoint pA, TyPoint pB, TyPoint pX) {
double a = Math.abs(Geodesic.WGS84.Inverse(pA.y, pA.x, pB.y, pB.x).s12);
double b = Math.abs(Geodesic.WGS84.Inverse(pA.y, pA.x, pX.y, pX.x).s12);
double c = Math.abs(Geodesic.WGS84.Inverse(pB.y, pB.x, pX.y, pX.x).s12);
double p = (a + b + c) / 2.0;
double s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
return s * 2.0 / a;
}
/**
* 返回一个点是否在一个多边形边界上
*
* @param polygon 多边形坐标点列表
* @param point1 待判断点
* @return true 点在多边形边上,false 点不在多边形边上。
*/
public static boolean isPointInPolygonBoundary(String point1, String polygon) {
String[] split = point1.split(",");
TyPoint point = new TyPoint(0, Double.parseDouble(split), Double.parseDouble(split));
List<TyPoint> mPoints = new ArrayList<>();
String[] split1 = polygon.split(";");
for (int i = 0; i < split1.length; i++) {
String[] split2 = split1.split(",");
mPoints.add(new TyPoint(i, Double.parseDouble(split2), Double.parseDouble(split2)));
}
for (int i = 0; i < mPoints.size(); i++) {
TyPoint p1 = mPoints.get(i);
TyPoint p2 = mPoints.get((i + 1) % mPoints.size());
// 取多边形任意一个边,做点point的水平延长线,求解与当前边的交点个数
// point 在p1p2 底部 --> 无交点
if (point.y < Math.min(p1.y, p2.y))
continue;
// point 在p1p2 顶部 --> 无交点
if (point.y > Math.max(p1.y, p2.y))
continue;
// p1p2是水平线段,要么没有交点,要么有无限个交点
if (p1.y == p2.y) {
double minX = Math.min(p1.x, p2.x);
double maxX = Math.max(p1.x, p2.x);
// point在水平线段p1p2上,直接return true
if ((point.y == p1.y) && (point.x >= minX && point.x <= maxX)) {
return true;
}
} else { // 求解交点
double x = (point.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
if (x == point.x) // 当x=point.x时,说明point在p1p2线段上
return true;
}
}
return false;
}
}
@Data
@NoArgsConstructor
@AllArgsConstructor
@ToString
class TyPoint {
public int id;//点ID
public double x;//经度
public double y;//纬度
} niusan521 发表于 2021-7-2 12:56
上来直接撸代码看的人一脸懵逼，优化的突出点和算法精髓讲解下。。
但是大概原理你可以搜一下道格拉斯普客算法，原理比较简单 niusan521 发表于 2021-7-2 12:56
上来直接撸代码看的人一脸懵逼，优化的突出点和算法精髓讲解下。。
都说了不是算法工程师，咋解说，我自己都看不懂{:301_1001:} 大部分内容靠百度，具体哪个帖子忘了，谁找到了可以发出来，我置顶 本人非算法工程师，java开发一枚，别找我写啥算法，头给你卸了 高端，牛逼大了，收藏学习 边缘变平滑了。
大佬请教下，这么整的作用是什么 sam喵喵 发表于 2021-6-24 18:06
边缘变平滑了。
大佬请教下，这么整的作用是什么
点位过多，前端处理时就会卡死，需要在后端压缩下点位数量 三木猿 发表于 2021-6-24 18:53
点位过多，前端处理时就会卡死，需要在后端压缩下点位数量
这算法好野蛮，丢失细节颇多 看的好蒙啊{:301_985:} 是粉紅色區域的邊啊。 上来直接撸代码看的人一脸懵逼，优化的突出点和算法精髓讲解下。。
页:
[1]
2