Wo finde ich die Python-Implementierung von Chaikins Eckenschnittalgorithmus?

Question

Ich bin auf der Suche nach Chaikin Ecke Schnittalgorithmus (link1, link2) in Python 2.7.X implementiert, kann aber nicht finden.

Vielleicht hat jemand es und kann den Code teilen?

Answer 1

Ok, es war nicht so schwer, hier ist der 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() 

Answer 2

Herr Che Antwort wird funktionieren, aber hier ist eine viel kürzere Version, die etwas effizienter ist.

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 

Wie funktioniert es?

Für je zwei Punkte müssen wir den unteren Teil und den oberen Teil in der Leitung zwischen ihnen nehmen das Verhältnis 1: 3:

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

und fügen Sie sie beide auf die neue Punkteliste. Wir müssen auch die Kantenpunkte hinzufügen, damit die Linie nicht schrumpft.

Wir bauen zwei Arrays L und R in einer bestimmten Weise, dass, wenn wir sie wie folgt multiplizieren werden, es die neue Punktliste ergeben wird.

NEW-POINTS = L * 0.75 + R * 0.25 

Zum Beispiel, wenn wir Array von 4 Punkten haben:

P = 0 1 2 3 

die L- und R-Arrays sein wird, wie folgt:

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

wobei jede Zahl einen Punkt entspricht.