道格拉斯——普克法(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 Algorithm)是另一种常用的矢量数据简化算法,它基于距离阈值来决定是否保留或删除点。光栏法(Visvalingam-Whyatt Algorithm)则是通过考虑局部细节对点进行重要性评估,并据此...
根据窗视变换原理,提出了视觉无损的SVG空间矢量数据压缩算法。该算法通过重新设定SVG的地图范围,根据新的范围对原始空间数据进行变换,从而实现空间数据的约减。实验结果表明,该算法优于常用的Douglas-Peucker...
道格拉斯-普克(Douglas-Peucker)算法,简称为DP算法,是一种用于压缩二维曲线点集的矢量数据压缩技术。该算法的主要目的是减少数据点的数量,同时尽可能保持原始曲线的基本形状,这对于存储和传输大量地理信息系统...
基于这些问题,提出了一个增强型道格拉斯-普克压缩算法,并通过实际的MapInfo矢量数据验证了该算法的有效性。 #### 二、Douglas-Peucker算法原理 Douglas-Peucker算法是一种用于简化矢量数据的常用方法,其基本...
3. 新的矢量数据压缩算法:文章提出了基于垂直距离方法和Douglas-Peucker算法的新的矢量数据压缩算法。这种算法通过特征点的提取和有效性判断,使得压缩过程不会导致图像失真。这种方法的核心在于通过数学分析,找到...
Douglas-Peucker算法作为一种经典的矢量压缩算法,因其简洁高效而被广泛应用于曲线数据的简化处理。其非递归实现方式进一步提升了算法的实用性和稳定性,为AutoCAD等绘图软件的用户提供了一种有效的曲线抽稀工具。...
道格拉斯压缩算法,又称道格拉斯-普克算法(Douglas-Peucker Algorithm),是一种在计算机图形学和地理信息系统中常用的算法,主要用于简化多边形或曲线,尤其是地图上的线条。这个算法的主要目标是在保持原始形状的...
道格拉斯-普克(Douglas-Peucker)压缩算法是一种常见的点序列简化算法,用于在保持几何形状基本不变的情况下减少点的数量,常用于地图绘制、CAD系统和计算机图形学等领域。该算法主要目的是降低数据量,提高数据...
综上所述,通过对现有曲线矢量数据压缩算法的比较研究,Douglas-Peucker算法因其简单高效的特点,在World Wind环境下的应用表现出了显著的优势。该算法不仅能够有效减少矢量数据的存储空间,还能确保较高的显示精度...
在IT领域,矢量地图数据压缩对于移动用户来说...综上所述,这种面向移动用户的矢量地图数据压缩方法通过优化数据结构和压缩算法,为移动设备提供了高效、节省流量的地图服务,极大地提升了用户在使用地图应用时的体验。
在本项目中,我们关注的是GIS中的两个关键算法:面裁剪算法和道格拉斯-普克(Douglas-Peucker)压缩算法。这两个算法在处理地理空间数据时具有重要意义。 面裁剪算法通常用于处理GIS中的几何对象,如多边形,以确定...
道格拉斯-普克(Douglas-Peucker,简称DP)压缩算法是一种常见的点序列简化算法,广泛应用于GIS(地理信息系统)和计算机图形学领域。该算法的主要目的是减少点的数量,同时尽可能保持原始几何形状的轮廓。在处理大...
利用Douglas-Peucker压缩算法提取矢量数据地物的特征点并计算地物特征点之间的距离比值,按阈值对比值序列进行划分,根据水印信息将特征点移动到相应的奇偶间隔之中,由此实现水印的嵌入。实验结果证明,该算法具有...
常用的等高线数据压缩算法包括间隔取点法、偏角法、Douglas-Peucker法和光栏法。间隔取点法计算简单,但可能导致曲线特征丢失;偏角法和光栏法是局部算法,而Douglas-Peucker算法则以其较好的压缩效果而被广泛采用。...
- 基于小波理论的矢量数据压缩模型:利用小波分析的强大特征提取能力,对等高线进行多分辨率分析,既能保持局部特征,又能实现数据压缩。 2. 成组等高线的综合 - 构建三角网:等高线转换为三角网后,可以进行结构...
空间数据压缩算法主要用于减少存储和传输的空间数据量,提升系统效率。常见的压缩算法包括: **1. 基于矢量的压缩算法** - **道格拉斯-普克算法(Douglas-Peucker Algorithm)**: 一种广泛使用的简化折线或多边形...
该算法通过提取曲线端点和曲线间交叉点这两类特殊点,以扫描跟踪的方式提取曲线上的所有像素点坐标,采用Douglas-Peucker法对曲线栅格点进行压缩,获得最终矢量图。实验结果表明,该算法能够有效地实现线状目标栅格图像...
常见的数据压缩方法有道格拉斯-普克算法(Douglas-Peucker Algorithm),用于简化曲线上的点,以及游程编码和四叉树编码用于栅格数据的压缩。压缩的目标是在保持一定精度的前提下,尽可能提高压缩比率。 空间数据的...
具体的曲线抽稀算法有步长法、线段过滤法、圆柱法、道格拉斯-普克法、垂矩限值法等多种,其中道格拉斯-普克法(Douglas-Peucker Algorithm)是矢量曲线数据压缩中一个成熟的算法。该算法通过选取曲线的两端点,计算...