道格拉斯-普克抽稀算法

道格拉斯-普克抽稀算法

目的

用来对大量冗余的图形数据点进行压缩以提取必要的数据点。

过程

先将一条曲线首尾点虚连一条直线，求其余各点到该直线的距离，取其最大者与规定的临界值相比较，若小于临界值，则将直线两端间各点全部舍去，否则将离该直线距离最大的点保留，并将原线条分成两部分，对每部分线条再实施该抽稀过程，直到结束。

抽稀结果点数随选取限差临界值的增大而减少，应用时应根据精度来选取限差临界值，以获得最好的效果。

一个十分突出的优点

一个十分突出的优点,即它是一个整体算法，通过准确删除小弯曲上的定点，能够在整体上有效地保持线要素的形态特征。

正是因为道格拉斯-普克法具有这样突出的优点,所以已经在线要素地自动制图中得到了较广泛的应用。

C++代码实现

/*
 *  计算点到直线的距离
 */
double PerpendicularDistance(CPoint Point1, CPoint Point2, CPoint Point)
{
    //Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)|   *Area of triangle
    //Base = v((x1-x2)2+(x1-x2)2)                               *Base of Triangle*
    //Area = .5*Base*H                                          *Solve for height
    //Height = Area/.5/Base

    double area = abs(0.5 * (Point1.x * Point2.y + Point2.x * Point.y + Point.x * Point1.y - Point2.x * Point1.y - Point.x * Point2.y - Point1.x * Point.y));
    double bottom = sqrt(pow(Point1.x - Point2.x, 2) + pow(Point1.y - Point2.y, 2));
    double height = area / bottom * 2;

    return height;

}

/*
 *  将要保留的点添加到pointIndexsToKeep中
 */
void DouglasPeuckerReduction(vector<CPoint>points, int firstPoint, int lastPoint, double tolerance, list<int> &pointIndexsToKeep)
{
    double maxDistance = 0;
    int indexFarthest = 0;
    
    for (int index = firstPoint; index < lastPoint; index++)
    {
        double distance = PerpendicularDistance
            (points[firstPoint], points[lastPoint], points[index]);
        if (distance > maxDistance)
        {
            maxDistance = distance;
            indexFarthest = index;
        }
    }

    if (maxDistance > tolerance && indexFarthest != 0)
    {
        //Add the largest point that exceeds the tolerance
        pointIndexsToKeep.push_back(indexFarthest);
    
        DouglasPeuckerReduction(points, firstPoint, 
        indexFarthest, tolerance, pointIndexsToKeep);
        
        DouglasPeuckerReduction(points, indexFarthest, 
        lastPoint, tolerance, pointIndexsToKeep);
    }
}

/*
 *  对一组点进行抽稀
 */
vector<CPoint> DouglasPeucker(vector<CPoint> &Points, double Tolerance)
{
    if (Points.empty() || (Points.size() < 3))
    return Points;

    int firstPoint = 0;
    int lastPoint = Points.size() - 1;
    list<int> pointIndexsToKeep ;

    //Add the first and last index to the keepers
    pointIndexsToKeep.push_back(firstPoint);
    pointIndexsToKeep.push_back(lastPoint);

    //The first and the last point cannot be the same
    while (Points[firstPoint]==(Points[lastPoint]))
    {
        lastPoint--;
    }

    DouglasPeuckerReduction(Points, firstPoint, lastPoint, 
    Tolerance, pointIndexsToKeep);

    vector<CPoint> returnPoints ;
    pointIndexsToKeep.sort();
    list<int>::iterator theIterator;
    for( theIterator = pointIndexsToKeep.begin(); theIterator != pointIndexsToKeep.end(); theIterator++ )
    {
        returnPoints.push_back(Points[*theIterator]);
    }

    return returnPoints;
}