Douglas-Peucker 曲线离散化算法.rar

在数字化过程中，需要对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且能够在一定程度上保持原有的形状。

#include “DouglasPeucker.h“

double DouglasPeucker::PerpendicularDistance（MyPointStruct &point1 MyPointStruct &point2 MyPointStruct &point3）
{
	// 点到直线的距离公式法
	double A B C maxDist = 0;
	A = point2.Y - point1.Y;
	B = point1.X - point2.X;
	C = point2.X * point1.Y - point1.X * point2.Y;
	maxDist = fabs（（A * point3.X + B * point3.Y + C） / sqrt（A * A + B * B））;
	return maxDist;
}

MyPointStruct DouglasPeucker::myConvert（int index）
{
	return PointStruct[index];
}

void DouglasPeucker::DouglasPeuckerReduction（int firstPoint int lastPoint double tolerance）
{
	double maxDistance = 0;
	int indexFarthest = 0;  // 记录最大值时点元素在数组中的下标

	for （int index = firstPoint; index < lastPoint; index++）
	{
		double distance = PerpendicularDistance（myConvert（firstPoint） myConvert（lastPoint） myConvert（index））;

		if （distance > maxDistance）
		{
			maxDistance = distance;
			indexFarthest = index;
		}
	}
	if （maxDistance > tolerance && indexFarthest != 0） 
	{
		myTag[indexFarthest] = true; // 记录特征点的索引信息

		DouglasPeuckerReduction（firstPoint indexFarthest tolerance）;
		DouglasPeuckerReduction（indexFarthest lastPoint tolerance）;
	}
}

DouglasPeucker::DouglasPeucker（vector &Pointsint tolerance）
{
	PointStruct = Points;
	int totalPointNum =Points.size（）;

	myTag.resize（totalPointNum0）;

	DouglasPeuckerReduction（0 totalPointNum-1 tolerance）;

	for （int index = 0; index	{
		if（myTag[index]）PointNum.push_back（index）;
	}
}
void DouglasPeucker::WriteData（const char *filename）
{
	FILE *fp = fopen（filename“w“）;
	int pSize = PointNum.size（）;
	for（int index=0;index	{
		fprintf（fp“%lf\t%lf\n“PointStruct[PointNum[index]].XPointStruct[PointNum[index]].Y）;
	}
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     126976  2009-03-01 16:08  Douglas_Peucker\debug\Douglas_Peucker.exe

     文件     520012  2009-03-01 16:08  Douglas_Peucker\debug\Douglas_Peucker.ilk

     文件     715776  2009-03-01 16:08  Douglas_Peucker\debug\Douglas_Peucker.pdb

     文件       9028  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug\BuildLog.htm

     文件     415120  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug\DouglasPeucker.obj

     文件        403  2009-03-01 14:33  Douglas_Peucker\Douglas_Peucker\Debug\Douglas_Peucker.exe.embed.manifest

     文件        468  2009-03-01 14:33  Douglas_Peucker\Douglas_Peucker\Debug\Douglas_Peucker.exe.embed.manifest.res

     文件        385  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug\Douglas_Peucker.exe.intermediate.manifest

     文件         67  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug\mt.dep

     文件     169606  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug\sample.obj

     文件     216064  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug\vc80.idb

     文件     249856  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug\vc80.pdb

     文件       1819  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\DouglasPeucker.cpp

     文件        982  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\DouglasPeucker.h

     文件       4124  2009-03-01 15:11  Douglas_Peucker\Douglas_Peucker\Douglas_Peucker.vcproj

     文件       1427  2009-03-01 16:13  Douglas_Peucker\Douglas_Peucker\Douglas_Peucker.vcproj.3C785FDEE0B54AD.luliang.user

     文件       1016  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\sample.cpp

     文件    1960960  2009-03-01 16:13  Douglas_Peucker\Douglas_Peucker.ncb

     文件        910  2009-03-01 13:41  Douglas_Peucker\Douglas_Peucker.sln

    ..A..H.     10752  2009-03-01 16:13  Douglas_Peucker\Douglas_Peucker.suo

     目录          0  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker\Debug

     目录          0  2009-03-01 16:08  Douglas_Peucker\debug

     目录          0  2009-03-01 16:08  Douglas_Peucker\Douglas_Peucker

     目录          0  2009-03-01 14:09  Douglas_Peucker

----------- ---------  ---------- -----  ----

              4405751                    24