道格拉斯—普克法（Douglas—Peucker）简化线算法报告线简化算法程序设计报告 ⽮量数据是GIS中，使⽤⾮常普遍的⼀种数据类型。在使⽤中，有时需要对⽮量数据进⾏压缩，⽮量数据压缩的⽬的是删除冗余数据，减少数据的存贮量，节省存贮空间，加快后继处理的速度。 ⽮量数据的压缩⽅法常⽤的有道格拉斯—普克法、垂距法、光栏法。本⽂主要讨论道格拉斯—普克法，运⽤该算法的思想，⽤C语⾔于TC20中编写⼀个⼩程序，实现对既有线的简化。
⾸先，简要介绍下道格拉斯—普克法(Douglas—Peucker)的核⼼思想：
基本思路(如图1)：
对每⼀条曲线的⾸末端点连⼀条线，求所有点到该直线的距离，并出最⼤距离值dmax，⽤dmax与限差D相⽐： （1）若dmax＜D，这条曲线上的中间点全部舍去；
（2）若dmax≥D，保留dmax对应的坐标点，并以该点为界，把曲线分为两部分，对这两部分重复使⽤该⽅法。
图1
由该算法的基本思路可知，该算法是递归的，⽽且算法的核⼼是求得点到直线的距离。根据以上分析，结合⽼师给出的数据，编写出了程序代码。
经过调试，能实现线简化的功能。
使⽤TC20做为程序的开发环境，主程序流程图如下所⽰：
该算法的主要功能函数是Simp()，该函数的功能是根据输⼊的限差LimitDis 确定线上的点是保留还是
去除。
Simp()函数的实现思想是，将曲线上的各点与曲线的端点连接，组成⼀个三⾓形，如下：
先根据点到点的距离公式，求出a,b,c 的值。然后再应⽤余弦公式
cosA=(b*b+c*c-a*a)/(2*b*c);cosB=(a*a+c*c-b*b)/(2*a*c);sinA=(float)sqrt(1-co sA*cosA)；再根据cosA ，cosB ，sinA 的值，算出距离。对每个点进⾏上述的计算，求出每个点到AB 的距离，取最⼤值和LimitDis ⽐较，如果⼤于限差，那么从C 点将曲线分为⼆段，重复第⼀步。如果⼩于，则去除AB 间的所有点。
该函数的流程图如下：
C
A B
b c a
算法源代码：
#include "stdio.h"
#include "math.h"
#include "graphics.h"
/*---------------------------------------------------------*/
/*----------------define the points struct-----------------*/
/*---------------------------------------------------------*/ typedef struct Point {dfm
float x,y;
char Res;
};
FILE *fp;
int iNum;
float LimitDis;
struct Point Pt[30];
/*-------------------------------------------------------*/
/*----------save the points to the structtype------------*/
/*-------------------------------------------------------*/
void Savetostruct()
{
float px,py;
int j=0;
if((fp=fopen("C:\\","r"))==NULL)
{
printf("Can't Open the File\n");
exit(0);
实验场}
while(!feof(fp))
{
刘师培fscanf(fp,"%f %f",&px,&py);
Pt[iNum].x=px;
Pt[iNum].y=py;
Pt[iNum].Res='T';
iNum++;
}
printf("These are the Original Points before Simplized :");
for(j=0;j<=iNum-1;j++)
{
printf("\nOriginalPt-%d x=%f y=%f \n",j,Pt[j].x,Pt[j].y);
}
printf("\n Toatal points: %d \n",j);
};
/*-------------------------------------------------------*/
蓟县莱德商厦大火/*--------------------Simplize the line------------------*/ /*-------------------------------------------------------*/ void Simp(p1,p2) {
float a,b,c,cosA,cosB,sinA,maxdis,curdis;
int i=0,maxNO=0;
float p2pdis();
if((p2-p1)>=2)
{
maxdis=0.00;
c=p2pdis(p1,p2);
i=p1+1;
while(i
{
curdis=0.00;
b=p2pdis(p1,i);
女外阴a=p2pdis(p2,i);
cosA=(b*b+c*c-a*a)/(2*b*c); cosB=(a*a+c*c-b*b)/(2*a*c); sinA=(float)sqrt(1-cosA*cosA); if((cosA==0) || (cosB==0))
{
if(cosA==0)
{curdis=b;}
else
{curdis=a;}
}
else
{curdis=b*sinA;
}
if(maxdis<=curdis)
{
maxdis=curdis;
maxNO=i;
}
i++;
}/*end while*/
if(maxdis>=LimitDis)
{
美国参议院Simp(p1,maxNO);
Simp(maxNO,p2);
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议