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?
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
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.
Ok, it wasn't so hard, here is the code:
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()
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With