道格拉斯——普克法(Douglas—Peucker)
基本思路是:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax,用dmax与限差D相比:
若dmax<D,这条曲线上的中间点全部舍去;
若dmax≥D,保留dmax对应的坐标点,并以该点为界,把曲线分为两部分,对这两部分重复使用该方法。
/// <summary>
/// Uses the Douglas Peucker algorithm to reduce the number of points.
/// </summary>
/// <param name="Points">The points.</param>
/// <param name="Tolerance">The tolerance.</param>
/// <returns></returns>
public static List<Point> DouglasPeuckerReduction
(List<Point> Points, Double Tolerance)
{
if (Points == null || Points.Count < 3)
return Points;
Int32 firstPoint = 0;
Int32 lastPoint = Points.Count - 1;
List<Int32> pointIndexsToKeep = new List<Int32>();
//Add the first and last index to the keepers
pointIndexsToKeep.Add(firstPoint);
pointIndexsToKeep.Add(lastPoint);
//The first and the last point cannot be the same
while (Points[firstPoint].Equals(Points[lastPoint]))
{
lastPoint--;
}
DouglasPeuckerReduction(Points, firstPoint, lastPoint,
Tolerance, ref pointIndexsToKeep);
List<Point> returnPoints = new List<Point>();
pointIndexsToKeep.Sort();
foreach (Int32 index in pointIndexsToKeep)
{
returnPoints.Add(Points[index]);
}
return returnPoints;
}
/// <summary>
/// Douglases the peucker reduction.
/// </summary>
/// <param name="points">The points.</param>
/// <param name="firstPoint">The first point.</param>
/// <param name="lastPoint">The last point.</param>
/// <param name="tolerance">The tolerance.</param>
/// <param name="pointIndexsToKeep">The point index to keep.</param>
private static void DouglasPeuckerReduction(List<Point>
points, Int32 firstPoint, Int32 lastPoint, Double tolerance,
ref List<Int32> pointIndexsToKeep)
{
Double maxDistance = 0;
Int32 indexFarthest = 0;
for (Int32 index = firstPoint; index < lastPoint; index++)
{
Double distance = PerpendicularDistance
(points[firstPoint], points[lastPoint], points[index]);
if (distance > maxDistance)
{
maxDistance = distance;
indexFarthest = index;
}
}
if (maxDistance > tolerance && indexFarthest != 0)
{
//Add the largest point that exceeds the tolerance
pointIndexsToKeep.Add(indexFarthest);
DouglasPeuckerReduction(points, firstPoint,
indexFarthest, tolerance, ref pointIndexsToKeep);
DouglasPeuckerReduction(points, indexFarthest,
lastPoint, tolerance, ref pointIndexsToKeep);
}
}
/// <summary>
/// The distance of a point from a line made from point1 and point2.
/// </summary>
/// <param name="pt1">The PT1.</param>
/// <param name="pt2">The PT2.</param>
/// <param name="p">The p.</param>
/// <returns></returns>
public static Double PerpendicularDistance
(Point Point1, Point Point2, Point Point)
{
//Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)| *Area of triangle
//Base = v((x1-x2)²+(x1-x2)²) *Base of Triangle*
//Area = .5*Base*H *Solve for height
//Height = Area/.5/Base
Double area = Math.Abs(.5 * (Point1.X * Point2.Y + Point2.X *
Point.Y + Point.X * Point1.Y - Point2.X * Point1.Y - Point.X *
Point2.Y - Point1.X * Point.Y));
Double bottom = Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) +
Math.Pow(Point1.Y - Point2.Y, 2));
Double height = area / bottom * 2;
return height;
//Another option
//Double A = Point.X - Point1.X;
//Double B = Point.Y - Point1.Y;
//Double C = Point2.X - Point1.X;
//Double D = Point2.Y - Point1.Y;
//Double dot = A * C + B * D;
//Double len_sq = C * C + D * D;
//Double param = dot / len_sq;
//Double xx, yy;
//if (param < 0)
//{
// xx = Point1.X;
// yy = Point1.Y;
//}
//else if (param > 1)
//{
// xx = Point2.X;
// yy = Point2.Y;
//}
//else
//{
// xx = Point1.X + param * C;
// yy = Point1.Y + param * D;
//}
//Double d = DistanceBetweenOn2DPlane(Point, new Point(xx, yy));
}
分享到:
相关推荐
点集压缩算法,douglas-peucker,Radial distance,Nth point等。使用win7,VS2013,Qt5.5.1,64位编译。对原程序作了Qt适应性修改。psimpl_v7_win32_demo\src\demo\x64\Debug下的程序可直接运行,裸机已实验
Douglas-Peucker算法是经典的多边形压缩算法
一种改进的基于Douglas-Peucker原理的轮廓采样算法,张真,罗立民,本文首先介绍了Douglas-Peucker曲线化简算法的原理,然后提出了DP算法的一种非递归实现方法,该过程主要是利用队和栈的性质来实现的。�
基于流量突变特征的Douglas-Peucker改进算法,欧阳雯,毛京丽,本文提出一种基于Douglas-Peucker算法框架的改进算法,针对算法对于一些重要特征点会被舍弃的缺点,利用小波变换检测流量突变的特性来
现有基于可缩放矢量图形SVG的空间矢量数据网络发布往往存在着网络延时大、浏览器资源占用率高等问题。...实验结果表明,该算法优于常用的Douglas-Peucker算法,在提高压缩率的同时也减少了计算时间。
Douglas-Peucker算法的讲解。经典的图形数据压缩算法。
可以简化一条线段 使用douglas-peucker算法来实现 一个线段的简化
Douglas-Peucker算法 在数字化过程中,需要对曲线进行采样简化,即在曲线上取有限个点,将其变为折线,并且能够在一定程度 上保持原有的形状。 经典的Douglas-Peucker算法描述如下: (1)在曲线首尾两点A,B之间...
用VC++实现Douglas-Peucker算法,对现状目标进行化简,通过改变参数,能轻易得到你想要的结果
用于 matlab 的 Douglas Peucker 算法。
在arcpy中实现Douglas-Peucker压缩算法。
在数字化过程中,需要对曲线进行采样简化,即在曲线上取有限个点,将其变为折线,并且能够在一定程度上保持原有的形状。
在 Objective C 中使用 Douglas-Peucker 线逼近算法进行路径优化
主要介绍了Java编程实现轨迹压缩之Douglas-Peucker算法详细代码,具有一定借鉴价值,需要的朋友可以参考。
用于线数据的化简,用visual studiou 2005实现
% Ramer-Douglas-Peucker 算法 (RDP) 是一种减少% 曲线中由一系列近似的点数% 点。 该算法的初始形式是独立提出的% 于 1972 年由 Urs Ramer 和 1973 年由 David Douglas 和 Thomas Peucker 以及% 在接下来的十年中...
Douglas-Peucker算法
这是 Ramer-Douglas-Peucker 算法的演示。 RDP_GUI.m 用鼠标在第一个图形上画线,然后在第二个图形中绘制一条简化的曲线。 DouglasPeucker.m 使用 Ramer-Douglas-Peucker 算法降低矢量数据中的点密度。