“其實(shí)卷要，人間路是一條向死而生的路，每個(gè)人的生命都是走向死亡的一個(gè)過程独榴。在這條路上我們無法回頭僧叉，也終會(huì)走到終點(diǎn)。沒有永遠(yuǎn)棺榔，只有永別瓶堕。這一路上你的所作所為，你所經(jīng)歷的事務(wù)症歇，見過的風(fēng)景同伴郎笆，便是你這一行的意義所在谭梗。我們都是彼此路上的意義⊥痱荆”
背景
在對(duì)行車軌跡在地圖上進(jìn)行展示時(shí)激捏，往往需要繪制大量的坐標(biāo)點(diǎn)，但是設(shè)備取點(diǎn)的間隔往往是固定的凄吏，傳統(tǒng)的做法是將所有的點(diǎn)繪制出來缩幸，極大地消耗了瀏覽器的性能。然而在一條軌跡上竞思，兩點(diǎn)便可以確定一條直線，因此在行駛路徑比較直的區(qū)域钞护，很多坐標(biāo)點(diǎn)都是可以舍棄的盖喷，同時(shí)，當(dāng)對(duì)地圖進(jìn)行縮小难咕，使可視區(qū)域變大時(shí)课梳，坐標(biāo)點(diǎn)也不必繪制地十分精確，往往取一些關(guān)鍵點(diǎn)就能繪制出行駛軌跡余佃。Douglas-Peuker正是一個(gè)對(duì)坐標(biāo)關(guān)鍵點(diǎn)進(jìn)行抽取的算法暮刃。
算法原理
1. 將軌跡的首尾點(diǎn)連成一條線，計(jì)算曲線上每一個(gè)點(diǎn)到直線的距離爆土，找出最大距離dmax椭懊，看距離是否小于給定的閾值max（及軌跡精確度）。
2. a.若dmax < max步势，則舍棄這條曲線上的所有中間點(diǎn)氧猬，將曲線首尾點(diǎn)連成的直線作為這段曲線的近似，這條線段便處理完畢坏瘩。
b.若dmax >= max盅抚，則以dmax所在點(diǎn)作為分割點(diǎn)，將原來的曲線分為兩段倔矾，分出來的兩條曲線繼續(xù)直線步驟1妄均、2，直到所有的dmax < max哪自。
顯然丰包，算法的抽稀精讀是和閾值相關(guān)的，閾值越大提陶，舍棄的點(diǎn)越多烫沙，提取的關(guān)鍵點(diǎn)越少。若繪制的軌跡較長(zhǎng)隙笆，可在對(duì)地圖進(jìn)行縮放時(shí)動(dòng)態(tài)調(diào)整閾值锌蓄。
代碼實(shí)現(xiàn)
/**
* gps軌跡抽稀算法
* @author: Z1hgq
*/
/**
* 點(diǎn)到直線的距離升筏，直線方程為 ax + by + c = 0
* @param {Number} a 直線參數(shù)a
* @param {Number} b 直線參數(shù)b
* @param {Number} c 直線參數(shù)c
* @param {Object} xy 點(diǎn)坐標(biāo)例如{ lat: 2, lng: 2 }
* @return {Number}
*/
function getDistanceFromPointToLine(a, b, c, xy) {
const x = xy.lng;
const y = xy.lat;
return Math.abs((a * x + b * y + c) / Math.sqrt(a * a + b * b));
}
/**
* 根據(jù)兩個(gè)點(diǎn)求直線方程 ax+by+c=0
* @param {Object} xy1 點(diǎn)1,例如{ lat: 1, lng: 1 }
* @param {Object} xy2 點(diǎn)2,例如{ lat: 2, lng: 2 }
* @return {Array} [a,b,c] 直線方程的三個(gè)參數(shù)
*/
function getLineByPoint(xy1, xy2) {
const x1 = xy1.lng; // 第一個(gè)點(diǎn)的經(jīng)度
const y1 = xy1.lat; // 第一個(gè)點(diǎn)的緯度
const x2 = xy2.lng; // 第二個(gè)點(diǎn)的經(jīng)度
const y2 = xy2.lat; // 第二個(gè)點(diǎn)的緯度
const a = y2 - y1;
const b = x1 - x2;
const c = (y1 - y2) * x1 - y1 * (x1 - x2);
return [a, b, c];
}
/**
* 稀疏點(diǎn)
* @param {Array} points 參數(shù)為[{lat: 1, lng: 2},{lat: 3, lng: 4}]點(diǎn)集
* @param {Number} max 閾值,越大稀疏效果越好但是細(xì)節(jié)越差
* @return {Array} 稀疏后的點(diǎn)集[{lat: 1, lng: 2},{lat: 3, lng: 4}]，保持和輸入點(diǎn)集的順序一致
*/
function sparsePoints(points, max) {
if (points.length < 3) {
return points;
}
const xy1 = points[0]; // 取第一個(gè)點(diǎn)
const xy2 = points[points.length - 1]; // 取最后一個(gè)點(diǎn)
const [a, b, c] = getLineByPoint(xy1, xy2); // 獲取直線方程的a,b,c值
let ret = []; // 最后稀疏以后的點(diǎn)集
let dmax = 0; // 記錄點(diǎn)到直線的最大距離
let split = 0; // 分割位置
for (let i = 1; i < points.length - 1; i++) {
const d = getDistanceFromPointToLine(a, b, c, points[i]);
if (d > dmax) {
split = i;
dmax = d;
}
}
if (dmax > max) {
// 如果存在點(diǎn)到首位點(diǎn)連成直線的距離大于max的,即需要再次劃分
// 按split分成左邊一份瘸爽，遞歸
const child1 = sparsePoints(points.slice(0, split + 1), max);
// 按split分成右邊一份您访，遞歸
const child2 = sparsePoints(points.slice(split), max);
// 因?yàn)閏hild1的最后一個(gè)點(diǎn)和child2的第一個(gè)點(diǎn),肯定是同一個(gè)（即為分割點(diǎn)）,合并的時(shí)候,需要注意一下
ret = ret.concat(child1, child2.slice(1));
return ret;
} else {
// 如果不存在點(diǎn)到直線的距離大于閾值的,那么就直接是首尾點(diǎn)了
return [points[0], points[points.length - 1]];
}
}
export default sparsePoints;
效果展示
數(shù)據(jù)點(diǎn)類型為類似30.664147,104.067232，抽稀閾值為0.000005剪决，第一張圖為原始gps數(shù)據(jù)灵汪，共265個(gè)點(diǎn)，第二張圖為抽稀之后的數(shù)據(jù)柑潦，共108個(gè)點(diǎn)享言。
