[数据结构与算法]【直线提取】矢量数据压缩算法提取直线（RDP）

矢量数据压缩算法提取直线（RDP）

问题：给出一个点集合，从集合中提取所有的直线

1. 关键参数设置：
   一条直线上最少的点数：min_size_point：
   一条直线上相邻点之间的最大距离：max_interval
   一条直线上的点到该直线最大的距离：max_distance_threshold

2. 首先假设这些points在第一个点和最后一个点所在的直线上L，如果这些点的个数小于min_size_point则直接返回。
   遍历最后一个点之外的所有点，记录每个点到L的最大距离D和该点的索引D_i若D<max_distance且点的间隔都小于max_interval则points组成了一条直线，存储该直线并执行返回。若某个点p与下一个点间距大于max_interval则将p前后分成两组pints2和pints3然后分别递归执行步骤2。若相邻点间距都小于max_interval则判断D是否大于max_distance，若D>max_distance_threshold则将points从D_i处分成两段points2和points3分别递归执行步骤2.

3. 整个递归调用返回后既得到所有的直线。

参考代码：

    /**
     * @brief 使用RDP矢量数据压缩算法提取直线
     * @param Points 点集合
     * @param max_distance_threshold 点到线的最大距离，大于该值则认为不共线
     * @param resultlist 从点集合中提取出来的所有直线
     * @return true 成功 false 失败
     */
bool getLine(const std::vector<Point> &Points, double max_distance_threshold, std::vector<Line>& resultlist)
{
    if(Points.size() < min_size_point)
    {
      return false;
    }

    double max_distance = 0;
    int32_t max_i;
    int32_t interval_i = -1;

    size_t loop_size = Points.size()-1;
    for(int32_t i=0; i < loop_size;i++)
    {
        double point_interval = hypot(Points[i].x - Points[i+1].x, Points[i].y - Points[i+1].y);
        if(point_interval > max_interval)
        {
            interval_i = i;
            break; 
        }

        double D = point2LineDistance(Points[i], Points.front(), Points.back()); //点Points[i]到直线（Points.front()，Points.back()）的距离
        if(D > max_distance)
        {
            max_distance = D;
            max_i = i;
        }
    }
    if(interval_i != -1)
    {
        std::vector<Point> pre_points, next_points;

        pre_points.assign(Points.begin(), Points.begin() + interval_i+1); //前一段
        next_points.assign(Points.begin() + interval_i+1, Points.end()); //后一段

        std::vector<Line> resultlist1;
        getLine(pre_points, max_distance_threshold, resultlist1);
        std::vector<Line> resultlist2;
        getLine(next_points, max_distance_threshold, resultlist2);

        if ( !resultlist1.empty())
            resultlist.insert(resultlist.end(), resultlist1.begin(), resultlist1.end());
        if( !resultlist2.empty())
            resultlist.insert(resultlist.begin(), resultlist2.begin(), resultlist2.end());
    }
    else if(max_distance > max_distance_threshold) // 如果点到线的距离最大值大于max_distance_threshold
    {
        std::vector<Point> pre_points, next_points;

        pre_points.assign(Points.begin(), Points.begin() + max_i+1); //前一段
        next_points.assign(Points.begin() + max_i, Points.end()); //后一段

        std::vector<Line> resultlist1;
        getLine(pre_points, max_distance_threshold, resultlist1);
        std::vector<Line> resultlist2;
        getLine(next_points, max_distance_threshold, resultlist2);

        if ( !resultlist1.empty())
            resultlist.insert(resultlist.end(), resultlist1.begin(), resultlist1.end());
        if( !resultlist2.empty())
            resultlist.insert(resultlist.begin(), resultlist2.begin(), resultlist2.end());
    }
    else
    {
        Line result;
        result.start_point = Points.front();
        result.end_point = Points.back();
        resultlist.push_back(result);
    }
    return true;
}