C++实现道格拉斯-普克法压缩矢量数据

include “stdafx.h”

include “iostream”

include “stdlib.h”

include “stack”

using namespace std;

define STACK_SIZE 100 /* 堆栈最大容纳元素数量 */

stack stk;
//定义点结构
struct point
{
double x;
double y;
bool isSave;
};

//对数组进行排序(冒泡排序)
void sortArray(point* a,point* b,int n)
{

int i, j;
for (i = 0; i < n; i++)
{
    for (j = 0; i + j<n - 1; j++)
    {
        if ((*(a+j)).x>(*(a+j+1)).x)
        {
            point temp = *(a+j);
            *(a + j) = *(a+j+1);
            *(a + j + 1) = temp;
        }


    }
    *(b + n - i - 1) = *(a + n - i - 1);
}

for (int j = 0; j < n;j++)
{
    printf("the %d line is: %f \n", j, (*(b + j)).x);
}

}

//求最大值
void maxDouble(double* a, int n)
{

int i, j;
for (i = 0; i < n-1; i++)
{   
        if ((*(a + i)) > (*(a + i + 1)))
        {
            double temp = *(a + i);
            *(a + i) = *(a + i + 1);
            *(a + i + 1) = temp;
        }   
}

}
//求点到直线的距离
double getDistance(point M, point N, point P)
{
double distance;//距离
double numerator, denominator;//分子和分母
numerator = abs((N.y - M.y)P.x + (M.x - N.x)*P.y + N.x M.y - M.x * N.y);
denominator = sqrt((N.y - M.y)(N.y - M.y) + (M.x - N.x)(M.x - N.x));
if (denominator == 0)
{
return -1;
}
else
{
distance = numerator / denominator;
return distance;
}
}
//道格拉斯-普克法 抽稀数组
void douglasArray(point* from, point* to, int n, double val)
{
double p[100] ;
double q[100];
to = (from + n - 1);

from->isSave = true;
to->isSave = true;

if (n<=2)
{
    return;
}
if (n==3)
{
    double midP_dist = getDistance(*from, *to, *(from + n - 2));
    if (midP_dist>val)
    {
        (from + n - 2)->isSave = true;
    }

}
if (n>3)
{
    for (int i = 1; i < n - 1; i++)
    {
        *(p + i) = getDistance(*from, *to, *(from + i));
        *(q + i) = *(p+i);
    }

    maxDouble((p + 1), n - 2);
    for (int m = 1; m < n - 1;m++)
    {
        if (*(q + m) == *(p + n - 2) && *(q + m)>val)
        {
            (from+m)->isSave = true;
            douglasArray(from, (from + m), m+1, val);
            douglasArray((from + m), (from + n - 1), n - m, val);           
        }
    }
}

}
int _tmain(int argc, _TCHAR* argv[])
{
//数据可以从文件读
point a[6] ;
a[0].x = 1; a[0].y = 3.5; a[0].isSave = false;
a[1].x = 1.5; a[1].y = 1.5; a[1].isSave = false;
a[2].x = 3; a[2].y = 2; a[2].isSave = false;
a[3].x = 4.5; a[3].y = 1.5; a[3].isSave = false;
a[4].x = 6; a[4].y = 3; a[4].isSave = false;
a[5].x = 8; a[5].y = 3.5; a[5].isSave = false;
point b[6];
sortArray(a, b, 6);
douglasArray(a, a + 5, 6, 0.9);
for (int i = 0; i < 6;i++)
{
if (a[i].isSave == true)
{
cout << i << endl;
}
}
system(“pause”);
return 0;
}