哪里可以找到Chaikin角切割算法的Python实现？

Question

我正在寻找在Python 2.7.X中实现的Chaikin的角切割算法（link1，link2），但找不到它。

也许有人拥有它并且能够共享代码？

Answer 1

Che先生的回答是有效的，但这里的版本更短，效率稍高。

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?

对于每两个点，我们需要使用1：3的比例将它们之间的下半部分和上半部分放在它们之间：

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

并将它们添加到新点列表中。我们还需要添加边缘点，因此线条不会缩小。

我们以某种方式构建两个数组L和R，如果我们将它们相乘，它将产生新的点列表。

NEW-POINTS = L * 0.75 + R * 0.25

例如，如果我们有4个点的数组：

P = 0 1 2 3

L和R数组如下：

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

其中每个数字对应一个点。

Answer 2

好吧，这不是很难，这里是代码：

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()