Approximating Curves: Finding Intersections

[hamsterman]

I need to deal with some curves. Nothing too fancy and nothing precise. I really need a line, something that looks like a parabola. A circle and something similar to Bézier curves would be very nice. I'm working in two dimensions, real numbers only.

What I have right now is a vector of two polynomials (P1(t), P2(t)). Note that some of my curves need to be functions of time (trajectories), while others can have any form (surfaces). I'm happy with curves available to me, but I have a problem. I need approximate t of intersections of the curves. To solve a system of polynomials seems rather challenging if I restrict myself to lines and parabolas. I won't be able to do even that for higher polynomials. I assume I should be able to approximate the t of intersection somehow, but I'm not much familiar with how that is done.

I was hoping there was another way to write simple curves that would make finding intersections more simple. Although I can't think of anything myself.

Thanks for your time.

 

[chiro]

I need to deal with some curves. Nothing too fancy and nothing precise. I really need a line, something that looks like a parabola. A circle and something similar to Bézier curves would be very nice. I'm working in two dimensions, real numbers only.

What I have right now is a vector of two polynomials (P1(t), P2(t)). Note that some of my curves need to be functions of time (trajectories), while others can have any form (surfaces). I'm happy with curves available to me, but I have a problem. I need approximate t of intersections of the curves. To solve a system of polynomials seems rather challenging if I restrict myself to lines and parabolas. I won't be able to do even that for higher polynomials. I assume I should be able to approximate the t of intersection somehow, but I'm not much familiar with how that is done.

I was hoping there was another way to write simple curves that would make finding intersections more simple. Although I can't think of anything myself.

Thanks for your time.

Hey hamsterman and welcome to the forums.

For your curves do you have a parametrization for x and y in terms of t? (Is that your P1(t), P2(t)), and for your surface you have x, y, and z parameterized (P1(t,u), P2(t,u), P3(t,u))?

The way I see you doing this is to solve two sets of simultaneous equations.

The first set will find the intersection of the line with your curve/surface in terms of x, y, and z. From this you will have a value for x,y or x,y,z depending on your object.

Then using this you have two or three equations in terms of t which you can substitute into one another to get an answer for t.

In terms of the specifics, one would need to know the type of formulas used for the curves and surfaces (I'm guessing they are cubic approximating Bezier-family curves/surfaces), and from this you can use a bit of math to solve the first set of equations and then the second.

 

[hamsterman]

Yes, currently all of my curves are defined by polynomials of a parameter t. x and y separately.
I suppose I misused the word surface. I meant a curve that is not logically a function of time. One could, for example, be defined as x²+y=0 (I'm not sure how such form is called).

I know that normally I'd have to solve a system of equations, but it's not easy for polynomial of high degree, I don't need much precision and I don't have much time (this task is for a program I'm writing).
Is there any method to approximate the solution of a system of equations?

The types of curves to use is what I am trying to choose. Surely there should be more ways to write simple curves than just using polynomials. I don't know if any of them will be easier to solve though.

 

[chiro]

The standard Bezier curve is a cubic polynomial which means you can get an exact solution.

Since you said that an approximation is enough, its probably easier to just use a root finding algorithm. There are plenty of implementations for root finding algorithms that you can download for free.

In terms of more general curves, you should look at B-SPLINES and NURBS. They are a lot more general, but they offer more power (for example they can accurately model an arc of a circle or sphere).

The thing is that if you are trying to interpolate (or approximate) a set of points where the number of points is finite, then you will end up with a polynomial using standard methods.

The only other suggestion I can give is to use an integral transform of some sort. These kind of transforms allow you to use transcendental functions like sines and cosines if you want to decompose a function on a finite interval into sines and cosines. This decomposition will allow you to control frequency information if you wanted to.

But yeah for your problem, if you don't want to work out the finer details, just use a root finding algorithm twice: one for finding initial (x,y) and secondly for finding t.

Have you ever used or are familiar with a root finding algorithm?

 

[hamsterman]

I have written Durand–Kerner method to solve a single polynomial equation before, but I still don't see how that could work for a system. The second step is clear. For the first one, I'd need a different algorithm, I assume?
Another problem is that, at least this algorithm finds complex roots, while I need real ones only. Due to imprecision it may be unclear whether the imaginary part exists or not. I'm not sure how much of a problem this is. Would a small imaginary part always imply that the distance between the curves is small?

 

[chiro]

I have written Durand–Kerner method to solve a single polynomial equation before, but I still don't see how that could work for a system. The second step is clear. For the first one, I'd need a different algorithm, I assume?
Another problem is that, at least this algorithm finds complex roots, while I need real ones only. Due to imprecision it may be unclear whether the imaginary part exists or not. I'm not sure how much of a problem this is. Would a small imaginary part always imply that the distance between the curves is small?

For the 2D case (x,y) you can solve for t instantly (I should have realized this, but anyway here we go).

Consider a line in two dimensions. You can parametrize the line in terms of t given x(t) and y(t). You can also do the same for the polynomial where a(t) = t and b(t) represents the y coordinate of the curve.

Now all you have to do is equate these things together (in other words a(t) = x(t) and b(t) = y(t)). Using those, expand out the definitions, substitute one equation into the other and solve for t.

If the equation ends up being greater than a quartic, use a root finding algorithm. If not, use a standard analytic solver which will give you an answer that is quick to compute and accurate.

This will work easily for the 2D form but the 3D form is a bit harder since you have a two dimensional parametrization.

 

[hamsterman]

Why is it just t?
The way I have it is
x₁(t) = x₂(u)
y₁(t) = y₂(u)
where x₁, x₂, y₁, y₂ are polynomials.
It seems to me that you can only substitute u with a function of t in trivial cases. Or maybe it can be done in all cases, but you need to know the roots already..

 

[chiro]

Why is it just t?
The way I have it is
x₁(t) = x₂(u)
y₁(t) = y₂(u)
where x₁, x₂, y₁, y₂ are polynomials.
It seems to me that you can only substitute u with a function of t in trivial cases. Or maybe it can be done in all cases, but you need to know the roots already..

The t will correspond to the appropriate x coordinate and the other functions will be in terms of that. If you need to add a constant or scale some function then adjust for that, but otherwise just use the same unit and scale for your x.

Thats the key here: since you can express a line (with any offset) and a curve in terms of the same x unit, this will be the way you end up with a simultaneous equation.

 

[hamsterman]

I may be misunderstanding, but keeping one of the two functions for every curve linear is a bit too much of a restriction for me.

Edit:
when phrased as "finding intersections of Bezeir curves" this problem seems to be quite common. I'm currently looking at a pdf on this

Also, when one curve is (x(t), y(t)) and another is f(x, y) = 0, the intersections are quite obviously easy to find. I didn't think about that at all. I'm not sure what curves can be written as f(x, y) = 0 though (apart from conic sections).

 

[chiro]

Also, when one curve is (x(t), y(t)) and another is f(x, y) = 0, the intersections are quite obviously easy to find. I didn't think about that at all. I'm not sure what curves can be written as f(x, y) = 0 though (apart from conic sections).

Anything can be written in the f(x,y) = 0 form. It doesn't necessarily have to be implicit: you can write things where the different variables are seperable.

The example in the PDF you linked to for a line written in f(x,y) = 0 form is basically ax + by + c = f(x,y) = 0. In this case, the x and y variables are seperable which is why you can write y in terms of x, but for many functions this is not the case.

 

[hamsterman]

Again, parametric curves that have at least one linear component are trivial examples. Is it possible to write any Bezier curve as f(x, y) = 0?

 

[chiro]

Again, parametric curves that have at least one linear component are trivial examples. Is it possible to write any Bezier curve as f(x, y) = 0?

Oh sorry dude, you were talking about the bezier curves and not the linear one.

The way you do it with the bezier is pretty much the same as with the linear, but yeah depending on the curve it can be more complicated as you have pointed out.

Just for clarity, post the general expression of the curve you are using and I will attempt to turn it into an implicit function in the form f(x,y) = 0.

Basically all I am going to do is find a relationship between x and y and then balance the equation. This is the basic idea employed to do this. There are other methods that can be used that involve derivatives, but we will try this one first.

 

[hamsterman]

General expression is just two polynomials. Let's say
x(t) = at³ + bt² + ct + d
y(t) = pt³ + qt² + rt + s

So, as I understand, there is no general way to convert a parametric function to an implicit one?

 

[chiro]

General expression is just two polynomials. Let's say
x(t) = at³ + bt² + ct + d
y(t) = pt³ + qt² + rt + s

So, as I understand, there is no general way to convert a parametric function to an implicit one?

What you might be able to do is to use derivatives to do this.

If you can figure out dy/dx from dx/dt and dy/dt then you can figure out y in terms of x and balance the equation.

Since you have x(t) why don't you use implicit differentiation to find dt/dx and collect terms to get the right expression. From this you should be able to figure out dy/dx using the chain rule, and the use a taylor series expansion centred around t = 0 to give you an equation.

How does that sound?

 

[hamsterman]

That sounds like a lot of work.. My calculus isn't great. Though that's not important. It seems to me that what I have now (polynomials for trajectories and implicit conic sections and lines for static curves) is enough. Thanks for all the help.