道格拉斯-普克算法(经纬度或坐标点抽稀)

道格拉斯-普克算法（经纬度或坐标点抽稀）

起因

最近在做⼀个车联⽹项⽬，有⼀个场景是车辆定时上报当前所在经纬度等位置信息上报给平台，平台通过web页⾯在⾼德地图上展⽰车辆⾏驶路径。

由于车辆上报规则是每隔4s上报⼀次，⼀个⼩时也就是900个点，⼀天也就是21600个点，如果是10辆车就是216000个点，那如果是100辆车，甚⾄是10000辆车对于数据库存储来说会是⼀个灾难，对于渲染地图，过多的点，也减少页⾯的流畅度。

考虑到车辆直线⾏驶的时候，只需要记录第⼀个点和最后⼀个点即可，期间的点位都是没有必要的，如果拐弯的话，只需要记录⼀两个拐弯的点即可，这样就可以减少点数，进⽽减少存储或者绘图压⼒。

有没有⼀种合适的算法解决此问题呢，遂查阅资料，了解到⼀个算法----道格拉斯-普克算法

介绍

道格拉斯-普克算法 (Douglas–Peucker algorithm，亦称为拉默-道格拉斯-普克算法、迭代适应点算法、分裂与合并算法)是将曲线近似表⽰为⼀系列点，并减少点的数量的⼀种算法。它的优点是具有平移和旋转不变性，给定曲线与阈值后，抽样结果⼀定。—摘⾃百度百科

如果有8个点，如上图（1），抽稀步骤如下：

1. 在曲线⾸尾两点间虚连⼀条直线，求出其余各点到该直线的距离，如右图（1）。

线性规划法2. 选到点到直线距离的最⼤者与阈值相⽐较，若⼤于阈值，则记录该点，否则将直线两端点间各点全部舍去，如右图（2），记录第4个点，

然后根据地4个点，将点分成两段1-4，4-8

3. 然后分别对1-4，4-8重复第1、2步操作，迭代操作，即仍选距离最⼤者与阈值⽐较，依次取舍，直到⽆点可舍去，最后得到满⾜给定精

度限差的曲线点坐标，如图（3）、（4）依次保留第6点、第7点，舍去其他点，即完成线的化简。

结合步骤，这⾥有两点数学知识，⼀是两点确定⼀条直线⽅程，⼆是求点到直线的距离。

点到直线的距离公式如下

PHP代码

/**

* 点到直线的距离

* @param $a float

* @param $b float

* @param $c float

* @param $xy string 点坐标例如 "2,2"

* @return number

public function getDistanceFromPointToLine($a,$b,$c,$xy)

{

$x=explode(",",$xy)[0];

$y=explode(",",$xy)[1];

乐视云视频

return abs(($a*$x+$b*$y+$c)/sqrt($a*$a+$b*$b));

}

/**

* 根据两个点求直线⽅程 ax+by+c=0

* @param $xy1 string 点1，例如"1,1"

* @param $xy2 string 点2，例如"2,2"

* @return array

public function getLineByPoint($xy1,$xy2)

{

$x1=explode(",",$xy1)[0];//第⼀个点的横坐标

$y1=explode(",",$xy1)[1];//第⼀个点的纵坐标

$x2=explode(",",$xy2)[0];//第⼆个点的横坐标

$y2=explode(",",$xy2)[1];//第⼆个点的横坐标

$a=$y2-$y1;

$b=$x1-$x2;

$c=($y1-$y2)*$x1-$y1*($x1-$x2);

return[$a,$b,$c];

笛卡尔坐标系

}

/**

* 稀疏点

* @param $points array 参数为["1,2","2,3"]点集

* @param $max float 阈值，越⼤稀疏效果越好但是细节越差

* @return array

public function sparePoints($points,$max)

{

if(count($points)<3){

return$points;

}

$xy1=$points[0];//取第⼀个点

$xy2=end($points);//取最后⼀个点

list($a,$b,$c)=$this->getLineByPoint($xy1,$xy2);//获取直线⽅程的a,b,c值$ret=[];//最后稀疏以后的点集

$dmax=0;//记录点到直线的最⼤距离

$split=0;//分割位置

for($i=1;$i<count($points)-1;$i++){

$d=$this->getDistanceFromPointToLine($a,$b,$c,$points[$i]);

if($d>$dmax){

$split=$i;

$dmax=$d;

}

if($tmp){//如果存在点到⾸位点连成直线的距离⼤于max的，即需要再次划分

$child1=$this->sparePoints(array_slice($points,0,$split+1),$max);//按split分成左边⼀份，递归

$child2=$this->sparePoints(array_slice($points,$split),$max);//按split分成右边⼀份，递归

//因为child1的最后⼀个点和child2的第⼀个点，肯定是同⼀个（即为分割点），合并的时候，需要注意⼀下

$ret=array_merge($ret,$child1,array_slice($child2,1));

return$ret;

}else{//如果不存在点到直线的距离⼤于阈值的，那么就直接是⾸尾点了

return[$points[0],end($points)];

}

效果

随机了⼀段路，根据⾼德地图的驾驶导航提⽰，选取了80个经纬度（因为这些点都是⾼德算出来的重要点位，经过了⼀定的稀疏），如下：

$points=[

"117.212448,39.133785",

"117.212669,39.133667",

"117.213165,39.133297",

"117.213203,39.13327",

"117.213554,39.133099",

"117.213669,39.13295",

"117.213921,39.132462",

"117.214088,39.132126",

"117.214142,39.131962",

"117.214188,39.13176",

"117.214233,39.131397",

"117.21418,39.13055",

"117.214279,39.130459",

"117.214539,39.130375",

"117.214874,39.130188",

slic"117.216881,39.128716",

"117.217598,39.127995",

"117.217972,39.12759",

"117.218338,39.127178",

"117.218407,39.127071",

"117.218567,39.126911",

"117.219704,39.125702",

"117.219795,39.12561",

"117.220284,39.125114",

"117.220619,39.124802",

"117.221046,39.124348",

"117.221138,39.124245",

"117.221268,39.124092",

"117.222321,39.122955",

"117.222824,39.122406",

"117.222916,39.122311",

"117.223663,39.121544",

"117.2239,39.121452",

"117.224113,39.12159",

"117.224251,39.121677",

"117.225136,39.122208",

"117.225281,39.122292",

"117.225319,39.122311",

"117.226273,39.122875",

"117.226685,39.123127",

"117.227371,39.12352",

"117.227806,39.123779",

"117.228477,39.124134",

"117.228531,39.124161",

"117.228668,39.124187",

"117.228897,39.124325",

"117.229767,39.12479",

"117.230927,39.12545",

"117.231186,39.12561",

"117.231659,39.125908",

"117.231834,39.126026",

"117.232018,39.126186",

"117.232185,39.126362",

"117.232353,39.126583",

"117.232658,39.126972",

"117.233124,39.12748",

"117.233253,39.127609",

"117.233368,39.127689",

"117.233513,39.127762",

"117.233665,39.127823",

"117.233734,39.127846",

"117.233833,39.127865",

"117.233994,39.127888",

"117.234138,39.127892",

"117.234329,39.127884",

"117.234612,39.127838",

"117.234955,39.127754",

龙羊峡电站"117.235252,39.12767",

"117.236282,39.12738",

"117.237137,39.127129",

"117.237671,39.126961",

"117.237953,39.126949",

"117.238213,39.126865",

"117.238472,39.126793",

"117.2397,39.126434",

"117.242233,39.125698",

"117.243538,39.12532",

"117.243645,39.125298",

];

$data=sparePoints($points,"0.00001")；运⾏结果

[