Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Bezier curve fitting

  1. Aug 17, 2007 #1
    hello
    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. jcsd
  3. Aug 17, 2007 #2

    hotvette

    User Avatar
    Homework Helper

    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.
     
    Last edited: Aug 17, 2007
  4. Aug 19, 2007 #3
    thanx for your reply
    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)
     
  5. Aug 20, 2007 #4

    hotvette

    User Avatar
    Homework Helper

    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)2P0 + 2t(1-t)P1 + t2P2……….0 ≤ t ≤ 1

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

    a = P0 – 2 P1 + P2
    b = 2P0 + 2 P1
    c = P0

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

    x(t) = axt2 + bxt + cx
    y(t) = ayt2 + byt + cy

    Calling the control points P0 = (p0x, p0y), P1 = (p1x, p1y), P2 = (p2x, p2y)

    ax = p0x – 2 p1x + p2x
    ay = p0y – 2 p1y + p2y
    bx = 2p0x + 2 p1x
    by = 2p0y + 2 p1y
    cx = p0x
    cy = p0y

    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 = [p1, p2, ..pn] = [(x1, y1), (x2, y2), … (xn, yn)]. 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(x1) - y1)2 + (f(x2) - y2)2 … + (f(xn) – yn)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:

    [(x1, y1), (x2, y2), (x3, y3), (x4, y4), (x5, y5)] = [(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 P1 (P0 = (0, 0) and P2 = (1, 1) are given). I used P1 = (0.7, 0) as an initial guess.

    2. Calculate the polynomial coefficients:

    ax = p0x – 2 p1x + p2x = 0 – 2(0.7) + 1 = -0.4
    bx = 2p0x + 2 p1x = 2(0) + 2(0.7) = 1.4
    cx = p0x = 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 p1x and p1y 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, x2 = axt22 + bxt2 + cx. To find the t2 that produces x2, a quadratic equation needs to be solved (i.e.[ –b ± sqrt(b2-4ac)]/2a). This needs to be done for all interior points (the end points are already known). Thus, for the initial control points used:

    t1 = 0...........==> x1 = 0, y1 = 0
    t2 = 0.149..........==> x2 = 0.2, y2 = 0.022
    t3 = 0.604..........==> x3 = 0.7, y3 = 0.365
    t4 = 0.849……….==> x4 = 0.9, y4 = 0.72
    t5 = 1……….==> x5 = 1, y5 = 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 P1 until the sum of squares is minimized. Each time that p1x is changed, three sets of quadratic equations must be solved to find t associated with each x. As an example, suppose we try P1 = (0.6, 0). Then:

    ax = p0x – 2 p1x + p2x = 0 – 2(0.6) + 1 = -0.2
    bx = 2p0x + 2 p1x = 2(0) + 2(0.6) = 1.2
    cx = p0x = 0

    t1 = 0...........==> x1 = 0, y1 = 0
    t2 = 0.172..........==> x2 = 0.2, y2 = 0.029
    t3 = 0.655..........==> x3 = 0.7, y3 = 0.429
    t4 = 0.879……….==> x4 = 0.9, y4 = 0.772
    t5 = 1……….==> x5 = 1, y5 = 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 P1 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 p1 (i.e. p1x and p1y) to be changed. The net result:
    P1 = (0.543, -0.108)
    (ax, ay) = (-0.087, 1.216)
    (bx, by) = (1.087, -0.216)
    (cx, cy) = (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 p0y and p2y 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. :smile:
    .
     

    Attached Files:

    Last edited: Aug 20, 2007
  6. Oct 23, 2007 #5
    I believe the b term in the quadratic should be -2P0 + 2P1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Bezier curve fitting
  1. Bezier Curve Question (Replies: 1)

Loading...