Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 787
Comrade Che Avatar asked Nov 02 '17 05:11

Comrade Che


2 Answers

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.

like image 71
Liran Funaro Avatar answered Nov 11 '22 19:11

Liran Funaro


Ok, it wasn't so hard, here is the code: enter image description here

import math

# visualisation
import matplotlib.pyplot as plt
import matplotlib.lines as lines
# visualisation

def Sum_points(P1, P2):
    x1, y1 = P1
    x2, y2 = P2
    return x1+x2, y1+y2

def Multiply_point(multiplier, P):
    x, y = P
    return float(x)*float(multiplier), float(y)*float(multiplier)

def Check_if_object_is_polygon(Cartesian_coords_list):
    if Cartesian_coords_list[0] == Cartesian_coords_list[len(Cartesian_coords_list)-1]:
        return True
    else:
        return False

class Object():

    def __init__(self, Cartesian_coords_list):
        self.Cartesian_coords_list = Cartesian_coords_list

    def Find_Q_point_position(self, P1, P2):
        Summand1 = Multiply_point(float(3)/float(4), P1)
        Summand2 = Multiply_point(float(1)/float(4), P2)
        Q = Sum_points(Summand1, Summand2) 
        return Q

    def Find_R_point_position(self, P1, P2):
        Summand1 = Multiply_point(float(1)/float(4), P1)
        Summand2 = Multiply_point(float(3)/float(4), P2)        
        R = Sum_points(Summand1, Summand2)
        return R

    def Smooth_by_Chaikin(self, number_of_refinements):
        refinement = 1
        copy_first_coord = Check_if_object_is_polygon(self.Cartesian_coords_list)
        while refinement <= number_of_refinements:
            self.New_cartesian_coords_list = []

            for num, tuple in enumerate(self.Cartesian_coords_list):
                if num+1 == len(self.Cartesian_coords_list):
                    pass
                else:
                    P1, P2 = (tuple, self.Cartesian_coords_list[num+1])
                    Q = obj.Find_Q_point_position(P1, P2)
                    R = obj.Find_R_point_position(P1, P2)
                    self.New_cartesian_coords_list.append(Q)
                    self.New_cartesian_coords_list.append(R)

            if copy_first_coord:
                self.New_cartesian_coords_list.append(self.New_cartesian_coords_list[0])

            self.Cartesian_coords_list = self.New_cartesian_coords_list
            refinement += 1
        return self.Cartesian_coords_list

if __name__ == "__main__":
    Cartesian_coords_list = [(1,1),
                             (1,3),
                             (4,5),
                             (5,1),
                             (2,0.5),
                             (1,1),
                             ]

    obj = Object(Cartesian_coords_list)    
    Smoothed_obj = obj.Smooth_by_Chaikin(number_of_refinements = 5)

    # visualisation
    x1 = [i for i,j in Smoothed_obj]
    y1 = [j for i,j in Smoothed_obj]
    x2 = [i for i,j in Cartesian_coords_list]
    y2 = [j for i,j in Cartesian_coords_list]    
    plt.plot(range(7),range(7),'w', alpha=0.7)
    myline = lines.Line2D(x1,y1,color='r')
    mynewline = lines.Line2D(x2,y2,color='b')
    plt.gca().add_artist(myline)
    plt.gca().add_artist(mynewline)
    plt.show()  
like image 11
Comrade Che Avatar answered Nov 11 '22 19:11

Comrade Che