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). ** ** 1.png

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

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

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

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). ** ** 5-6.png ** 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. ** ** 7.png

** 3. Divide the Bezier curve by the obtained $ t_ {min} and t_ {max} $ to make a new Bezier curve. ** ** 8.png ** 4. Repeat the process of 2-3 until the interval $ [t_ {min}, ~ t_ {max}] $ becomes sufficiently small. ** ** 9.png ** 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. ** ** 10.png

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 1.png Second time 2.png Third time 3.png 4th 4.png

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.

References

Recommended Posts

I want to find the intersection of a Bezier curve and a straight line (Bezier Clipping method)
Find the intersection of a circle and a straight line (sympy matrix)
I want to clear up the question of the "__init__" method and the "self" argument of a Python class.
I want to know the features of Python and pip
I want to get the name of the function / method being executed
Scraping and tabelog ~ I want to find a good restaurant! ~ (Work)
I want to create a histogram and overlay the normal distribution curve on it. matplotlib edition
I want to extract the tag information (title and artist) of a music file (flac, wav).
I want to analyze the emotions of people who want to meet and tremble
Python: I want to measure the processing time of a function neatly
I wanted to play with the Bezier curve
I want to easily find a delicious restaurant
I want to customize the appearance of zabbix
[LINE Messaging API] I want to send a message from the program to everyone's LINE
The story of IPv6 address that I want to keep at a minimum
I want to set a life cycle in the task definition of ECS
I want to add silence to the beginning of a wav file for 1 second
I want to see a list of WebDAV files in the Requests module
I want to get the file name, line number, and function name in Python 3.4
I want to find a popular package on PyPi
I want to fully understand the basics of Bokeh
I want to install a package of Php Redis
I want to increase the security of ssh connections
I tried to notify the update of "Become a novelist" using "IFTTT" and "Become a novelist API"
I can't find the clocksource tsc! ?? The story of trying to write a kernel patch
The story of Linux that I want to teach myself half a year ago
I want to take a screenshot of the site on Docker using any font
I want to write a triple loop and conditional branch in one line in python
I want to divide an nth-order Bezier curve at an arbitrary point ~ Recursion and matrix ~
I tried to find the entropy of the image with python
I want to save the photos sent by LINE to S3
I tried to find the average of the sequence with TensorFlow
I want to start a lot of processes from python
I want to use only the normalization process of SudachiPy
NikuGan ~ I want to see a lot of delicious meat! !!
I want to get the operation information of yahoo route
I want to find a stock that will rise 5 minutes after the Nikkei Stock Average rises
I want to judge the authenticity of the elements of numpy array
I want to send a message from Python to LINE Bot
How to find the scaling factor of a biorthogonal wavelet
I want to output a beautifully customized heat map of the correlation matrix. matplotlib edition
I want to map the EDINET code and securities number
Keras I want to get the output of any layer !!
I want to know the legend of the IT technology world
I want to create a Dockerfile for the time being.
[Python] A program to find the number of apples and oranges that can be harvested
I want to get information from fstab at the ssh connection destination and execute a command
I wrote AWS Lambda, and I was a little addicted to the default value of Python arguments
I made a Line bot that guesses the gender and age of a person from an image
Find the white Christmas rate by prefecture with Python and map it to a map of Japan
I tried to find out the difference between A + = B and A = A + B in Python, so make a note
[Twitter] I want to make the downloaded past tweets (of my account) into a beautiful CSV
I want to manually assign the training parameters of the [Pytorch] model
I want to automatically find high-quality parts from the videos I shot
I created a Python library to call the LINE WORKS API
I want to read the html version of "OpenCV-Python Tutorials" OpenCV 3.1 version
[Introduction to Python] I compared the naming conventions of C # and Python.
[Introduction to StyleGAN] I played with "The Life of a Man" ♬
I want to output the beginning of the next month with Python
I want to find the shortest route to travel through all points
I want to create a system to prevent forgetting to tighten the key 1