道格拉斯-普克算法
该算法也以Douglas-Peucker算法和迭代终点拟合算法为名。算法的目的是给出由线段组成的曲线（在某些上下文中也称为折线），以找到具有较少点的相似曲线。 该算法基于原始曲线和简化曲线（即曲线之间的豪斯多夫距离）之间的最大距离定义“不相似”。 简化曲线由定义原始曲线的点的子集组成。
算法描述如下：
起始曲线是有序的一组点或线，距离维度ε> 0。该算法递归地划分线。 最初给出了第一点和最后一点之间的所有点。 它会自动标记要保存的第一个和最后一个点。 然后找到距离第一点和最后一点组成的线段的最远的点作为终点; 这一点在距离终点之间的近似线段的曲线上显然最远。 如果该点比线段更接近于ε，那么当前未被标记的任何点将被保存，而没有简化的曲线比ε更差的可以丢弃。
如果离线段最远的点距离近似值大于ε，则必须保留该点。 该算法以第一个点和最远点递归地调用自身，然后以最远点和最后一个点（包括最远点被标记为保留）递归调用自身。
当递归完成时，可以生成一个新的输出曲线，其中包括所有且仅标记为保留的点。
非参数Ramer-Douglas-Peucker
ε的选择通常是用户定义的。 像大多数线拟合/多边形近似/主点检测方法一样，通过使用由于数字化/量化的误差界限作为终止条件，可以使其非参数化[1] 这种非参数RDP算法[2]的MATLAB代码在这里可用[3]
伪代码：
假设输入是基于一一数组
function DouglasPeucker(PointList[], epsilon)
// Find the point with the maximum distance
dmax = 0
index = 0
end = length(PointList)
for i = 2 to ( end - 1) {
d = perpendicularDistance(PointList[i], Line(PointList[1], PointList[end]))
if ( d > dmax ) {
index = i
dmax = d
}
}
// If max distance is greater than epsilon, recursively simplify
if ( dmax > epsilon ) {
// Recursive call
recResults1[] = DouglasPeucker(PointList[1...index], epsilon)
recResults2[] = DouglasPeucker(PointList[index...end], epsilon)
// Build the result list
ResultList[] = {recResults1[1...length(recResults1)-1], recResults2[1...length(recResults2)]}
} else {
ResultList[] = {PointList[1], PointList[end]}
}
// Return the result
return ResultList[]
end
该算法用于处理矢量图形 和制图综合。该算法广泛应用于机器人技术[4]中，对旋转量程扫描仪采集的范围数据进行简化和去噪; 在这个领域中，它被称为分裂合并算法，归因于Duda和Hart。
该算法的复杂度可以利用线性递归来描述T(n)
= 2T( n⁄2)
+ O(n)，其具有T（n）∈Θ（n
log n）的公知解决方案（通过主定理）。
然而，最坏情况的复杂度是Θ（n2）。
#include "opencv2/imgproc.hpp"
#include "opencv2/highgui.hpp"
#include
#include
using namespace cv;
using namespace std;
static void help()
{
cout<< "\nThis program illustrates the use of findContours and drawContours\n"
<< "The original image is put up along with the image of drawn contours\n"
<< "Usage:\n"<< "./contours2\n"
<< "\nA trackbar is put up which controls the contour level from -3 to 3\n"
<< endl;
}
const int w = 500;
int levels = 3;
vector > contours;
vector hierarchy;
static void on_trackbar(int,void*)
{
Mat cnt_img = Mat::zeros(w, w, CV_8UC3);
int _levels = levels - 3;
drawContours( cnt_img, contours, _levels <=0 ? 3 : -1, Scalar(128,255,255),
3, LINE_AA, hierarchy, std::abs(_levels) );
imshow("contours", cnt_img);
}
int main( int argc, char** argv)
{
cv::CommandLineParser parser(argc, argv,"{help h||}");
if (parser.has("help"))
{
help();
return 0;
}
Mat img = Mat::zeros(w, w, CV_8UC1);
//Draw 6 faces
for( int i = 0; i < 6; i++ )
{
int dx = (i%2)*250 -30;
int dy = (i/2)*150;
const Scalar white = Scalar(255);
const Scalar black = Scalar(0);
if( i == 0 )
{
for( int j = 0; j <= 10; j++ )
{
double angle = (j+5)*CV_PI/21;
line(img, Point(cvRound(dx+100+j*10-80*cos(angle)),
cvRound(dy+100-90*sin(angle))),
Point(cvRound(dx+100+j*10-30*cos(angle)),
cvRound(dy+100-30*sin(angle))), white,1, 8, 0);
}
}
ellipse( img, Point(dx+150, dy+100),Size(100,70),0, 0, 360, white, -1,8, 0 );
ellipse( img, Point(dx+115, dy+70),Size(30,20),0, 0, 360, black, -1,8, 0 );
ellipse( img, Point(dx+185, dy+70),Size(30,20),0, 0, 360, black, -1,8, 0 );
ellipse( img, Point(dx+115, dy+70),Size(15,15),0, 0, 360, white, -1,8, 0 );
ellipse( img, Point(dx+185, dy+70),Size(15,15),0, 0, 360, white, -1,8, 0 );
ellipse( img, Point(dx+115, dy+70),Size(5,5),0, 0, 360, black, -1,8, 0 );
ellipse( img, Point(dx+185, dy+70),Size(5,5),0, 0, 360, black, -1,8, 0 );
ellipse( img, Point(dx+150, dy+100),Size(10,5),0, 0, 360, black, -1,8, 0 );
ellipse( img, Point(dx+150, dy+150),Size(40,10),0, 0, 360, black, -1,8, 0 );
ellipse( img, Point(dx+27, dy+100),Size(20,35),0, 0, 360, white, -1,8, 0 );
ellipse( img, Point(dx+273, dy+100),Size(20,35),0, 0, 360, white, -1,8, 0 );
}
//show the faces
namedWindow( "image",1 );
imshow( "image", img );
//Extract the contours so that
vector > contours0;
findContours( img, contours0, hierarchy, RETR_TREE, CHAIN_APPROX_SIMPLE);
contours.resize(contours0.size());
for( size_t k = 0; k < contours0.size(); k++ )
approxPolyDP(Mat(contours0[k]), contours[k],3, true);
namedWindow( "contours",1 );
createTrackbar( "levels+3","contours", &levels,7, on_trackbar );
on_trackbar(0,0);
waitKey();
return 0;
}
转载自：https://blog.csdn.net/wangmengmeng99/article/details/72519393
