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 |