max edge distance Simplification key Figure 4-1: A sample process for the Douglas-Peucker algorithm The Douglas-Peucker algorithm is for the selection of representative points to simplify a curve...

Extracted text: max edge distance Simplification key Figure 4-1: A sample process for the Douglas-Peucker algorithm The Douglas-Peucker algorithm is for the selection of representative points to simplify a curve composed of line segments. It uses a point-to-edge distance tolerance. The algorithm starts with a crude simplification that is the single edge joining the first and last vertices of the original polyline. It then computes the perpendicular distance of all intermediate vertices to that edge. The vertex that is furthest away from that edge, and that has a computed distance that is larger than a specified tolerance, will be marked as a key and added to the simplification. This process will recurse for each edge in the current simplification until all vertices of the original polyline are within tolerance of the simplification results. This process is illustrated in Figure 4-1.


Extracted text: (2) Suppose we have an abstract data type (ADT) of Point that contains the x-axis and y-axis of a point. We also have a function pDistance that computes the perpendicular distance from p to line ab. The input of pDistance is (p,a, b), and the return value is a float value representing the distance. Fill in the function farthestPoint regarding how to locate the point with the maximum perpendicular distance to the starting point points[0] and the ending point points[- 1]. def pDistance(p, a, b): # p, a, b are of type Point # return the distance from p to line ab def farthestPoint(points): # points is a list of type Point maxIdx = 1 maxDist = 0 for idx in range (1, len(points) - 1): dist ®_, points[-1]) %3D if _@. maxIdx = idx maxDist = dist %3D # returns the index and distance of the farthest point return maxIdx, maxDist