import matplotlib.pyplot as plt
import json
X = 0
Y = 1

def scale(s, pt):

    return s*pt[X], s*pt[Y]

def dist_squared(p1, p2):

    return (p1[X] - p2[X])**2 + (p1[Y] - p2[Y])**2

def sub(p1, p2):

    return p1[X] - p2[X], p1[Y] - p2[Y]

def add(p1, p2):

    return p1[X] + p2[X], p1[Y] + p2[Y]

def dot(p1, p2):

    return p1[X] * p2[X] + p1[Y] * p2[Y]

def dist_to_segment(begin, end, curr):

    d2 = dist_squared(begin, end)
    if d2 == 0.0:
        return dist_squared(begin, curr)

    diff  = sub(end, begin)
    d2beg = sub(curr, begin)

    t = min(1.0, max(0.0, dot(diff, d2beg) / d2))

    return dist_squared(add(begin, scale(t, diff)), curr)

def ramerdouglas(line, dist):

    if dist == 0.0:
        return line[:]

    if len(line) < 3:
        return line

    (begin, end) = (line[0], line[-1]) if line[0] != line[-1] else
    (line[0], line[-2])

    pos     = -1
    maxdist = -1.0
    l = len(line)
    for k in range(1,l):
        d2 = dist_to_segment(begin, end, line[k])
        if d2 > maxdist:
            maxdist = d2
            pos     = k - 1

    if maxdist < dist ** 2:
        return [begin, end]

    return (ramerdouglas(line[:pos + 2], dist) +
            ramerdouglas(line[pos + 1:], dist)[1:])

def to_xy(line):
    x = []
    y = []
    for pt in line:
        xx, yy = pt
        x.append(xx)
        y.append(yy)

    return (x, y)


if __name__ == "__main__":
    coast = [
    ( 0.181271 , 10.571000 ),
    ( 0.153745 , 10.620156 ),
    ( 0.114973 , 10.653889 ),
    ( 0.103274 , 10.707756 ),
    ( 0.157914 , 10.761511 ),
    ( 0.146256 , 10.811522 ),
    ( 0.061935 , 10.867833 ),
    ( 0.000000 , 10.960167 ),
    ( 8.107109 , 6.288978 ),
    ( 7.948394 , 6.177867 ),
    ( 7.925720 , 5.983422 ),
    ( 7.857699 , 5.816756 ),
    ( 7.835026 , 5.788978 ),
    ( 7.857699 , 5.511200 ),
    ( 7.812352 , 7.400089 ),
    ( 7.812352 , 4.344533 ),
    ( 7.812352 , 2.177867 ),
    ( 8.084435 , 4.733422 ),
    ( 8.107109 , 4.622311 ),
    ( 7.857699 , 4.344533 ),
    ( 7.630963 , 4.261200 ),
    ( 7.540268 , 4.177867 ),
    ( 7.494921 , 4.150089 )]


    x, y = to_xy(coast)

    cst = ramerdouglas(coast, 0.1)
    xx, yy = to_xy(cst)
    print(xx, yy)

    plt.plot(x, y, "bo", xx, yy, "r^")
    plt.show()

plt.plot(x, y, "bo", xx, yy, "r^")