Where to find Python implementation of Chaikin's corner cutting algorithm?

Question

I am looking for Chaikin's corner cutting algorithm (link1, link2) implemented in Python 2.7.X but can't find it.

Maybe someone have it and able share the code?

Answer 1

The implementation below will work, but here is a much shorter version that is more efficient and elegant.

import numpy as np

def chaikins_corner_cutting(coords, refinements=5):
    coords = np.array(coords)

    for _ in range(refinements):
        L = coords.repeat(2, axis=0)
        R = np.empty_like(L)
        R[0] = L[0]
        R[2::2] = L[1:-1:2]
        R[1:-1:2] = L[2::2]
        R[-1] = L[-1]
        coords = L * 0.75 + R * 0.25

    return coords

How does it work?

For every two points, we need to take the lower part and the upper part in the line between them using the ratio 1:3:

LOWER-POINT = P1 * 0.25 + P2 * 0.75
UPPER-POINT = P1 * 0.75 + P2 * 0.25

and add them both to the new points list. We also need to add the edge points, so the line will not shrink.

We build two arrays L and R in a certain way that if we will multiply them as follows it will yield the new points list.

NEW-POINTS = L * 0.75 + R * 0.25

For example, if we have array of 4 points:

P = 0 1 2 3

the L and R arrays will be as follows:

L = 0 0 1 1 2 2 3 3
R = 0 1 0 2 1 3 2 3

where each number corresponds to a point.