TRAKLA2 - Douglas-Peucker Line Simplification

Douglas-Peucker Line Simplification

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions Simplify the line by simulating the Douglas-Peucker line simplification algorithm. Douglas-Peucker is an algorithm for line simplification. Its principle is simple: Check if points between start and end points fit into a tolerance area around the line segment between them. If yes, only start and end point are needed from the segment. If not, choose the farthest lying point as an end point and repeat check. When segment is handled move to the next segment which has current ending point as start and most previous ending point as end point. A point can be dragged from the polyline to the stack top or to the simplified polyline. The stack top. Points can be added to either structure by dropping them to the structure header. The blue stack visualization cannot be manipulated. It is there to show the contents of the stack. A point can be moved from the stack to the simplified polyline by dragging it from the stack top. The polyline view will show the polyline in white and the simplified version in red. It will also show the tolerance area between two points. The distance of any point from the line segment created by two points can be calculated by clicking on the point. The distance will be shown in the distance text field.
Douglas-Peucker 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