geometry.py 文件源码

def simplify_segment(segment, epsilon):
    """Ramer-Douglas-Peucker algorithm"""
    if len(segment) < 3 or epsilon <= 0:
        return segment[:]

    l = Segment(segment[0], segment[-1])  # Longest segment

    # Find the furthest point from the segment
    index, maxDist = max([(i, l.pdistance(p)) for i, p in enumerate(segment)],
                         key=operator.itemgetter(1))

    if maxDist > epsilon:
        # Recursively call with segment splited in 2 on its furthest point
        r1 = simplify_segment(segment[:index + 1], epsilon)
        r2 = simplify_segment(segment[index:], epsilon)
        # Remove redundant 'middle' Point
        return r1[:-1] + r2
    else:
        return [segment[0], segment[-1]]