- #1

- 13

- 0

having a set of points of a curve, how i can find the best quadratic bezier curve that fits this curve?

(so we have start and end points of bezier curve, and only the position of control point is required.)

THX.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter temp
- Start date

- #1

- 13

- 0

having a set of points of a curve, how i can find the best quadratic bezier curve that fits this curve?

(so we have start and end points of bezier curve, and only the position of control point is required.)

THX.

- #2

hotvette

Homework Helper

- 996

- 5

Welcome to the forums!

Are you looking for a mathematical/theoretical development or a practical 'how to' approach?

Also, I presume you are fitting a single curve to the data points vs a series of connected quad Bezier splines. Also depends on what method you want for 'best fit'. Least squares comes to mind, but even then, there are at least two variations - sum of the square of vertical distances or sum of square of normal distances (sometimes called total least squares). Lastly, you imply the only unknown is the control point. That's true if you assume the Bezier start and end points are coincident with the start and end data points. If the Bezier start and end points are allowed to float, then there are 6 unknowns.

I've studied this a bit using cubic Beziers (https://www.physicsforums.com/showthread.php?t=166391) and haven't yet found (or created) a good mathematical development. What makes it tricky is having to find the value of the independent variable t to produce the x values you want so the y values can be computed and compared. It means solving a quadratic equation (which is easy) to determine the right t for each x.

One way to view this is as an optimization problem in 2 variables (i.e. x and y of the control point). There are many optimization approaches (e.g. simplex) that could solve this. The practical approach I've taken is:

1. Choose starting values for control point x & y

2. Calculate the necessary t's (by solving quadratic equation) to produce the x's of the data points

3. Calculate y's and compare (in a least squares sense) to the data points

4. Update the control point x & y based on the result of step 3 and go to step 2

I've done this two different ways. One is using an optimization Excel Add-In I found on a website. Another method was a traditional least squares approach that was quite involved because it required successive iterations of first optimizing the control point y, then x until a converged solution was found.

Are you looking for a mathematical/theoretical development or a practical 'how to' approach?

Also, I presume you are fitting a single curve to the data points vs a series of connected quad Bezier splines. Also depends on what method you want for 'best fit'. Least squares comes to mind, but even then, there are at least two variations - sum of the square of vertical distances or sum of square of normal distances (sometimes called total least squares). Lastly, you imply the only unknown is the control point. That's true if you assume the Bezier start and end points are coincident with the start and end data points. If the Bezier start and end points are allowed to float, then there are 6 unknowns.

I've studied this a bit using cubic Beziers (https://www.physicsforums.com/showthread.php?t=166391) and haven't yet found (or created) a good mathematical development. What makes it tricky is having to find the value of the independent variable t to produce the x values you want so the y values can be computed and compared. It means solving a quadratic equation (which is easy) to determine the right t for each x.

One way to view this is as an optimization problem in 2 variables (i.e. x and y of the control point). There are many optimization approaches (e.g. simplex) that could solve this. The practical approach I've taken is:

1. Choose starting values for control point x & y

2. Calculate the necessary t's (by solving quadratic equation) to produce the x's of the data points

3. Calculate y's and compare (in a least squares sense) to the data points

4. Update the control point x & y based on the result of step 3 and go to step 2

I've done this two different ways. One is using an optimization Excel Add-In I found on a website. Another method was a traditional least squares approach that was quite involved because it required successive iterations of first optimizing the control point y, then x until a converged solution was found.

Last edited:

- #3

- 13

- 0

but i have problem yet (i can't understand your method correctly).

its great that if you could explain your method with a sample (practical)

- #4

hotvette

Homework Helper

- 996

- 5

OK, I was able to create a relatively simple example, all done with Excel. First, some preliminaries. The standard form of a quadratic Bezier is: B(t) = (1-t)^{2}P_{0} + 2t(1-t)P_{1} + t^{2}P_{2}……….0 ≤ t ≤ 1

Expanding and collecting terms, the equation can be put in classic polynomial form: B(t) = at^{2} + bt + c, where:

a = P_{0} – 2 P_{1} + P_{2}

b = 2P_{0} + 2 P_{1}

c = P_{0}

The above expressions really represent two equations, one for x and the other for y:

x(t) = a_{x}t^{2} + b_{x}t + c_{x}

y(t) = a_{y}t^{2} + b_{y}t + c_{y}

Calling the control points P_{0} = (p_{0x}, p_{0y}), P_{1} = (p_{1x}, p_{1y}), P_{2} = (p_{2x}, p_{2y})

a_{x} = p_{0x} – 2 p_{1x} + p_{2x}

a_{y} = p_{0y} – 2 p_{1y} + p_{2y}

b_{x} = 2p_{0x} + 2 p_{1x}

b_{y} = 2p_{0y} + 2 p_{1y}

c_{x} = p_{0x}

c_{y} = p_{0y}

Thus, we’ve established a relationship between the Bezier control points the polynomial coefficients.

Least Squares analysis involves fitting a desired function f to a set of points p = [p_{1}, p_{2}, ..p_{n}] = [(x_{1}, y_{1}), (x_{2}, y_{2}), … (x_{n}, y_{n})]. A standard means of determining ‘quality of fit’ is to sum the squares of the differences in vertical distance between the data points and the points generated by the function:

sum of squares = (f(x_{1}) - y_{1})^{2} + (f(x_{2}) - y_{2})^{2} … + (f(x_{n}) – y_{n})^{2}

The idea is to make the sum of squares as small as possible. The key is that the same value of x must be used for each point, so only vertical distance is being used). This is a challenge when using parametric curves because x is a function of the independent variable t. Thus, for each data point, the proper t needs to be determined such that the resulting x is identical to the x of the data point.

Here is a specific example. Suppose we wish to fit a quadratic Bezier to the following data points:

[(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3}), (x_{4}, y_{4}), (x_{5}, y_{5})] = [(0, 0), (0.2, 0.01), (0.7, 0.4), (0.9, 0.8), (1, 1)]

Here is the simple approach I used:

1. Make an initial guess at control point P_{1} (P_{0} = (0, 0) and P_{2} = (1, 1) are given). I used P_{1} = (0.7, 0) as an initial guess.

2. Calculate the polynomial coefficients:

a_{x} = p_{0x} – 2 p_{1x} + p_{2x} = 0 – 2(0.7) + 1 = -0.4

b_{x} = 2p_{0x} + 2 p_{1x} = 2(0) + 2(0.7) = 1.4

c_{x} = p_{0x} = 0

3. Generate x, y points for t = 0 to 1 and plot the Bezier curve. Plot the original data points and see how close the fit is. (It is instructive to play around with various values for p_{1x} and p_{1y} and see how the shape of the curve changes in relation to the data points).

4. Calculate the sum of squares. Here’s the tricky part. To calculate (f-y)^{2}, you need to find t that results in the same x as the data point. For example, x_{2} = a_{x}t_{2}^{2} + b_{x}t_{2} + c_{x}. To find the t_{2} that produces x_{2}, a quadratic equation needs to be solved (i.e.[ –b ± sqrt(b^{2}-4ac)]/2a). This needs to be done for all interior points (the end points are already known). Thus, for the initial control points used:

t_{1} = 0...........==> x_{1} = 0, y_{1} = 0

t_{2} = 0.149..........==> x_{2} = 0.2, y_{2} = 0.022

t_{3} = 0.604..........==> x_{3} = 0.7, y_{3} = 0.365

t_{4} = 0.849……….==> x_{4} = 0.9, y_{4} = 0.72

t_{5} = 1……….==> x_{5} = 1, y_{5} = 1

Now we can calculate the sum of squares = (0 – 0)^{2} + (0.022 – 0.01)^{2} + (0.365 – 0.04)^{2} + (0.72 – 0.8)2 + (1 – 1)^{2} = 0.008

5. Try new values of P_{1} until the sum of squares is minimized. Each time that p_{1x} is changed, three sets of quadratic equations must be solved to find t associated with each x. As an example, suppose we try P_{1} = (0.6, 0). Then:

a_{x} = p_{0x} – 2 p_{1x} + p_{2x} = 0 – 2(0.6) + 1 = -0.2

b_{x} = 2p_{0x} + 2 p_{1x} = 2(0) + 2(0.6) = 1.2

c_{x} = p_{0x} = 0

t_{1} = 0...........==> x_{1} = 0, y_{1} = 0

t_{2} = 0.172..........==> x_{2} = 0.2, y_{2} = 0.029

t_{3} = 0.655..........==> x_{3} = 0.7, y_{3} = 0.429

t_{4} = 0.879……….==> x_{4} = 0.9, y_{4} = 0.772

t_{5} = 1……….==> x_{5} = 1, y_{5} = 1

sum of squares = (0 – 0)^{2} + (0.029 – 0.01)^{2} + (0.429 – 0.04)^{2} + (0.772 – 0.8)2 + (1 – 1)^{2} = 0.002

If Excel is used and the formulas are set up correctly, the quadratic equations will be automatically solved each time P_{1} is changed.

For this example, I just used the Excel built-in solver function to minimize the cell containing the sum of squares and allowing p_{1} (i.e. p_{1x} and p_{1y}) to be changed. The net result:

P_{1} = (0.543, -0.108)

(a_{x}, a_{y}) = (-0.087, 1.216)

(b_{x}, b_{y}) = (1.087, -0.216)

(c_{x}, c_{y}) = (0, 0)

sum of squares = 0.001

It should be noted that forcing the end points of the Bezier curve to be coincident with the first and last data points is an artificial restriction that limits the quality of fit. If p_{0y} and p_{2y} are also allowed to be adjusted, a better fit can be achieved. Also, since parametric curves are so flexible, it is relatively easy to get into a situation where the best fit curve has a loop somewhere in the middle or the curve otherwise takes on a completely unexpected and undesirable shape. Such are the caveats of least squares fitting with parametric curves.

.

Expanding and collecting terms, the equation can be put in classic polynomial form: B(t) = at

a = P

b = 2P

c = P

The above expressions really represent two equations, one for x and the other for y:

x(t) = a

y(t) = a

Calling the control points P

a

a

b

b

c

c

Thus, we’ve established a relationship between the Bezier control points the polynomial coefficients.

Least Squares analysis involves fitting a desired function f to a set of points p = [p

sum of squares = (f(x

The idea is to make the sum of squares as small as possible. The key is that the same value of x must be used for each point, so only vertical distance is being used). This is a challenge when using parametric curves because x is a function of the independent variable t. Thus, for each data point, the proper t needs to be determined such that the resulting x is identical to the x of the data point.

Here is a specific example. Suppose we wish to fit a quadratic Bezier to the following data points:

[(x

Here is the simple approach I used:

1. Make an initial guess at control point P

2. Calculate the polynomial coefficients:

a

b

c

3. Generate x, y points for t = 0 to 1 and plot the Bezier curve. Plot the original data points and see how close the fit is. (It is instructive to play around with various values for p

4. Calculate the sum of squares. Here’s the tricky part. To calculate (f-y)

t

t

t

t

t

Now we can calculate the sum of squares = (0 – 0)

5. Try new values of P

a

b

c

t

t

t

t

t

sum of squares = (0 – 0)

If Excel is used and the formulas are set up correctly, the quadratic equations will be automatically solved each time P

For this example, I just used the Excel built-in solver function to minimize the cell containing the sum of squares and allowing p

P

(a

(b

(c

sum of squares = 0.001

It should be noted that forcing the end points of the Bezier curve to be coincident with the first and last data points is an artificial restriction that limits the quality of fit. If p

.

Last edited:

- #5

- 1

- 0

I believe the b term in the quadratic should be -2P0 + 2P1.

Share: