录十六

一、什么是抽稀？

在处理矢量曲线数据时，记录中往往会有很多重复数据，对进一步数据处理带来诸多不便。多余的数据一方面浪费了较多的存储空间，另一方面造成所要表达的图形不光滑或不符合标准。因此要通过某种规则，在保证矢量曲线形状不变的情况下， 最大限度地减少数据点个数，这个过程称为抽稀。

通俗的讲就是对曲线进行采样简化，即在曲线上取有限个点，将其变为折线，并且能够在一定程度保持原有形状。比较常用的两种抽稀算法是：道格拉斯-普克(Douglas-Peuker)算法和垂距限值法。

二、道格拉斯-普克抽稀算法

Douglas一Peukcer算法由D.Douglas和T.Peueker于1973年提出，简称D一P算法，是眼下公认的线状要素化简经典算法。现有的线化简算法中，有相当一部分都是在该算法基础上进行改进产生的。它的长处是具有平移和旋转不变性，给定曲线与阂值后，抽样结果一定。

经典的Douglas-Peucker算法描述如下：

1. 在曲线首尾两点A，B之间连接一条直线AB，该直线为曲线的弦；

2. 得到曲线上离该直线段距离最大的点C，计算其与AB的距离d；

3. 比较该距离与预先给定的阈值threshold的大小，如果小于threshold，则该直线段作为曲线的近似，该段曲线处理完毕。

4. 如果距离大于阈值，则用C将曲线分为两段AC和BC，并分别对两段取信进行1~3的处理。

5. 当所有曲线都处理完毕时，依次连接各个分割点形成的折线，即可以作为曲线的近似。

三、算法实现

按照算法逻辑实现即可，完整实现如下：

int  MCDouglas::Compress(Vector2f*  ptArray, int nSize, float threshold)
{
    m_fThreshold = threshold;

    m_ptArray = ptArray;
    m_nSize = nSize;

    //初始索引
    m_idxArray =  new int[nSize];
    for(int i=0; i<nSize ; i++)
    {
        m_idxArray[i] = i;
    }

    //抽稀
    if(m_nSize > 2)
    {
        Compress(0, nSize-1);
    }

    //刪除抽稀掉的点
    int nPos = 1;
    for(int i = 1; i<nSize; i++)
    {
        if(m_idxArray[i] >= 0)
        {
           m_ptArray[nPos++] = m_ptArray[i];
        }
    }
    //释放内存
    delete[]  m_idxArray;

    //返回抽稀后的点数量
    return nPos;
}

//真正的抽稀函数
void MCDouglas::Compress(int idxFrom, int idxTo)
{
    int   middleIdx = -1;
    float maxDistance = 0;

    for(int i = idxFrom + 1; i<idxTo; i++)
    {
        float fDistance = Point2LineDistance(m_ptArray[idxFrom], m_ptArray[idxTo], m_ptArray[i]);

        if(fDistance > maxDistance)
        {
            maxDistance = fDistance;
            middleIdx = i;
        }
    }

    if(maxDistance  < m_fThreshold)
    {
        //删除多余的点
        for(int i = idxFrom + 1; i<idxTo; i++)
        {
            m_idxArray[i] = -1;
        }
    }
    else
    {
        //依次抽稀左，右两条线    
        if(middleIdx > idxFrom +1 )
        {
            Compress(idxFrom,  middleIdx); 
        }

        if(idxTo > middleIdx +1 )
        {
            Compress(middleIdx,  idxTo); 
        }
    }
}

//点到直线距离
float  MCDouglas::Point2LineDistance(const Vector2f& pt1, const Vector2f& pt2, const Vector2f& pnt)
{

    Vector2f vecU = pt2 - pt1;
    Vector2f vecV = pnt - pt1;

    float fArea = vecU.x * vecV.y - vecU.y * vecV.x; 

    float fLenth = vecU.Length();

    if(fLenth != 0) 
    {
        float fDistance = fArea/fLenth; 

        //取绝对值
        if(fDistance < 0)
        {
            fDistance = -fDistance;
        }

        return fDistance;
    }
    else
    {   
        //直线两点重合，退化成线
        float fDistance = vecV.Length();
        return fDistance;
    }
}

//两点之间距离
float  MCDouglas::Distance(const Vector2f& pnt1, const Vector2f& pnt2)
{
    Vector2f vec = pnt1 - pnt2;

    float dist = vec.Length();

    return dist;
}

四、运行结果

源码下载：Douglas