Douglas-Peucker Line Simplification

Hide text Hide pseudo-code

Simplify the line by simulating the Douglas-Peucker line simplification algorithm.

DOUGLAS_PEUCKER(Polyline l, int tolerance)
1.  initialize list Q
2.  initialize stack S
3.  let v be the array of vertices in l
4.  anchor = v[0]
5.  floater = v[v.length - 1]
6.  Q.append(anchor)
7.  S.push(floater)
8.  while (S is not empty)
9.    let seq be a line seqment from anchor to floater
10.   maxd = 0
11.   farthest = floater
13.   i = index of anchor + 1
14.   while (i < index of floater)
15.     let d be the shortest distance from seq to v[i]
16.     if (d > maxd)
17.       maxd = d
18.       farthest = v[i]
19.     i = i + 1
20.   if (maxd <= tolerance)
21.     Q.append(S.pop())
22.     anchor = floater
23.     floater = S.peek()
24.   else
25.     floater = farthest
26.     S.push(floater)
27. return Q


  Created Wed Jun 20 16:00:43 EEST 2007 - Powered by SVG-hut