道格拉斯-普克算法

维基百科,自由的百科全书
跳转至: 导航搜索

道格拉斯-普克算法(Douglas–Peucker algorithm,亦称为拉默-道格拉斯-普克算法迭代适应点算法分裂与合并算法)是将曲线近似表示为一系列点,并减少点的数量的一种算法。该算法的原始类型分别由乌尔斯·拉默(Urs Ramer)于1972年以及大卫·道格拉斯(David Douglas)和托马斯·普克(Thomas Peucker)于1973年提出[1],并在之后的数十年中由其他学者予以完善[2]

算法[编辑]

使用道格拉斯-普克算法以平滑一条已线性分段的曲线。

伪代码[编辑]

function DouglasPeucker(PointList[], epsilon)
 //Find the point with the maximum distance
 dmax = 0
 index = 0
 for i = 2 to (length(PointList) - 1)
  d = PerpendicularDistance(PointList[i], Line(PointList[1], PointList[end])) 
  if d > dmax
   index = i
   dmax = d
  end
 end
 
 //If max distance is greater than epsilon, recursively simplify
 if dmax >= epsilon
  //Recursive call
  recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
  recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
  
  // Build the result list
  ResultList[] = {recResults1[1...end-1] recResults2[1...end]}
 else
  ResultList[] = {PointList[1], PointList[end]}
 end
 
 //Return the result
 return ResultList[]
end

参考文献[编辑]

  • Urs Ramer, "An iterative procedure for the polygonal approximation of plane curves", Computer Graphics and Image Processing, 1(3), 244–256 (1972) (DOI: 10.1016/S0146-664X(72)80017-0)
  • David Douglas & Thomas Peucker, "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature", The Canadian Cartographer 10(2), 112–122 (1973) (DOI: 10.3138/FM57-6770-U75U-7727)
  • John Hershberger & Jack Snoeyink, "Speeding Up the Douglas–Peucker Line-Simplification Algorithm", Proc 5th Symp on Data Handling, 134–143 (1992). UBC Tech Report TR-92-07 available at http://www.cs.ubc.ca/cgi-bin/tr/1992/TR-92-07

注释[编辑]

外部链接[编辑]