simplify-py

simplify.py

# python version of http://mourner.github.com/simplify-js/
class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
        
    def __repr__(self):
        return "<Point x=%s y=%s>" % (self.x, self.y)
        
def sqDist(p1, p2):
    dx = p1.x - p2.x
    dy = p1.y - p2.y
    return dx ** 2 + dy ** 2

def sqSegDist(p, p1, p2):
    x  = p1.x
    y  = p1.y

    dx = p2.x - x
    dy = p2.y - y

    if dx != 0 or dy != 0:
        t = ((p.x - x) * dx + (p.y - y) * dy) / (dx * dx + dy * dy)
        if t > 1:
            x = p2.x
            y = p2.y
        elif t > 0:
            x += dx * t
            y += dy * t

    dx = p.x - x
    dy = p.y - y
    return dx ** 2 + dy ** 2

def simplifyRadialDist(points, sqTolerance):
    newPoints = [points[0]]
    prev = 0
    points_len = len(points)
    for i in xrange(1,points_len):
        if sqDist(points[i], points[prev]) > sqTolerance:
            newPoints.append(points[i])
            prev = i

    if prev < points_len - 1:
        newPoints.append(points[points_len - 1])
    return newPoints

def markPointsDP(points, markers, sqTolerance, first, last):
    maxSqDist = 0
    index = 0
    for i in xrange(first + 1, last):
        sqDist = sqSegDist(points[i], points[first], points[last])
        if sqDist > maxSqDist:
            index = i
            maxSqDist = sqDist

    if maxSqDist > sqTolerance:
        markers[index] = 1
        markPointsDP(points, markers, sqTolerance, first, index)
        markPointsDP(points, markers, sqTolerance, index, last)


def simplifyDouglasPeucker(points, sqTolerance):
    markers = [0 for i in xrange(len(points))]
    markers[0] = markers[len(points) - 1] = 1
    markPointsDP(points, markers, sqTolerance, 0, len(points) - 1)
    
    newPoints = []
    for i in xrange(len(points)):
        if markers[i]:
            newPoints.append(points[i])
    return newPoints

def simplify(points, tolerance = None):
    tolerance = tolerance or 1
    sqTolerance = tolerance ** 2
    points = simplifyRadialDist(points, sqTolerance)
    points = simplifyDouglasPeucker(points, sqTolerance)
    return points