为什么会有这篇文章？
因公司业务调整降低运动门槛，产品部要求引入地图，记录用户的运动轨迹上传至服务器，用户进入记录页面可查看运动轨迹。而且绘制轨迹的时候要求有一个绘制动画（参照咕咚）。听到这心中万只草泥马 ~~~ 可是需求下来了，还是得硬着头皮做啊。
提早说一些废话吧（万一被我枯燥的文字折磨的滑不到文末，就中途退出，遂提至此处）
作为一个非计算机专业出身的菜鸟程序员（原专业：大通信）做完这个需求之后，真正的意识到算法的重要性。如果你能坚持看完，我相信你会和我一样觉得贼TM diao！！！而且文末会有小福利 (˘˘)
下面是公司20年Java大神告诫我们的话：
“ 如果以后要是跳槽，最好选择去这两种公司：分析数据的公司 和 收集数据的公司 。将来所有的业务都是根据数据来定的，未来一个公司最宝贵的就是所收集的数据。利用这些数据可以扩展自己的业务，甚至你只需要收集数据，分析数据，利用数据衍生出服务，将这些服务卖个那些需要的群体。”
“ 数学是分析数据的基础，赶紧捡起你们的高等数学、线性代数、数理统计、算法导论等书。”
“ 未来如果你不懂得学习，那样你真的只会被淘汰的，人工智能时代真正到来的时候一个不会学习的人只可能生活在“胶囊”里面。”
PS: 40好几的人，依然保持旺盛的学习能力，而且据我自己观察，学习新知识炒鸡快哦，瞬秒我们公司20岁的一帮小正太（羞射~）
废话多了，直接进入正题。
本文用到的一切地图相关的东西都来源高德 VCVCVCVCvVC vvv vvVC地图。至于地图展示不是本文重点，所以不做赘述。文中提及的距离的计算，根据自己引用的地图类型做替换即可。文中是地图API所有，会有标注。效果如如下
运动轨迹效果图
一、定位点的抽稀-道格拉斯算法
1、道格拉斯简介
Douglas一Peukcer算法由D.Douglas和T.Peueker于1973年提出，简称D一P算法，是眼下公认的线状要素化简经典算法。现有的线化简算法中，有相当一部分都是在该算法基础上进行改进产生的。它的长处是具有平移和旋转不变性，给定曲线与阂值后，抽样结果一定。
算法的基本思路是:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax ,用dmax与限差D相比:若dmax < D ,这条曲线上的中间点所有舍去;若dmax ≥D ,保留dmax 相应的坐标点,并以该点为界,把曲线分为两部分,对这两部分反复使用该方法。
算法的具体过程如下:
(1) 在曲线首尾两点间虚连一条直线,求出其余各点到该直线的距离，如图3（1）。
(2) 选其最大者与阈值相比較,若大于阈值,则离该直线距离最大的点保留,否则将直线两端点间各点所有舍去，如图3（2），第4点保留。
(3) 根据所保留的点,将已知曲线分成两部分处理,反复第1、2步操作，迭代操作，即仍选距离最大者与阈值比較,依次取舍,直到无点可舍去，最后得到满足给定精度限差的曲线点坐标，如图3（3）、（4）依次保留第6点、第7点，舍去其它点,即完成线的化简。
道格拉斯算法示意图
2、算法代码实现
存储经纬度坐标的实体LatLngPoint
public class LatLngPoint implements Comparable<LatLngPoint> {
/**
* 用于记录每一个点的序号
*/
public int id;
/**
* 每一个点的经纬度
*/
public LatLng latLng;
public LatLngPoint(int id,LatLng latLng){
this.id = id;
this.latLng = latLng;
}
@Override
public int compareTo(@NonNull LatLngPoint o) {
if (this.id < o.id) {
return -1;
} else if (this.id > o.id)
return 1;
return 0;
}
}
使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离,
AMapUtils.calculateLineDistance(start.latLng, end.latLng)计算两点之间的距离，此公式高德API
/**
* 使用三角形面积（使用海伦公式求得）相等方法计算点pX到点pA和pB所确定的直线的距离
* @param start 起始经纬度
* @param end 结束经纬度
* @param center 前两个点之间的中心点
* @return 中心点到 start和end所在直线的距离
*/
private double distToSegment(LatLngPoint start, LatLngPoint end, LatLngPoint center) {
double a = Math.abs(AMapUtils.calculateLineDistance(start.latLng, end.latLng));
double b = Math.abs(AMapUtils.calculateLineDistance(start.latLng, center.latLng));
double c = Math.abs(AMapUtils.calculateLineDistance(end.latLng, center.latLng));
double p = (a + b + c) / 2.0;
double s = Math.sqrt(Math.abs(p * (p - a) * (p - b) * (p - c)));
double d = s * 2.0 / a;
return d;
}
Douglas工具类具体代码
public Douglas(ArrayList<LatLng> mLineInit, double dmax) {
if (mLineInit == null) {
throw new IllegalArgumentException("传入的经纬度坐标list == null");
}
this.dMax = dmax;
this.start = 0;
this.end = mLineInit.size() - 1;
for (int i = 0; i < mLineInit.size(); i++) {
this.mLineInit.add(new LatLngPoint(i, mLineInit.get(i)));
}
}
/**
* 压缩经纬度点
*
* @return
*/
public ArrayList<LatLng> compress() {
int size = mLineInit.size();
ArrayList<LatLngPoint> latLngPoints = compressLine(mLineInit.toArray(new LatLngPoint[size]), mLineFilter, start, end, dMax);
latLngPoints.add(mLineInit.get(0));
latLngPoints.add(mLineInit.get(size-1));
//对抽稀之后的点进行排序
Collections.sort(latLngPoints, new Comparator<LatLngPoint>() {
@Override
public int compare(LatLngPoint o1, LatLngPoint o2) {
return o1.compareTo(o2);
}
});
ArrayList<LatLng> latLngs = new ArrayList<>();
for (LatLngPoint point : latLngPoints) {
latLngs.add(point.latLng);
}
return latLngs;
}
/**
* 根据最大距离限制，采用DP方法递归的对原始轨迹进行采样，得到压缩后的轨迹
* x
*
* @param originalLatLngs 原始经纬度坐标点数组
* @param endLatLngs 保持过滤后的点坐标数组
* @param start 起始下标
* @param end 结束下标
* @param dMax 预先指定好的最大距离误差
*/
private ArrayList<LatLngPoint> compressLine(LatLngPoint[] originalLatLngs, ArrayList<LatLngPoint> endLatLngs, int start, int end, double dMax) {
if (start < end) {
//递归进行调教筛选
double maxDist = 0;
int currentIndex = 0;
for (int i = start + 1; i < end; i++) {
double currentDist = distToSegment(originalLatLngs[start], originalLatLngs[end], originalLatLngs[i]);
if (currentDist > maxDist) {
maxDist = currentDist;
currentIndex = i;
}
}
//若当前最大距离大于最大距离误差
if (maxDist >= dMax) {
//将当前点加入到过滤数组中
endLatLngs.add(originalLatLngs[currentIndex]);
//将原来的线段以当前点为中心拆成两段，分别进行递归处理
compressLine(originalLatLngs, endLatLngs, start, currentIndex, dMax);
compressLine(originalLatLngs, endLatLngs, currentIndex, end, dMax);
}
}
return endLatLngs;
}
结果：
上图中展示的轨迹是定位得到的4417个点，经过抽稀之后绘制在地图上的样式。算法中传入的阙值是10，4417个点处理之后只136个点。而且这136个点绘制的轨迹和4417个点绘制的轨迹几乎没有什么差别。
不知道你们有没有被震撼到，反正我是彻彻底底被震到了。作为算法小白的我，感觉整个世界都被颠覆了。
二、轨迹绘制-自定义运动轨迹View
最开始得时候认为直接在地图上绘制动态轨迹的，根据高德提供绘制轨迹的API，结果直接卡死。当时一脸懵逼的找高德客服，一提高德的客服更让人窝火。算了不提了。后面自己试了好多遍之后放弃直接在地图上绘制，不知道哪一刻，就突然想到在地图上覆盖一个自定义的View。当时有一瞬间觉得自己是这个世界上智商最接近250的 ┐(‘～`；)┌
地图API提供了经纬度转换成手机上的坐标，所以可以拿到地图上点对应的屏幕的位置，也就自然可以自定义一个View动态的绘制轨迹，当自定义View的动画结束之后，隐藏自定义View然后在地图上绘制轨迹。这就是我的整体思路，下面袖子撸起，上代码。
1、初始化变量、画笔、path、
* 起点Paint
*/
private Paint mStartPaint;
/**
* 起点
*/
private Point mStartPoint;
/**
* 起点bitmap
*/
private Bitmap mStartBitmap;
/**
* 轨迹
*/
private Paint mLinePaint;
/**
* 小亮球
*/
private Paint mLightBallPaint;
/**
* 小两球的bitmap UI切图
*/
private Bitmap mLightBallBitmap;
/**
* 起点rect 如果为空时不绘制小亮球
*/
private Rect mStartRect;
/**
* 屏幕宽度
*/
private int mWidth;
/**
* 屏幕高度
*/
private int mHeight;
/**
* 轨迹path
*/
private Path mLinePath;
/**
* 保存每一次刷新界面轨迹的重点坐标
*/
private float[] mCurrentPosition = new float[2];
public SportTrailView(Context context) {
this(context, null);
}
public SportTrailView(Context context, @Nullable AttributeSet attrs) {
this(context, attrs, 0);
}
public SportTrailView(Context context, @Nullable AttributeSet attrs, int defStyleAttr) {
super(context, attrs, defStyleAttr);
initPaint();
}
/**
* 初始化画笔，path
*/
private void initPaint() {
mLinePaint = new Paint();
mLinePaint.setColor(Color.parseColor("#ff00ff42"));
mLinePaint.setStyle(Paint.Style.STROKE);
mLinePaint.setStrokeWidth(10);
mLinePaint.setStrokeCap(Paint.Cap.ROUND);
mLinePaint.setAntiAlias(true);
mLightBallPaint = new Paint();
mLightBallPaint.setAntiAlias(true);
mLightBallPaint.setFilterBitmap(true);
mStartPaint = new Paint();
mStartPaint.setAntiAlias(true);
mStartPaint.setFilterBitmap(true);
mLinePath = new Path();
}
2、轨迹View绘制
protected void onDraw(Canvas canvas) {
super.onDraw(canvas);
//绘制轨迹
canvas.drawPath(mLinePath, mLinePaint);
//绘制引导亮球
if (mLightBallBitmap !=null && mStartRect !=null){
int width = mLightBallBitmap.getWidth();
int height = mLightBallBitmap.getHeight();
RectF rect = new RectF();
rect.left = mCurrentPosition[0] - width;
rect.right = mCurrentPosition[0] + width;
rect.top = mCurrentPosition[1] - height;
rect.bottom = mCurrentPosition[1] + height;
canvas.drawBitmap(mLightBallBitmap, null, rect, mLightBallPaint);
}
//绘制起点
if (mStartBitmap != null && mStartPoint != null) {
if (mStartRect == null) {
int width = mStartBitmap.getWidth() / 2;
int height = mStartBitmap.getHeight() / 2;
mStartRect = new Rect();
mStartRect.left = mStartPoint.x - width;
mStartRect.right = mStartPoint.x + width;
mStartRect.top = mStartPoint.y - height;
mStartRect.bottom = mStartPoint.y + height;
}
canvas.drawBitmap(mStartBitmap, null, mStartRect, mStartPaint);
}
}
3、设置数据
/**
* 绘制运动轨迹
* @param mPositions 道格拉斯算法抽稀过后对应的点坐标
* @param startPointResId 起点图片的资源id
* @param lightBall 小亮球的资源id
* @param listener 轨迹绘制完成的监听
*/
public void drawSportLine(final List<Point> mPositions, @DrawableRes int startPointResId,@DrawableRes int lightBall, final OnTrailChangeListener listener) {
if (mPositions.size() <= 1) {
listener.onFinish();
return;
}
//用于
Path path = new Path();
for (int i = 0; i < mPositions.size(); i++) {
if (i == 0) {
path.moveTo(mPositions.get(i).x, mPositions.get(i).y);
} else {
path.lineTo(mPositions.get(i).x, mPositions.get(i).y);
}
}
final PathMeasure pathMeasure = new PathMeasure(path, false);
//轨迹的长度
final float length = pathMeasure.getLength();
if (length < ViewUtil.dip2Px(getContext(), 16)) {
listener.onFinish();
return;
}
//动态图中展示的亮色小球（UI切图）
mLightBallBitmap = BitmapFactory.decodeResource(getResources(), lightBall);
//起点
mStartPoint = new Point(mPositions.get(0).x, mPositions.get(0).y);
mStartBitmap = BitmapFactory.decodeResource(getResources(), startPointResId);
ValueAnimator animator = ValueAnimator.ofFloat(0, length);
animator.setDuration(3000);
animator.setInterpolator(new AccelerateDecelerateInterpolator());
animator.addUpdateListener(new ValueAnimator.AnimatorUpdateListener() {
@Override
public void onAnimationUpdate(ValueAnimator animation) {
float value = (Float) animation.getAnimatedValue();
// 获取当前点坐标封装到mCurrentPosition
pathMeasure.getPosTan(value, mCurrentPosition, null);
if (value == 0) {
//如果当前的运动轨迹长度为0，设置path的起点
mLinePath.moveTo(mPositions.get(0).x, mPositions.get(0).y);
}
//pathMeasure.getSegment（）方法用于保存当前path路径，
//下次绘制时从上一次终点位置处绘制，不会从开始的位置开始绘制。
pathMeasure.getSegment(0, value, mLinePath, true);
invalidate();
//如果当前的长度等于pathMeasure测量的长度，则表示绘制完毕，
if (value == length && listener != null) {
listener.onFinish();
}
}
});
animator.start();
}
/**
* 轨迹绘制完成监听
*/
public interface OnTrailChangeListener {
void onFinish();
}
来来来，小板凳，划重点！！！
本文重点：算法、算法、算法、PathMeasure、Path
说到底写这篇文章的初衷还是想让大多数和我一样的朋友能意识到算法的重要性，之前因为不是计算机专业毕业，所以只听别人说算法如何如何重要，但在自己的内心里却并没有多重视。但是当你程序中真正用到的时候，你会发现算法之美。强大的算法会让你在千千万万的数据中找寻真正的美（也就是去除噪声，原谅我毫无征兆的文艺一下）。作为一个叛变的工科生，曾经怀疑过为什么要学数学，平常工作生活中完全用不到当年所学的夹逼定理啊，让人有种报国无门的感觉，可是经过这次算法的洗礼之后，让我想起了阔别多年的数学，而且让我第一次真正的意识到数学真的贼TM有用。如果你还想在程序这条路上继续下去那你真的应该尽快捡起数学。
至此，我想说的也完了。希望能帮到有类似需求的猿友们，文中有错误的地方请指出。-.-
或许有些朋友心想说好的福利呢，其实我是骗你们的 Bazinga ~~~
其实没什么福利但是段子确实有一个。系好安全带，飙车了。
又是一年毕业季，小明问室友：“你毕业后和女朋友回家呢，还是留在这边呢。”
室友说：“当然是留在这边了！ ”
小明又问：“那你和你女朋友户口的问题解决了吗？”
室友瞪了小明一下，犹豫了一会，吞吞吐吐的说：“我给她口，可是她不愿意给我口 -.-||”
联系邮箱：walle0228@163.com
Github主页：https://github.com/Walll-E
网友评论