# Intersection of bezier and straight line

Show 40 post(s) from this thread on one page
Page 1 of 2 1 2 Last
• 05-18-2007, 08:30 AM
Application Development
Intersection of bezier and straight line
Hi all,
I was wondering, how do we determine the a value 'Y' on a bezier when
you know the value of X coordinate.
ie. for X = (say) 10.0 , how do we find corrosponding Y value.
This problem reduces to finding intersection of line X=10 with the
given bezier.

Also I was wondering if it is possible to achive this using Dave
Eberly's Wild Magic library.

Regards
Yogesh

• 05-18-2007, 01:01 PM
Application Development
Re: Intersection of bezier and straight line
Hi,
I have two ideas, one is simple and stupid, the other is quite
complicated, but should be more efficient, let's see if there is
something interesting for you:
1. simple sampling
sample a Bezier curve by evaluating a parametric form of the Bezier
curve at equidistant discreet parameter values, check each sample if
it is close to x-value which are you lookign for, if necessary
adaptively increase the sampling rate, also note that there can be
several values of Y for one X
2. Bezier clipping
unfortunatelly I don't have any references here, but if you google
"Bezier clipping" you will find something for sure, it is a recursive
numerical approach which uses some nice properties of Bezier curves
(variation dimnishing property, convex hull) and it is said to be
quite stable, it has been used in the area of raytracing Bezier
patches quite extensively

jindra

On May 18, 3:30 pm, yogesh.k...@gmail.com wrote:
> Hi all,
> I was wondering, how do we determine the a value 'Y' on a bezier when
> you know the value of X coordinate.
> ie. for X = (say) 10.0 , how do we find corrosponding Y value.
> This problem reduces to finding intersection of line X=10 with the
> given bezier.
>
> Also I was wondering if it is possible to achive this using Dave
> Eberly's Wild Magic library.
>
> Regards
> Yogesh

• 05-19-2007, 01:02 AM
Application Development
Re: Intersection of bezier and straight line
jindra wrote:
> I have two ideas, one is simple and stupid, the other is quite
> complicated, but should be more efficient, let's see if there is
> something interesting for you:
> 1. simple sampling
> sample a Bezier curve by evaluating a parametric form of the Bezier
> curve at equidistant discreet parameter values, check each sample if
> it is close to x-value which are you lookign for, if necessary
> adaptively increase the sampling rate, also note that there can be
> several values of Y for one X

This is basically a generic naive root-finding algorithm. There are
plenty of _good_ generic root-finding algorithms that one can find with
a little bit of searching, which will be a lot faster and not much more
complex. :)

For that matter, for a given spline segment X is cubic in T, and cubic
polynomials can be inverted directly, so there's no need for an
iterative method anyway. So you solve for T, and then plug that into
the equation for Y.

- Brooks

--
The "bmoses-nospam" address is valid; no unmunging needed.
• 05-19-2007, 01:31 AM
Application Development
Re: Intersection of bezier and straight line
> I was wondering, how do we determine the a value 'Y' on a bezier when
> you know the value of X coordinate.

Solve roots t for polynomial x(t) = given x. Closed form solution for

Plug t's into y(t).

Mind the degenerate cases. You can have 1, 2, 3 or infinite solutions.
• 05-19-2007, 02:02 AM
Application Development
Re: Intersection of bezier and straight line
<yogesh.kini@gmail.com> wrote in message
> I was wondering, how do we determine the a value 'Y' on a bezier when
> you know the value of X coordinate.
> ie. for X = (say) 10.0 , how do we find corrosponding Y value.
> This problem reduces to finding intersection of line X=10 with the
> given bezier.

If the curve is (x(t),y(t)) and the vertical line is x = x0, you need
to compute the roots to the polynomial p(t) = x(t) - x0. For each
root T, compute the y-value y(T).

As mentioned by another poster, if the curve is degree 3, then you
could use the closed-form equations for the roots to a cubic. Be
aware, though, that those equations are notoriously ill-conditioned
when you have two roots that are nearly the same.

> Also I was wondering if it is possible to achive this using Dave
> Eberly's Wild Magic library.

By example:

int Generic::Main (int, char**)
{
// The Bezier curve is
// (x(t),y(t)) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
// for 0 <= t <= 1.
const int iDegree = 3;
Vector2d* akCtrlPoint = WM4_NEW Vector2d[iDegree + 1];
akCtrlPoint[0] = Vector2d( 0.0,0.0);
akCtrlPoint[1] = Vector2d( 3.0,1.0);
akCtrlPoint[2] = Vector2d(-1.0,2.0);
akCtrlPoint[3] = Vector2d( 4.0,4.0);
BezierCurve2d kCurve(iDegree, akCtrlPoint);

// The polynomial x(t).
Polynomial1d kXPoly(iDegree);
kXPoly[0] = kCurve.GetPosition(0.0)[0];
kXPoly[1] = kCurve.GetFirstDerivative(0.0)[0];
kXPoly[2] = kCurve.GetSecondDerivative(0.0)[0]/2.0;
kXPoly[3] = kCurve.GetThirdDerivative(0.0)[0]/6.0;

// The vertical line x = x0.
double dX0 = 1.26;

// Solve for x(t) = x0.
kXPoly[0] -= dX0;
int iDigits = 8;
PolynomialRootsd kPR(Mathd::ZERO_TOLERANCE);
kPR.FindB(kXPoly,iDigits);

// I have chosen the curve and an x0 so that the vertical line
// intersects the curve 3 times.
int iCount = kPR.GetCount();
// root[0] = 0.33563439076802315
// root[1] = 0.42569287040671300
// root[2] = 0.55117273179554338

// y0 = 1.0447125355351101
// y1 = 1.3542202977928879
// y2 = 1.8209597203487196

return 0;
}

--
Dave Eberly
http://www.geometrictools.com

• 05-20-2007, 11:32 PM
Application Development
Re: Intersection of bezier and straight line
Hi all,
Thanks for all the replies.
Also Many Many Thanks to Dave for creating such a great open source
library(Wild Magic).
Wild Magic is truely awesome and seems to have all the math you will
ever need :-)

Best Regards
Yogesh

• 05-21-2007, 12:15 AM
Application Development
Re: Intersection of bezier and straight line
On May 19, 12:02 pm, "Dave Eberly" <dNOSPAMebe...@usemydomain.com>
wrote:
> <yogesh.k...@gmail.com> wrote in message
>
>
> > I was wondering, how do we determine the a value 'Y' on a bezier when
> > you know the value of X coordinate.
> > ie. for X = (say) 10.0 , how do we find corrosponding Y value.
> > This problem reduces to finding intersection of line X=10 with the
> > given bezier.

>
> If the curve is (x(t),y(t)) and the vertical line is x = x0, you need
> to compute the roots to the polynomial p(t) = x(t) - x0. For each
> root T, compute the y-value y(T).
>
> As mentioned by another poster, if the curve is degree 3, then you
> could use the closed-form equations for the roots to a cubic. Be
> aware, though, that those equations are notoriously ill-conditioned
> when you have two roots that are nearly the same.
>
> > Also I was wondering if it is possible to achive this using Dave
> > Eberly's Wild Magic library.

>
> By example:
>
> int Generic::Main (int, char**)
> {
> // The Bezier curve is
> // (x(t),y(t)) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
> // for 0 <= t <= 1.
> const int iDegree = 3;
> Vector2d* akCtrlPoint = WM4_NEW Vector2d[iDegree + 1];
> akCtrlPoint[0] = Vector2d( 0.0,0.0);
> akCtrlPoint[1] = Vector2d( 3.0,1.0);
> akCtrlPoint[2] = Vector2d(-1.0,2.0);
> akCtrlPoint[3] = Vector2d( 4.0,4.0);
> BezierCurve2d kCurve(iDegree, akCtrlPoint);
>
> // The polynomial x(t).
> Polynomial1d kXPoly(iDegree);
> kXPoly[0] = kCurve.GetPosition(0.0)[0];
> kXPoly[1] = kCurve.GetFirstDerivative(0.0)[0];
> kXPoly[2] = kCurve.GetSecondDerivative(0.0)[0]/2.0;
> kXPoly[3] = kCurve.GetThirdDerivative(0.0)[0]/6.0;
>
> // The vertical line x = x0.
> double dX0 = 1.26;
>
> // Solve for x(t) = x0.
> kXPoly[0] -= dX0;
> int iDigits = 8;
> PolynomialRootsd kPR(Mathd::ZERO_TOLERANCE);
> kPR.FindB(kXPoly,iDigits);
>
> // I have chosen the curve and an x0 so that the vertical line
> // intersects the curve 3 times.
> int iCount = kPR.GetCount();
> const double* adRoot = kPR.GetRoots();
> // root[0] = 0.33563439076802315
> // root[1] = 0.42569287040671300
> // root[2] = 0.55117273179554338
>
> // y0 = 1.0447125355351101
> // y1 = 1.3542202977928879
> // y2 = 1.8209597203487196
>
> return 0;
>
> }
>
> --
> Dave Eberlyhttp://www.geometrictools.com

Hi Dave,

Am very very impressed by looking at this post.I am very much
intersted in the way you would actually be finding the intersection
points of a bezier and a straight line.I would love to know how the
polynomial equation is created using the bezier contol points and then
how are the roots actually calculated using the 1st,2nd and third
derivatives of the polynomial.Could you give me a little insight into
this

Thanks and Regards
Praveen

• 05-21-2007, 12:59 AM
Application Development
Re: Intersection of bezier and straight line
<praveenk.dj@gmail.com> wrote in message

> I am very much intersted in the way you would actually be finding
> the intersection points of a bezier and a straight line.

The source code I posted is the way I find the intersection
points of a Bézier curve and a vertical line, so I do not understand
intersection of the curve with an arbitrary line?

> I would love to know how the polynomial equation is created
> using the bezier contol points and then how are the roots
> actually calculated using the 1st,2nd and third derivatives
> of the polynomial.

The Bézier curve I mentioned is
P(t) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
where P0, P1, P2, and P3 are the user-specified control points, and
where 0 <= t <= 1. In standard form, the polynomial is
P(t) = C0 + t*C1 + t^2*C2 + t^3*C3
The first three derivatives are
P'(t) = C1 + 2*t*C2 + 3*t^2*C3
P''(t) = 2*C2 + 6*t*C3
P'''(t) = 6*C3
Notice that C0 = P(0), C1 = P'(0), C2 = P''(0)/2, and C3 = P'''(0)/6,
which is what I computed in the sample code.

Equivalently, I could have expanded the Bézier form for P(t) as
P(t) = P0 + t*(-3*P0+3*P1) + t^2*(3*P0-6*P1+3*P2)
+ t^3*(-P0+3*P1-3*P2+P3)
to obtain C0, C1, C2, and C3.

--
Dave Eberly
http://www.geometrictools.com

• 05-21-2007, 01:23 AM
Application Development
Re: Intersection of bezier and straight line
On May 21, 10:59 am, "Dave Eberly" <dNOSPAMebe...@usemydomain.com>
wrote:
> <praveenk...@gmail.com> wrote in message
>
>
> > I am very much intersted in the way you would actually be finding
> > the intersection points of a bezier and a straight line.

>
> The source code I posted is the way I find the intersection
> points of a Bézier curve and a vertical line, so I do not understand
> intersection of the curve with an arbitrary line?
>
> > I would love to know how the polynomial equation is created
> > using the bezier contol points and then how are the roots
> > actually calculated using the 1st,2nd and third derivatives
> > of the polynomial.

>
> The Bézier curve I mentioned is
> P(t) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
> where P0, P1, P2, and P3 are the user-specified control points, and
> where 0 <= t <= 1. In standard form, the polynomial is
> P(t) = C0 + t*C1 + t^2*C2 + t^3*C3
> The first three derivatives are
> P'(t) = C1 + 2*t*C2 + 3*t^2*C3
> P''(t) = 2*C2 + 6*t*C3
> P'''(t) = 6*C3
> Notice that C0 = P(0), C1 = P'(0), C2 = P''(0)/2, and C3 = P'''(0)/6,
> which is what I computed in the sample code.
>
> Equivalently, I could have expanded the Bézier form for P(t) as
> P(t) = P0 + t*(-3*P0+3*P1) + t^2*(3*P0-6*P1+3*P2)
> + t^3*(-P0+3*P1-3*P2+P3)
> to obtain C0, C1, C2, and C3.
>
> --
> Dave Eberlyhttp://www.geometrictools.com

Hi Dave,

Thanks for explaining the way u have calculated the coefficients using
the derivatives.I am very new to cubic curves and it was really

Thanks and Regards
Praveen

Thanks and Regards
Praveen

• 05-21-2007, 02:25 AM
Application Development
Re: Intersection of bezier and straight line
On May 21, 10:59 am, "Dave Eberly" <dNOSPAMebe...@usemydomain.com>
wrote:
> <praveenk...@gmail.com> wrote in message
>
>
> > I am very much intersted in the way you would actually be finding
> > the intersection points of a bezier and a straight line.

>
> The source code I posted is the way I find the intersection
> points of a Bézier curve and a vertical line, so I do not understand
> intersection of the curve with an arbitrary line?
>
> > I would love to know how the polynomial equation is created
> > using the bezier contol points and then how are the roots
> > actually calculated using the 1st,2nd and third derivatives
> > of the polynomial.

>
> The Bézier curve I mentioned is
> P(t) = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3
> where P0, P1, P2, and P3 are the user-specified control points, and
> where 0 <= t <= 1. In standard form, the polynomial is
> P(t) = C0 + t*C1 + t^2*C2 + t^3*C3
> The first three derivatives are
> P'(t) = C1 + 2*t*C2 + 3*t^2*C3
> P''(t) = 2*C2 + 6*t*C3
> P'''(t) = 6*C3
> Notice that C0 = P(0), C1 = P'(0), C2 = P''(0)/2, and C3 = P'''(0)/6,
> which is what I computed in the sample code.
>
> Equivalently, I could have expanded the Bézier form for P(t) as
> P(t) = P0 + t*(-3*P0+3*P1) + t^2*(3*P0-6*P1+3*P2)
> + t^3*(-P0+3*P1-3*P2+P3)
> to obtain C0, C1, C2, and C3.
>
> --
> Dave Eberlyhttp://www.geometrictools.com

Hi Dave,

Yes,I am actually interested to know how the intersection points of a
cubic curve with any generic straight line is calculated.Could you
please explain me that as well

Thanks and Regards
Praveen

Show 40 post(s) from this thread on one page
Page 1 of 2 1 2 Last