www.gusucode.com > VC++道格拉斯普克算法源码程序 > VC++道格拉斯普克算法源码程序/code/DouglasPeuker.cpp

    // DouglasPeuker.cpp : Defines the entry point for the console application.
// Download by http://www.NewXing.com

#include "stdafx.h"
#include <vector>
#include <stdio.h>
#include <math.h>
using namespace std;

typedef struct point
{
	double x;
	double y;
}POINT;

vector<POINT> initialPoints;
vector<POINT> FinalPoints;
bool *bTag=NULL;
//////////////////////////////////////////////////////////////////////////
void Readdata(char *);
void DouglasPeuker(int ,int ,double);
double cacuDistance(int ,int ,int);
void Writedata(char *);

//////////////////////////////////////////////////////////////////////////
int main(int argc, char* argv[])
{
	int nums=0;
	char path1[]=".\\jpl_vegetation_grass2.txt";//打开文件的路径
	char path2[]=".\\2.txt";//输出文件的路径
	double torelance;
	int i;
	int nums2=0;

	Readdata(path1);

	nums=initialPoints.size();
	bTag=(bool *)malloc(sizeof(bool)*nums);
	memset(bTag,0,nums);
	torelance=0.00002;

    DouglasPeuker(0,nums-1,torelance);

	for (i=0;i<nums;i++)
	{
		if(bTag[i])
		{
			FinalPoints.push_back(initialPoints[i]);
		}
	}

	Writedata(path2);
/*	nums2=FinalPoints.size();
	printf("final data:%d \n",nums2);
	for (i=0;i<nums2;i++)
	{
	
		printf("%lf %lf\n",FinalPoints[i].x,FinalPoints[i].y);
	}*/
	free(bTag);
	return 0;
}
void Readdata(char *filename)
{

	char predata1[256];
	char predata2[256];
	char predata3[256];

	FILE *filein;
//	int i;
	POINT point0;
	//float xi,yi;

	memset(predata1,0,256);
	memset(predata2,0,256);
	memset(predata3,0,256);
	filein=fopen(filename,"r");
//	for (i=0;i<3;i++)
	{
		fscanf(filein,"%[^\n]c\n",predata1);
	//	fscanf(filein,"%[^\n]c\n",predata2);
	//	fscanf(filein,"%[^\n]c\n",predata3);
	}


	point0.x=0.00000;//启用浮点库，不加报错
	point0.y=0.00000;

	while (fscanf(filein,"%lf%lf",&point0.x,&point0.y)!=EOF)
	//while (fscanf(filein,"%f%f",&xi,&yi)!=EOF)
	{
		initialPoints.push_back(point0);
		printf("%f %f\n",point0.x,point0.y);
	}
	fclose(filein);
}
void DouglasPeuker(int leftpoint,int rightpoint,double tolerance)
{
	int i,maxindex;
	double dis,maxdis;
	maxdis=0;
	maxindex=0;
	for (i=leftpoint;i<rightpoint;i++)
	{
		dis=cacuDistance(leftpoint,rightpoint,i);
		if (dis>maxdis)
		{
			maxdis=dis;
			maxindex=i;
		}
	}

	if (maxdis>tolerance)
	{
		bTag[maxindex]=1;
	//	p=initialPoints(maxindex);
       // FinalPoints.push_back(initialPoints[maxindex]);
		DouglasPeuker(leftpoint,maxindex,tolerance);
		DouglasPeuker(maxindex,rightpoint,tolerance);//回调
	}
	else
	{
	//	FinalPoints.push_back(initialPoints[leftpoint]);
	//	FinalPoints.push_back(initialPoints[rightpoint]);
	}

}

double cacuDistance(int l,int r,int n)
{
	double a,b,c;
	//POINT p1,p2,p;
	double x1,x2,y1,y2,x,y;
	double dis=0;

	
	y1=initialPoints[l].y*1000;
	x1=initialPoints[l].x*1000;
	x2=initialPoints[r].x*1000;
	y2=initialPoints[r].y*1000;

	x=initialPoints[n].x*1000;
	y=initialPoints[n].y*1000;

	if (x1==x2)
	{
		dis=abs(x-x1);//两点式失效的情况
		return dis;
	}
	
	//解析直线
   a=(y2-y1)/(x2-x1);
   b=-1;
   c=y1-(y2-y1)/(x2-x1)*x1;

   dis=abs(a*x+b*y+c)/(sqrt(a*a+b*b));
   return dis;
}

void Writedata(char *pathname)
{
	FILE *fileout;
	int nums,i;
	fileout=fopen(pathname,"w");
	nums=FinalPoints.size();
	fprintf(fileout,"final points: %d\n",nums);
	for (i=0;i<nums;i++)
	{
		fprintf(fileout,"%lf  %lf\n",FinalPoints[i].x,FinalPoints[i].y);
	}

	fclose(fileout);

}