Douglas-Peucker algorithm for image compression

Algorithm interpretation

WIKIPEDIA

The starting curve is an ordered set of points or lines and the distance dimension ε > 0.

The algorithm recursively divides the line. Initially it is given all the points between the first and last point. It automatically marks the first and last point to be kept. It then finds the point that is furthest from the line segment with the first and last points as end points; this point is obviously furthest on the curve from the approximating line segment between the end points. If the point is closer than ε to the line segment, then any points not currently marked to be kept can be discarded without the simplified curve being worse than ε.

If the point furthest from the line segment is greater than ε from the approximation then that point must be kept. The algorithm recursively calls itself with the first point and the furthest point and then with the furthest point and the last point, which includes the furthest point being marked as kept.

When the recursion is completed a new output curve can be generated consisting of all and only those points that have been marked as kept.

Gif Demo

Calculation steps

这里实现了基于链表的Douglas-Peucker算法，步骤如下：

Part I

判断点是否保留返回应保留点点号

1.读入点d[i],d[j],若j-i==1,转到7,若否,转到2;

2.计算过点P[i]和点P[j]的直线Ax+By+C=0;

3.根据点到直线距离公式计算P[i+1],P[i+2]…P[j-1]到直线的距离d[xx];

4.排序选出最大值d[k];

5.若d[k]>D(阈值),返回k,结束;

6.若d[k]<D(阈值),转到7;

7.返回0,结束;

Part II

生成应保留点链表函数

1.将第一点p[1]与最后一点p[n]写入链表.p[1]指向p[n],p[n]指向NULL,当前指针p指针指向p[1];

2.判断p->next是否指向NULL,若是,转到6;若否,转到3;

3.将p与p->next代入函数PartI,获得返回值R;

4.若R==0,p=p->next,转到2;

5.若R！=0,将p[R]插入链表到p与p->next之间,转到2;

6.结束.

Code display

	struct node
	{
        int num;                                      //point number
	    struct node *next;
    };
	int  m=sen;
    struct node *head;                                //header pointer
    struct node *pd;                                  //current pointer
    struct node *end;                                 //footer pointer
    struct node *new1;                                //new node

	head=(struct node*)malloc(sizeof(struct node));   
	head->num=0;                                      
    pd=head;                                           
	end=(struct node*)malloc(sizeof(struct node));  
	end->num=m-1;        
	head->next=end;
	end->next=NULL;

	while(pd->next!=NULL)
	{
		if(Douglas(point,pd->num,pd->next->num)!=0)
		{
        new1=(struct node*)malloc(sizeof(struct node)); 
        new1->num=Douglas(point,pd->num,pd->next->num);
		new1->next=pd->next;
		pd->next=new1;
		}
		else
			pd=pd->next;
	}

	pd=head;

int Douglas(double *p[], int n1, int n2)
{
	if(n2-n1==1)
		return 0;
	int n;                      //Maximum distance corresponding to the point number
	double d,dmax=0;            //Point to straight line distance
	double A,B,C;               //Calculated two straight line coefficients
	double D=3;                 //Threshold
	A=p[n1][1]-p[n2][1];                 
	B=p[n2][0]-p[n1][0];                 
	C=p[n1][0]*p[n2][1]-p[n2][0]*p[n1][1];   
	
	for(int i=n1+1;i<n2;i++)
	{
		d=fabs(A*p[i][0]+B*p[i][1]+C)/sqrt(A*A+B*B);             
		if(d>dmax)
		{
			dmax=d;
			n=i;
		}
	}

if(dmax>D)
   return n;
else 
   return 0;
}