What is the Best Method to Find the Peak Point of a Quadratic Bezier Curve?

[temp]

hello
i want to find the peak point of a quadratic bezier curve.
one approach is finding all distance between "start point","any point on curve","end point"

and then choosing then maximum distance between them.
but this approach get much time when implementing on computer
is there any other approach?

 

[hotvette]

I think all you have to do is solve y' = 0, just like you do in a non-parametric equation. Here's the logic. A max or min will occur where dy/dx = 0. In a parametric equation x = f(t) and y = g(t), dy/dx = (dy/dt)(dt/dx) = y'/x'. If you find where y' = 0, that's also where dy/dx = 0, unless x' happens to be zero or infinity at the same location.

Since you are dealing with a quadratic bezier:

$$x = a_xt^2 + b_xt + c_x$$
$$y = a_yt^2 + b_yt + c_y$$

then a max/min will occur at:

$$t = \frac{-0.5b_y}{a_y} = \frac{P_{y0} - P_{y1}}{P_{y0} -2P_{y1} + P_{y2}}$$

 

[temp]

thanx
but it gives me maximum-y point
i also can use such formula to calculate maximum-x point
but what i need is maximum point on curve (see below picture)

 

[Sourabh N]

Think a bit. Try drawing lines x + y = c for different values of c.

 

[temp]

do you read my first post carefully?

one approach is finding all distance between "start point","any point on curve","end point"

and then choosing then maximum distance between them.
but this approach get much time when implementing on computer

do your mean is such mine?

 

[Sourabh N]

I didn't clearly understand what you are saying :(

But I was trying to tell you that at max point the slope of curve is -1.
Hope this helps.

 

[HallsofIvy]

I don't think temp made it very clear what he was asking for- in particular he never said what he meant by "peak" point. I too thought he meant "maximum y" but then he started talking about finding the maximum distance along the curve from some starting point. I can't connect that with any reasonable concept of "peak".

Oh, and I'm sure you meant to say, "at max point the slope of curve is 0", not 1!

 

[Sourabh N]

Actually, by max point I meant what temp was referring to as max point (the "?" in the figure). This max point is the point farthest from origin, lying on the curve, I suppose.

 

[temp]

Actually, by max point I meant what temp was referring to as max point (the "?" in the figure). This max point is the point farthest from origin, lying on the curve, I suppose.

that's true
i marked "?" in my attached image to tell you what i need.

 

[Sourabh N]

So did you get my idea (at "?" slope is -1)

 

[hotvette]

Yeah, I thought peak meant maximum y. If it really means the distance to the curve from some reference point (x₀, y₀), then it seems to me the problem boils down to solving a cubic equation.

$$d^2 = (x - x_0)^2 + (y - y_0)^2$$

Since x and y are quadratic in t, d² is a 4th order equation in t. Taking the derivative and setting equal to zero involves solving a cubic equation, which can be done analytically or numerically. Or, am I not understanding something?

 

[Sourabh N]

You are absolutely correct. A bit of manipulation will end you up the same thing I was telling (slope = -1).

 

[temp]

ok
but my mean is not finding slope at "?"
My Mean Is Finding Position Of "?" Point!
there are other sample:

http://www.hostdump.com/uploads/cb2d22775c.jpg

 

[hotvette]

You are absolutely correct. A bit of manipulation will end you up the same thing I was telling (slope = -1).

I disagree, unless I'm totally not understanding what is going on. Look at this simple example: http://www.hostdump.com/uploads/212436219e.jpg

The maximum distance from (x₀, y₀) to the curve is a vertical line - the slope of the curve is zero,
not -1. It is problem dependent. Certainly there are specific problems where it is true, but not in general.

temp,

What said before I believe is correct. Write the expression for distance from the reference point to the curve, take the derivative with respect to t, set = zero, and solve (the resulting cubic equation) for t. In the case of the specific posted example, t = 0.5, which means x = 0, y = -1.

$$d^2 = (x-x_0)^2 + (y-y_0)^2$$

$$d(d^2)/dt = 0 = 2(x-x_0)x'+ 2(y-y_0)y' = (x-x_0)x'+ (y-y_0)y'$$

$$0 = (a_xt^2+ b_xt + c_x - x_0)(2a_xt + b_x) + (a_yt^2+ b_yt + c_y - y_0)(2a_yt + by)$$

$$0=2t^3(a_x^2+a_y^2)+3t^2(a_xb_x+a_yb_y)+t(2a_xc_x-2a_xx_0+b_x^2+2a_yc_y-2a_yy_0+b_y^2)+b_xc_x-b_xx_0+b_yc_y-b_yy_0$$

For the specific problem posted, the cubic to be solved is:

$$0 = 32t^3 - 48t^2 + 12t + 2$$

The 3 solutions are:

$$t = (-0.112, 0.5, 1.112)$$

There is only 1 value of t within the desired range of t=0,1 and that's t = 0.5, which is the point of maximum distance from (x₀, y₀). The other 2 values of t represent minimum distance.

Like I said before, the key to this problem is solving a cubic equation - that can be done analytically or numerically. Here is a more complicated example: http://www.hostdump.com/uploads/2c1856190f.jpg