Why does this article exist?

Due to the business adjustment of the company and the lowering of the threshold of movement, the Product Department requires the introduction of a map to record the movement track of users and upload it to the server. Users can view the movement track on the record page. And when drawing the trajectory requires a drawing animation (see Goo dong). Hear this heart ten thousand grass mud horse ~~~ but the demand came down, or have to do.

Say some nonsense in advance (in case I am tortured by the boring words to slip the end of the article, quit halfway, then bring up here)

As a non-computer professional rookie programmer (former major: big communication) after finishing this requirement, I really realized the importance of algorithm. If you can stick to it, I believe you will feel as bad as I do!! “If you want to change jobs in the future, the best choice is to work for two kinds of companies: companies that analyze data and companies that collect data. In the future, all businesses will be based on data, and the most valuable thing a company will have is the data it collects. You can use that data to grow your business, or even collect it, analyze it, use it to generate services, and sell those services to the people who need them.” “Math is the basis for analyzing data. Pick up your advanced math, linear algebra, mathematical statistics, Introduction to Algorithms, etc.” “In the future, if you don’t know how to learn, then you will really be eliminated. When the era of artificial intelligence really comes, a person who can’t learn will only live in a capsule.” PS: People in their 40s still have strong learning ability, and according to my own observation, they learn new knowledge quickly. In a blink of an eye, a group of 20-year-olds in our company are very young.

Let’s cut to the chase. Everything related to maps used in this article comes from Amap. As for the map display is not the focus of this article, so do not repeat. The distance calculation mentioned in the article can be replaced according to the type of map you quote. The text is map API owned, there will be annotations. The effect is as follows

Motion trajectory rendering

A thinning – Douglas algorithm for registration points

1. Introduction to Douglas

Douglas-peukcer algorithm was put forward by D.Douglas and T. Pueker in 1973, referred to as D-P algorithm, which is currently recognized as the classical algorithm for linear element simplification. Most of the existing line simplification algorithms are improved on the basis of this algorithm. Its advantage is that it has invariance of translation and rotation, and the sampling result is certain after given curve and threshold. This chapter focuses on line simplification to explain the algorithm. The basic idea of the algorithm is: to connect the first and last points of each curve with a line, calculate the distance between all points and the line, and find the maximum distance value dmax, compared with the limit D: if dmax < D, all the intermediate points on the curve are dropped; If Dmax ≥D, the corresponding coordinate point of Dmax is reserved, and the curve is divided into two parts with this point as the boundary, and the method is repeatedly applied to these two parts. The specific process of the algorithm is as follows: (1) A virtual line is connected between the beginning and the end of the curve, and the distance between the remaining points and the line is calculated, as shown in Figure 3 (1). (2) The largest point is selected and compared with the threshold value. If it is larger than the threshold value, the point with the largest distance from the straight line is retained; otherwise, all points between the two endpoints of the straight line are omitted, as shown in Figure 3 (2), and the fourth point is retained. The retained points, (3) based on the known curve is divided into two parts processing, repeated 1, 2 step operation, iterative operation, that is still choose so much compared with threshold, trade-offs in sequence, until there is no point to leave, finally satisfy the given accuracy tolerance curve point coordinates, as shown in figure 3 (3), (4), in turn, keep 6 points, 7 PM, I’m going to get rid of all the other points, the simplification of the completion line.

Diagram of Douglas algorithm

2. Algorithm code implementation

Entity LatLngPoint that stores latitude and longitude coordinates

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; }}Copy the code

Used) (use Helen formula obtained equal triangle area point method to calculate the pX point-to-point straight line distance, determined by pA and pB, AMapUtils. CalculateLineDistance (start latLng, end. LatLng) to calculate the distance between two points, this formula applies to API

/** * Calculate the distance of the straight line from point pX to points pA and pB using the equality method of triangle area (obtained using Helen's formula) * @param start longitude and latitude * @param end longitude and latitude * @param center center between the first two points * 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; }Copy the code

Douglas utility class concrete code

public Douglas(ArrayList<LatLng> mLineInit, Double dmax) {if (mLineInit == null) {throw new IllegalArgumentException(" passed 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; } /** * According to the maximum distance limit, the original trajectory is recursively sampled by DP method, To get the compressed track * x * * @param originalLatLngs Original latitude and longitude point set * @param endLatLngs keep the filtered point array * @param start start subscript * @param end subscript Private ArrayList<LatLngPoint> compressLine(LatLngPoint[] originalLatLngs, ArrayList<LatLngPoint> endLatLngs, int start, int end, double dMax) {if (start < end) {ArrayList<LatLngPoint> endLatLngs, int start, int end, double dMax) 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]); // Divide the original line into two segments by compressLine(originalLatLngs, endLatLngs, start, currentIndex, dMax); compressLine(originalLatLngs, endLatLngs, currentIndex, end, dMax); } } return endLatLngs; }Copy the code


The track shown in the figure above is a pattern of 4,417 points that have been located and thinned out on a map. The threshold passed in to the algorithm is 10,4417 points only 136 points after processing. And there is little difference between the 136 points and the 4,417 points. I don’t know if you were shocked, but I was totally shocked. As an algorithmic nerd, it feels like the whole world has been turned upside down.

2. Track rendering – Custom motion track View

At the beginning, we thought that dynamic trajectory could be drawn directly on the map. According to the API of trajectory drawing provided by Autonavi, the result was directly stuck. At that time a face meng forced to find Autonavi customer service, a mention of autonavi customer service more infuriating. Forget it. After trying many times, I gave up drawing directly on the map. At some moment, I suddenly thought of covering a custom View on the map. I felt for a moment that I was the closest TO 250 IQ in the world. Chrysene map API provides latitude and longitude conversion into mobile phone coordinates, so you can get the map point corresponding screen position, it is natural to customize a View dynamic drawing track, when the custom View animation is over, hide the custom View and then draw track on the map. So that’s the whole idea. Let’s roll up our sleeves and code.

1. Initialize variables, brushes, path,

Paint */ private Paint mStartPaint; /** * private Point mStartPoint; /** * private bitmap mStartBitmap; /** * private Paint mLinePaint; /** * private Paint mLightBallPaint; /** * private bitmap mLightBallBitmap; /** * private rect mStartRect; /** * private int mWidth; /** * private int mHeight; /** * path */ private path mLinePath; Private float[] mCurrentPosition = new float[2]; 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(); } /** * Initialize the brush, 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(); }Copy the code

2. Track View drawing

protected void onDraw(Canvas canvas) { super.onDraw(canvas); DrawPath (mLinePath, mLinePaint); 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); } // Draw the starting point 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); }}Copy the code

3. Set the data

/** * draw the movement track * @param mPositions corresponding point coordinates after the algorithm is extracted * @param startPointResId resource ID of the starting picture * @param lightBall resource ID of the small bright ball * Public void drawSportLine(final List<Point> mPositions, @DrawableRes int startPointResId,@DrawableRes int lightBall, final OnTrailChangeListener listener) { if (mPositions.size() <= 1) { listener.onFinish(); return; } // for 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; } / / dynamic graph display light balls cut figure (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(); GetPosTan (value, mCurrentPosition, NULL); MoveTo (mPositions. Get (0).x, mPositions. Get (0).y); } // the pathMeasure.getSegment () method is used to save the current path. pathMeasure.getSegment(0, value, mLinePath, true); invalidate(); If (value == length && listener!) if (value == length && listener! = null) { listener.onFinish(); }}}); animator.start(); } /** * Public interface OnTrailChangeListener {void onFinish(); }Copy the code

Come on, little bench, make a point!!

This paper focuses on: algorithm, algorithm, algorithm, PathMeasure, Path

In the final analysis, the original intention of writing this article is to let most friends like me realize the importance of algorithm. Before, because I did not graduate from the computer major, I only heard others say how important algorithm is, but I did not pay much attention to it in my heart. But when you actually use it in your programs, you’ll see the beauty of algorithms. Powerful algorithms will allow you to find real beauty in millions of pieces of data (i.e., cut out the noise, and forgive me if I don’t have a clue). As a defected engineering seniors, ever wonder why to learn mathematics, everyday work life learned does not fully use the clamp force theorem, let a person the feeling of BaoGuoWuMen, but after the baptism of the algorithm, reminds me of after many years of mathematics, and let the first time I truly realize the real thief TM useful math. You really should pick up math as soon as possible if you want to continue on the program path. And that’s all I want to say. I hope I can help ape friends who have similar needs. Please point out any mistakes in the article. Bazinga ~~~ ~~~ ~~~ ~~~

It’s not a perk but there is one. Buckle up for a drag race.

Another graduation season, Xiao Ming asked his roommate: “After graduation, will you go home with your girlfriend or stay here?” Roommate say: “of course is stay here!” Small clear ask again: “that you and the problem of your girl friend account solved?” Roommate stared xiaoming, hesitated for a moment, speak hesitatingly of say: “I gave her mouth, but she didn’t want to give my mouth – – | |”

Email: [email protected] Github home: github.com/Walll-E