C++ 道格拉斯-普克（DP）算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++ 道格拉斯-普克（DP）算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3087字，纯文字阅读大概需要5分钟。

内容图文

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

算法的基本思路是:对每一条曲线的首末点虚连一条直线,求所有点与直线的距离,并找出最大距离值dmax ,用dmax与限差D相比:若dmax <D,这条曲线上的中间点全部舍去;若dmax ≥D,保留dmax 对应的坐标点,并以该点为界,把曲线分为两部分,对这两部分重复使用该方法。

 

// DP.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "iostream"
#include "fstream"
#include "string"
#include "vector"
#include "cmath"
#include <algorithm>

using namespace std;

class Point
{
public:
	int ID;
	string Name;
	double x;
	double y;
	bool isRemoved = false;


};

double PointToLine(Point p1, Point p2, Point p3)
{
	double dist;
	double A, B, C;
	A = -(p2.y - p1.y) / (p2.x - p1.x);
	B = 1.0;
	C = -A * p1.x - p1.y;
	dist = abs(A * p3.x + B * p3.y + C) / sqrt(A * A + B * B);
	return dist;
}

double getMaxDist(vector<Point> &Points, int begin, int end)
{
	vector<double> dists;
	double maxdist;
	for (int i = begin; i <= end; i++)
	{
		dists.push_back(PointToLine(Points[begin], Points[end], Points[i]));
	}
	auto max = max_element(dists.begin(), dists.end());
	return *max;
}

int getMaxDistIndex(vector<Point> &Points, int begin, int end)
{
	vector<double> dists;
	int index;
	for (int i = begin; i <= end; i++)
	{
		dists.push_back(PointToLine(Points[begin], Points[end], Points[i]));
	}
	auto max = max_element(dists.begin(), dists.end());
	index = Points[begin].ID + distance(dists.begin(),max);
	return index;
}

void DP(vector<Point> &Points, int begin, int end, double threshold)
{
	int mid;
	if (end - begin > 1)
	{
		if (getMaxDist(Points, begin, end) > threshold)
		{
			mid = getMaxDistIndex(Points, begin, end);
			DP(Points, begin, mid, threshold);
			DP(Points, mid, end, threshold);
		}
		else
		{
			for (int i = begin + 1; i < end; i++)
			{
				Points[i].isRemoved = true;
			}
		}
	}
	else
	{
		return;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	

	ifstream file;
	ofstream out;
	string line;


	vector<Point> points1;
	vector<Point> points2;


	file.open("轨迹数据.txt");
	if (!file.is_open())
	{
		cout << "The file doesn't exist!" << endl;
		system("Pause");
		exit(1);
	}
	Point point;
	int count = 0;
	cout << "raw data" << endl;
	while (!file.eof())
	{
		getline(file, line);
		char *cstr = new char[line.length() + 1];
		strcpy(cstr, line.c_str());
		char *p = strtok(cstr, ",");
		point.Name = p; p = strtok(NULL, ",");
		point.x = atof(p); p = strtok(NULL, ",");
		point.y = atof(p); point.ID = count++;
		points1.push_back(point);
		points2.push_back(point);
		cout << point.Name << "," << point.x << "," << point.y << "\n";
	}


	DP(points1, 0, 16, 5.0);
	DP(points2, 0, 16, 8.0);

	cout << "\n\nthreshold=5.0" << endl;
	for (int i = 0; i < points1.size();i++)
	{
		if (points1[i].isRemoved==false)
		{
			cout << points1[i].Name << "," << points1[i].x << "," << points1[i].y << "\n";
		}
	}
	cout << "\n\nthreshold=8.0" << endl;
	for (int i = 0; i < points2.size(); i++)
	{
		if (points2[i].isRemoved == false)
		{
			cout << points2[i].Name << "," << points2[i].x << "," << points2[i].y << "\n";
		}
	}
	return 0;
}

内容总结

以上是互联网集市为您收集整理的C++ 道格拉斯-普克（DP）算法全部内容，希望文章能够帮你解决C++ 道格拉斯-普克（DP）算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---