Thuật toán đơn giản hóa đường cong: Douglas Peucker

Thuật toán Douglas Peucker

1. Ý tưởng

 Hình 1. Đơn giản hóa đường công theo thuật toán Douglas Peucker

Ý tưởng cơ bản của thuật toán Douglas-Peucker là xét xem khoảng cách lớn nhất từ đường cong tới đoạn thẳng nối hai đầu mút đường cong (hình 1) có lớn hơn ngưỡng θ không. Nếu điều này đúng thì điểm xa nhất được giữ lại làm điểm chia đường cong và thuật toán được thực hiện h > θ tương tự với hai đường cong vừa tìm được. Trong trường hợp ngược lại, kết quả của thuật toán đơn giản hoá là hai điểm đầu mút của đường cong.

Thuật toán Douglas-Peucker:

• Bước 1:    Chọn ngưỡng θ.

• Bước 2:    Tìm khoảng cách lớn nhất từ đường cong tới đoạn thẳng nối hai đầu đoạn đường cong h.

• Bước 3:    Nếu h ≤ θ thì dừng.

• Bước 4:    Nếu h > θ thì giữ lại điểm đạt cực đại này và quay trở lại bước 1.

Nhận xét: Thuật toán này tỏ ra thuận lợi đối với các đường cong thu nhận được mà gốc là các đoạn thẳng, phù hợp với việc đơn giản hoá trong quá trình véctơ các bản vẽ kỹ thuật, sơ đồ thiết kế mạch in v.v..

5.1.2.2. Chương trình

//Hàm tính đường cao từ dinh đến đoạn thẳng nối hai điểm dau, cuoi float Tinhduongcao (POINT dau, POINT cuoi, POINT dinh)

{

floot h;

|| tính đường cao

returm h ;

}

//Hàm đệ quy nhằm đánh dấu loại bỏ các điểm trong đường cong

void DPSimple(POINT *pLINE,int dau,int cuoi,BOOL *chiso,float θ)

{

int i, index = dau;

float h, hmax = 0;

for(i = dau + 1; i < cuoi; i++) {

h= Tinhduongcao(pLINE[dau], pLINE[cuoi]; pLINE[i]);

if(h > hmax) {

hmax = h;

index = i;

}

}

if(hmax ≤ θ)

for(i= dau + 1; i < cuoi, i++)

chiso[i] = FALSE;

else {

DPSimple(PLINE, dau, index, chiso, θ);

DPSimple(PLINE, index, cuoi, chiso, θ) ;

}

}

//Hàm rút gọn số lượng điểm DouglasPeucker

int DouglasPeucker(POINT *pLINE, int n, float θ)

{          int i, j;

BOOL chiso [MAX_PT];

for(i = 0; i < m; i++) //Tất cả các điểm được giữ lại

chiso[i] = TRUE;

DPSimple(pLINE, 0, n – 1, chiso, θ);

for(i = j = 0; i < n; i ++)

if (chiso [i] ==TRUE)

pLINE[j++] = pLINE[i];

return j;

}