Create bezier curve from 2 conected curve

[temp]

hello
commonly when we have 2 connected curve and we want to find quadratic bezier curve base on them we can use this interesting method:
(see the 4 picture in the middle of following page and you quickly understand)

http://www.actionscript.org/resources/articles/172/1/Understanding-curves-and-control-point-placement/Page1.html

but this method isn't intelligence and has poor result in some cases
for example see this case:

http://i23.tinypic.com/2z4n776.jpg

fig1 is two original connected curve
fig2 is the result from this algorithm (black curve)
fig3 is the favorite result that i want (black curve)

so this is final question:
having two connected curve, how i can find the best quadratic bezier curve that fits this two curves?

 

[hotvette]

Looks like you are fitting a single quad bezier to a composite of two curves. If this is true, I'd probably use least squares. It is straightforward but tedious. If you want, I can explain in detail, but I'd like to use a specific example to illustrate. Can you post an example (equations for the 2 curves or x,y data points)?

 

[hotvette]

Per our PM exchanges last night, my understanding is that you want to combine two quad bezier curves into a single quad bezier curve. This is effectively reducing the order/flexibility of the curves. I know of no analytical/closed form way of doing this. Other Forum members might.

If least squares is a suitable approach for your situation (it may not be if computational efficiency is important), then the approach depends on a couple of important factors:

1. Whether the final curve needs to exactly go through the beginning and end points. In general, this isn't true with least squares, but in the case of quad bezier, the analysis is easier if the curve is forced to go through the end points.

2. Whether $p_{1x}$ of the final curve needs to be iteratively determined or not. The example you provided looks symmetric, which means the optimal value of $p_{1x}$ would be half way between the $p_{1x}$'s of the two curves to consolidate. Even if $p_{1x}$ needs to be determined, the situation boils down to a univariate optimization problem that can be solved using a variety of techniques (e.g. bisection, Newton Raphson, Brent's method, Simplex, etc.)

Assuming the most simplistic situation (i.e. the curve goes through the end points, meaning $p_{0y}$ and $p_{2y}$ are known, and $p_{1x}$ is known, perhaps due to symmetry), then only 1 variable is to be determined using least squares, and that is $p_{1y}$. With these assumption, here is a method that will work:


a. Calculate x,y for an aribtrary number (n) points for each of the original curves. I picked n = 10 for an example I did. The result is 20 x,y values that will be fit with a single quad bezier.

b. Make an initial guess for all six control points of the final quad bezier curve. Using the assumptions from #2 above, this really means just picking an initial value for $p_{1y}$.

c. For each x from step a, find the corresponding value of t that will produce the same x using the control points from step b. This means solving 2n-1 quadratic equations.

d. Once you know t for each x, calculate corresponding y values using the control points from step b. This allows you to readily calculate the sum-of-squares residual.

e. Calculate 2t(1-t) for each value of t from step c. This is used for performing least squares analysis to find the optimal $p_{1y}$. Effectively:
$$2t(1-t) = \frac{\partial p_{1y}}{\partial y}$$

f. Take each value of 2t(1-t) from step e, square and sum. Call this number z. Thus:
$$z = \sum (2t(1-t))^2 = \sum (2t - 2t^2)^2$$

g. Calculate the difference between y calculated in step d and y from step a. This is an array that we will call f-y.

h. For each element of f-y, multiply by the corresponding element from step e and sum. Thus:
$$\sum (f-y)2t(1-t) = \sum (f-y)(2t-2t^2)$$

i. The optimal value of $p_{1y}$ is simply the original guess minus the quantity from step h divided by z from step f. In other words:
$$(p_{1y})_f = p_{1y} - \frac{\sum (f-y)(2t-2t^2)}{\sum (2t-2t^2)^2}= p_{1y} - \frac{\sum (p_{0y}(1-t)^2+2p_{1y}t(1-t)+p_{2y}t^2-y)(2t-2t^2)}{\sum (2t-2t^2)^2}$$

Example using the above:

http://www.hostdump.com/uploads/83d023211c.jpg