Bit of geometry doing my head in
I have a 2D rectangle of known dimensions, its sides are parallel to the X and Y axes.
I'm trying to find an algorithm which will take the rectangle width and height and return the two axes of the ellipse with the lowest area which will intersect the rectangle's corners.
I'm going a tad nuts as the best I can get is an algorithm which returns a perfect circle, and that isn't what I want!
Any ideas/solutions?
I'm trying to find an algorithm which will take the rectangle width and height and return the two axes of the ellipse with the lowest area which will intersect the rectangle's corners.
I'm going a tad nuts as the best I can get is an algorithm which returns a perfect circle, and that isn't what I want!
Any ideas/solutions?
Post edited by NickH on
Comments
Assuming you mean that the box should be completely inside the ellipse then I think the answer is pretty trivial.
For a square box the answer is obviously a circle with radius=sqrt((size*size)*2). So, I think for an ellipse an easy way to get the answer is to imagine the whole thing scaled back down to a square. So, given a box of width w and height h, first scale everything so that h=w (h_scale=h/w). Now calculate the radius of the circle (r=sqrt((w*w)*2)). Then scale back up to a rectangle, so the X radius of the ellipse is still xr=r, and the Y radius is yr=r*h_scale.
I might be wrong, but that works in my mind ;)
circles are easy anything with an ellipse in counts as Hard Maffs? in my book :smile:
That could do the trick... will try it tomorrow...
I think it's a little more complicated than that. from what I understand you are assuming that this is the minimal area.
There has been a paper written on this :-
http://www.springerlink.com/content/cu82682877416147/
But it's far too late to look at.
Damn. That's a good solution. It only works in the rectangle case though... Having said that, my props to you! Transforming the space prior to making the calculation was an inspired idea...
And here was me scribbling through page after page of differential equations. It's actually a very very tough problem in the general case of n-points. The easiest way to solve it computationally is with incremental tweaks...
Incidentally Nick, when you apply the above solution, I suggest you jitter a and b to vary by five percent to see if you can get a better solution. I think that just scaling the square will give you a great approximation, but as you're looking for the minimum of an area curve, a quick iterative search left and right will let you determine whether you're at the minimum already or whether you can tweak it further.
Yeah, but that's solves the general case for an arbitrary number of points. The fact he's looking at four highly constrained points makes it a lot easier.
Andrew
Start with the definition of an ellipse (the sum of the distances from each focus to any point X on the ellipse is constant).
Use Pythagoras's Theorem to write down an expression for the square of this distance.
Rescale the problem, by fixing one of your three variables to be equal to 1.
Then use the Calculus of Variations.
http://mathworld.wolfram.com/Ellipse.html
http://mathworld.wolfram.com/CalculusofVariations.html
That's about as much as I can write using plain text. If you like, I'll write a solution in LaTeX, and send you a PDF somehow.
I think you might need calculus to solve this, and thats about where my mostly self-taught maths ends ;). I think its not that hard though. Probably you can solve it by plugging the tangent at the corner (which you know, since its just the vector perpendicular to the vector pointing towards the corner of the box) and the corner point into the equation for tangent to an ellipse and solving for one of the axes (with the other axis equal to the first times a scaling factor or something).
I'm sure there is a simple geometric solution to this though - in my experience many problems that mathematicians will solve with a page full of calculus can be solved by plebs like me using geometric construction ;)
I wouldn't say that it's completely wrong... I think it would be a great first order approximation. Then - as it's a computationally cheap thing to do at this point - sliding down the area curve to reach the minima would find the optimum solution pretty quickly. It's convenient that the points to enclose are constrained as a rectangle.
The iterative approach is - I think the best way to "solve" it on a computer. The calculus does get a little hairy.
Andrew
If you're working with an ellipse, you're dealing with the sum of the distances from the two foci, which you can't calculate by adding the two squares. It isn't too hard for a computer to calculate square roots and find a solution by numerical iteration, but all those square root signs make it extremely difficult to simplify an algebraic solution into something that's usable.
A better method goes something like this:
If you want to find the minimum value of Y, look for points where (dY/dx) is zero.
If you only know Y? (Y squared), and it's too difficult to work out Y, then just look for zero values of (d Y?/dx), which equals 2Y (dY/dx). If you have a quick way of showing that Y is never zero, then you've solved the problem.
There's no point even trying to decipher the terse descriptions of mathematical techniques that are on various web sites. Once I've dug out my lecture notes from way back when, I'll write a description the method and solution in layman's terms.
- IONIAN-GAMES.com -
No, no, no - like Andrew said, it's a good approximation. I've just used it as a starting point and then, if the corners of the rectangle are outside the described ellipse, I keep expanding the two axes by 1%. That gives me a nice-looking ellipse.
Thankyou :)
- IONIAN-GAMES.com -
Heh, I was assuming finding the minimum area'd ellipse was trivial, and that it would give me a nice-looking ellipse. Now that I've seen just how tricky it is to calculate that, I'm happy to go with this for now :)
Bit of a tease, but early days yet...
That's actually probably the most 'aesthetically pleasing' ellipse... and as I said, if you wanted to actually check, you could jiggle a and b incrementally by 5% either way and see whether the area was at the minima.
Andrew
- IONIAN-GAMES.com -
All will become clear.
Maybe this year.
Maybe.
Go visit NickH's links (in his sig) ... I think one of them kinda sorta maybe explains what he's up to.