[PYTHON] I want to find the intersection of a Bezier curve and a straight line (Bezier Clipping method)

Introduction

In my junior research, I had to find the intersection of a Bezier curve and a straight line. I was helping with my research

"** Python is a strong library or a concise implementation example! Margin **: grin :"

I was thinking, but I couldn't find an article that was written ** at a level that I could understand. I couldn't help but focus on the Bezier Clipping method, which seems to be relatively easy and I found some commentary PDFs. I have read the paper, understood and implemented it, so I will leave that knowledge. Please note that some expressions may be inaccurate in the article (and please give me some corrections).

The implemented code is published on GitHub.

What is a Bezier curve?

A Bezier curve is a type of curve representation. It is often used to represent curves on a computer such as outline fonts and CG. A Bezier curve consists of several points called control points, in addition to the start and end points of the curve. Hereinafter, the control points including the start point and the end point will be referred to. The Bezier curve is expressed as follows using the parameter $ t $$ (0 \ leq t \ leq 1) $.

\begin{align}
P(t) &= \sum_{i=0}^{n} F_i B_{i}^{n}(t) \\
&= \sum_{i=0}^{n} F_i {n \choose i} t^i \left(1-t \right)^{n-i}
\end{align}

$ F_i $ is the control point and $ B_ {i} ^ {n} $ is the Bernstein Basis Polynomials. Also, $ {n \ choose i} $ represents a combination. The world standard seems to be this way of writing, but if you write it as you learned in Japanese high school, it will be as follows.

P(t) = \sum_{i=0}^{n} F_i ~~ {}_n \mathrm{C} {}_r ~~ t^i \left(1-t \right)^{n-i}

Since the Bezier curve is a set of points at $ t $$ (0 \ leq t \ leq 1) $, The finer the step size of $ t $, the smoother the curve. The following is an example of changing the step size. The gray $ \ times $ points represent control points. ** When $ (0 \ leq t \ leq 1) $ is divided into 5 (when only 5 points are calculated). ** **

** When $ (0 \ leq t \ leq 1) $ is divided into 10 (when only 10 points are calculated). ** **

** When $ (0 \ leq t \ leq 1) $ is divided into 50 (when only 50 points are calculated). ** **

** When $ (0 \ leq t \ leq 1) $ is divided into 100 (when only 100 points are calculated). ** **

Bezier Clipping method

Overview

The Bezier Clipping method is a method to find the intersection of a curve and a straight line by using the property of the Bezier curve. Proposed in 1990 by Nishida et al. The features are as follows (partial excerpt).

--All solutions (intersections) in the specified range can be found. --Stable solution is required --High-speed judgment of the existence of a solution --Solutions can be calculated in ascending order --Iterative calculation of only linear expressions ... etc

It seems that it can also be applied to intersections between Bezier curves and intersections in three-dimensional space. This time, we will limit it to Bezier curves and straight lines.

algorithm

The general flow of the algorithm is as follows. ** 1. Convert the target Bezier curve to a Bezier curve that represents the distance to a straight line (convert from the $ xy $ plane to the $ td $ plane). ** ** ** 2. Find the convex hull (convex-hull) of the control point of the converted Bezier curve, and find the intersections $ t_ {min} and t_ {max} $ with the $ t $ axis. ** **

** 3. Divide the Bezier curve by the obtained $ t_ {min} and t_ {max} $ to make a new Bezier curve. ** ** ** 4. Repeat the process of 2-3 until the interval $ [t_ {min}, ~ t_ {max}] $ becomes sufficiently small. ** ** ** 5. The obtained $ t $ (red dot in the above figure) becomes the parameter $ t $ of the original Bezier curve at the intersection with the straight line. ** **

The algorithm itself is very simple. Probably the place to get stuck

-** Bezier curve conversion process ** -** Processing when multiple intersections exist **

I think it is, so I will explain it in detail in the next section.

Bezier curve conversion process

It assumes a two-dimensional plane coordinate space. The straight line $ L $ in the plane space can be expressed as follows. $ a, b, c $ are constants.

ax + by + c = 0

The distance $ d $ between any point $ (x_1, y_1) $ in the coordinate space and the straight line $ L $ can be expressed as follows.

d = \frac{ax_1+by_1+c}{\sqrt{a^2 + b^2}}

Here, the point $ (x, y) $ on the Bezier curve can be obtained as follows with $ t $ as the intermediary variable. $ (x_i, y_i) $ represents the control point of the Bezier curve.

\begin{align}
x(t) &= \sum_{i=0}^{n} x_i B_i^n (t) \\
y(t) &= \sum_{i=0}^{n} y_i B_i^n (t)
\end{align}

Using these, the distance $ D $ between the straight line $ L $ and the Bezier curve can be expressed as follows.

\begin{align}
D &= \frac{ax(t)+by(t)+c}{\sqrt{a^2+b^2}} \\ \\
  &= \frac{1}{\sqrt{a^2+b^2}}\left( a\sum_{i=0}^{n} x_i B_i^n (t) + b\sum_{i=0}^{n} y_i B_i^n (t) + c \right)
\end{align}

Since $ \ sum_ {i = 0} ^ {n} B_i ^ n (t) = 1 $,

\begin{align}
D &= \frac{1}{\sqrt{a^2+b^2}}\left( a\sum_{i=0}^{n} x_i B_i^n (t) + b\sum_{i=0}^{n} y_i B_i^n (t) + c\sum_{i=0}^{n} B_i^n (t) \right) \\ \\
  &= \frac{1}{\sqrt{a^2+b^2}}\sum_{i=0}^{n} (ax_i+by_i+c) B_i^n (t) \\ \\
  &= \frac{1}{\sqrt{a^2+b^2}}\sum_{i=0}^{n} d_i B_i^n (t) 
\end{align}

Here, $ D $ is a rational Bezier curve consisting of the control points $ \ left (\ frac {i} {n}, d_i \ right) $. Also, $ D $ is a Bezier curve on the $ td $ plane, that is, a Bezier curve in a plane space with the horizontal axis $ t $ and the vertical axis $ d $. The fact that the converted Bezier curve $ D $ takes $ d = 0 $ at some $ t ~ (0 \ leq t \ leq 1) $ means that At that $ t $ value, it means that the distance between the Bezier curve and the straight line in the $ xy $ plane before conversion is zero. Therefore, the parameter $ t $ at the intersection of the straight line and the Bezier curve can be calculated. After that, if you enter the parameter $ t $ at the intersection in the following equation, the coordinates of the intersection on the $ xy $ plane can be obtained.

\begin{align}
x(t) &= \sum_{i=0}^{n} x_i B_i^n (t) \\
y(t) &= \sum_{i=0}^{n} y_i B_i^n (t)
\end{align}

Processing when there are multiple points

The process is simple when there are multiple intersections. If there are multiple intersections, the change between $ t_ {min} $ and $ t_ {max} $ will be small. An example is shown in the figure below. The blue dot in the figure represents the previous $ t_ {min}, t_ {max} $ dot.

First time Second time Third time 4th

From the third time, you can see that the positions of $ t_ {min} and t_ {max} $ have not changed. In this case, divide the curve at an appropriate point and apply the Bezier Clipping method again to each Bezier curve. It didn't seem to mention the point of division. In my implementation, I try to divide it at the midpoint.

in conclusion

In this article, I explained the Bezier Clipping method. I had a lot of trouble understanding the first part of the conversion. I hope the content of this article is useful to someone.