Math Question!

BlitzMax Forums/BlitzMax Programming/Math Question!

BLaBZ(Posted 2015) [#1]
Here's a math question for those who are equipped!

I'm using the linked equation to calculate the points at which a line intersects an ellipse.

http://mathworld.wolfram.com/Ellipse-LineIntersection.html

What I'm trying to figure out is how to change the origin of the line.


PhotonTom(Posted 2015) [#2]
I'll try to give you an answer and explain it but it is not as easy as you might think. You also need to do some extra checks as sometimes the line won't ever intersect

In the working on the link you gave they use y=(y0 / x0)x, this is an equation for a line going through the origin and (x0,y0). This will always intersect the circle in two places!
If we replace this with equation y=mx+n then we can describe any straight line we want using different values of m and n. (You can also get values for m and n from two points (x1,y1), (x2,y2) that a straight line passes through but I won't explain how unless you need it)

So we then use the same method they did to calculate their formula: substitute our equation for y into our formula for an ellipse: x^2/a^2 + y^2/b^2 = 1 and then solve for x using the quadratic formula and we get some results for x. We do similar to get the y coordinates. Its a long and tedious method and can lead to many mistakes so I cheated and got wolfram to calculate it for me:
[a http://www.wolframalpha.com/input/?i=x^2%2Fa^2%2By^2%2Fb^2%3D1%2Cy%3Dmx%2Bn]https://www.wolframalpha.com/input/?i=x^2%2Fa^2%2By^2%2Fb^2%3D1%2Cy%3Dmx%2Bn[/a]

The solutions section is all you need to worry about on that page and only the first two boxes are important for your problem. The last two boxes are not important under this situation. Your first two boxes provide your two x and y coordinates of intersecting points. Note if a^2*m^2+b^2=0 then the line doesn't touch the circle and if both solutions are the same then the line only touches the ellipse once.


BLaBZ(Posted 2015) [#3]
First of all, holy crap, I've never heard of Wolfram Alpha but that engine is freaking incredible.

That equation becomes quite a monster with that seemingly minor change. Thank you for you help!

Do you know of any other helpful math tools like Wolfram Alpha, or websites\references that you find useful regarding computational mathematics or algorithms?


Floyd(Posted 2015) [#4]
The reason that original Wolfram formulation was so simple is the total symmetry: a circle and a line through the center. That meant finding only one solution. If you found a point of intersection then you immediately knew the other, which was the reflection through the center.

Translating so the center is at (0,0) is an obvious simplification, translating back after finding the solution.

Likewise, you can recapture some of the symmetry by transforming the ellipse to a circle. If the ellipse was, say, x^2/4 + y^2/9 = 1 then you could substitute 2*u = x and 3*v = y. The ellipse becomes the unit circle u^2 + v^2 = 1. Make the same substitution for the line. The problem is now unit circle versus line. This is conceptually the same as the original, but much less fiddly in practice. For example, when I put the original problem into Wolfram Alpha I get a "standard time limit exceeded" message. With a unit circle I do not. Anyway, you solve this for intersection points (u,v). Then substitute back u = x/2 and v = y/3 to get the answer to the original problem.

There is still work to do for a really general solution: there can be zero, one or two points of intersection, the line might be vertical ( can't solve for y ). The latter problem could also be handled with a simple transformation: swap x and y, solve, swap back.


Floyd(Posted 2015) [#5]
Here's a promising looking Code Archive entry.


BLaBZ(Posted 2015) [#6]
This is fun, I decided to take it to the next level and find the x,y,z intersection points of an ellipsoid while adjusting the origin on the y access. The equation is quite crazy!

[a http://www.wolframalpha.com/input/?i=x%5E2%2Fa%5E2%2By%5E2%2Fb%5E2%2Bz%5E2%2Fc%5E2%3D1%2Cy%3Dmx%2Bn%2C+z%3Dtx]http://www.wolframalpha.com/input/?i=x%5E2%2Fa%5E2%2By%5E2%2Fb%5E2%2Bz%5E2%2Fc%5E2%3D1%2Cy%3Dmx%2Bn%2C+z%3Dtx[/a]


PhotonTom(Posted 2015) [#7]
Translating so the center is at (0,0) is an obvious simplification, translating back after finding the solution.

This only works if the line goes through the centre point of the ellipse though :(

Also Blitz forums really doesn't like the wolfram links :D


Floyd(Posted 2015) [#8]
At some point the forums restricted links in an attempt to reduce hacking.

TinyURL version of Circle-Line Wolfram Alpha