Introduction

I was studying shape processing, but I couldn't get it right just by reading a book, so I decided to try programming.

What is a Bezier curve?

A Bezier curve is a curve shape created in a control polygon formed by connecting control points $ P_i $. One point that composes the Bezier curve is defined by the control points and parameters, and when they are connected, the Bezier curve as shown in the figure below can be drawn. The blue point is the control point.

Bezier curve calculation

This time, we are targeting Bezier curves drawn in two-dimensional space. Therefore, the component of the coordinate value is $ (X_i, Y_i) $.

First, the Bezier curve is defined by the following formula. With this formula, once $ t $ is determined, the point $ P (t) $ on the Bezier curve can be calculated. Calculate the point $ P (t) $ by changing $ t $ in the range of 0 to 1, and connect them to form a Bezier curve.

P(t) = \sum_{i=0}^{N}B_{N,i}(t)Q_i \tag{1}

B_{n,i}(t) = \begin{pmatrix}n\\i\end{pmatrix}t^i(1-t)^{n-i}　\tag{2}

There are various symbols such as $ t $ and $ N $, but the meaning of each is as follows.

t It is called a parameter or parameter. The possible range is $ 0 \ leq t \ leq 1 $.
N
Is the order For example, if the order is 3, you can draw a cubic Bezier curve. As the order is increased, the shape becomes more complicated.
Q_i It is a control point. In the above figure, it is the blue dot.

--Binomial coefficient The coefficient part calculated on the right side of $ B_ {n, i} (t) $ is called the binomial coefficient, and it is calculated by the following formula.

\begin{pmatrix} n\\i \end{pmatrix} = {_n\mathrm{C}_k=\frac{n!}{k!(n-k)!} } \tag{3}

Also, $ (2) $ is called a Bernstein polynomial.

program

The implemented python script is as follows.

--Bezier curve calculation part

#Binomial coefficient calculation
def BiCoe(n, k):
    if n < k :
        return -1
    return math.factorial(n) / (math.factorial(k) * math.factorial((n - k)))

#Bernstein polynomial
def Bernstein(n, i, t):
    return BiCoe(n, i) * np.power((1-t), (n-i)) * np.power(t, i)

#Bezier curve
def BezierCurve(points, t):
    Gt = 0
    n = len(points) - 1
    for k, point in enumerate(points):
        Gt += point * Bernstein(n, k, t)
            
    return Gt

--Bezier curve drawing part

#Draw Bezier curve
def DrawBezierCurve(points):
    x = np.arange(0, 1, 0.01, dtype=np.float32)
    x = np.append(x, 1.0)
    gt = [BezierCurve(points, t) for t in x]
    gt_x = [g[0] for g in gt]
    gt_y = [g[1] for g in gt]
    ct_x = [ct[0] for ct in points]
    ct_y = [ct[1] for ct in points]
    
    plt.plot(ct_x, ct_y, linestyle='dashed', linewidth=1)
    plt.plot(gt_x, gt_y, linewidth = 3)
    plt.scatter(ct_x, ct_y)

in conclusion

When I was reading the book, I thought it was stupid to say, "Can I draw a curve with this formula?" I think it has deepened. As a mathematics enthusiast, it took me a long time to research and understand a little bit. .. .. For example, it took about 30 minutes to know that the coefficient part is a binomial coefficient by looking at the formula of $ (2) $. (LOL) I will continue to study hard.

References

-[Introduction to 3D shape processing](https://www.amazon.co.jp/3%E6%AC%A1%E5%85%83%E5%BD%A2%E7%8A%B6%E5%87 % A6% E7% 90% 86% E5% 85% A5% E9% 96% 80% E2% 80% 953% E6% AC% A1% E5% 85% 83CG% E3% 81% A8CAD% E3% 81% B8 % E3% 81% AE% E5% 9F% BA% E7% A4% 8E-Information-Computing-% E4% BB% 8A% E9% 87% 8E-% E6% 99% 83% E5% B8% 82 / dp / 4781910483)