Unsolved math problem! - defining the parameters of an ellipse...

gtoal

STOP PRESS! *** SOLVED *** !!!

Scratch user nXIII has solved this problem! The solution has been added to the Ellipse-drawing library at http://scratch.mit.edu/projects/50039326/

You can play with the algorithm interactively at this Javascript page: http://g6auc.me.uk/shear.html

*=====*=====*=====*=====*=====*=====*=====*=====*=====*=====*=====*=====*

This is a math/geometry problem which I came across almost 40 years ago that as far as I know hasn't been solved, or at least if it has, I can't find the solution on the net after a lot of searching. However it's not one of the impossibly hard problems, I just think no-one interested enough has ever tackled it. It would be great if a scratcher was the one to come up with the answer…

When drawing raster graphics on real hardware (ie not inside Scratch where the overhead of the language interpreter masks the underlying cost of the operations) it's important to use fast integer arithmetic to draw objects. There is a collection of algorithms by Bresenham from the 60's which use a practical application of a calculus technique to calculate function values incrementally, and Bresenham's algorithms for drawing lines, circles, ellipses etc are now used everywhere.

Bresenham's ellipse algorithm however just draws flattened or stretched circles, ie axis-aligned ellipses. It doesn't draw ellipses rotated to an arbitrary angle. To do that you currently have to generate the data for an axis-aligned ellipse and then rotate it using sin and cos on every point. On real graphics hardware this is relatively expensive.

One of my classmates at Edinburgh back in 1978 spotted that you could take advantage of the geometrical transformation where applying a shear to a circle turns it into a slanted ellipse. In terms of programming, if you have an implementation like Bresenhams, you simply add a value to either the x or y coordinate when you plot the pixels of a circle, and that gives you an ellipse. The value that is added is proportional to the other coordinate (eg the x coordinate if you are sliding columns of pixels vertically) and in fact can be specified by the equation of a line (dx and dy).

( If you haven't heard of the expression shear before in this context, check out the image http://www.pling.org.uk/cs/cgvimg/shearing.png at http://www.pling.org.uk/cs/cgv.html )

Since the equation of a line can also be calculated very cheaply using Bresenham's Line Drawing algorithm, you can add the circle algorithm and the line algorithm into the one piece of code and you get a very cheap way of generating non-axis-aligned ellipses using all integer code. Finally if you apply this technique to axis-aligned ellipses rather than circles, you get something that can generate any possible shape and size of ellipse.

But here's the problem… ellipses are usually defined by specifying their major and minor axes plus a rotation (or by specifying the two loci - there are several formulations that are effectively the same thing) - but the shear technique specifies ellipses by major and minor axes plus a shear component specified by a line equation.

It s not at all obvious how to take a specification in the traditional style and map the parameters to this alternative style in a way that you could call a procedure and draw an ellipse that is the same as one that would be drawn by the traditional but more expensive rotation-style algorithm.

If anyone can work out that mapping so that the only expensive operation is just the mapping of the parameters and then the ellipse is drawn by the cheap double-bresenham method, I think fame (although perhaps not fortune) awaits…

Here's a lab that allows you to define a rotated ellipse parametrically and then fit a sheared axis-aligned ellipse to it by eye: http://scratch.mit.edu/projects/50170934/

Can anyone find a way to map from one set of parameters to the other?

Good luck,

Graham
(PS I just realised that if you apply two shears - a positive one to X and a negative one to Y for example - you get something a lot more similar to a rotation, although it's still not an exact match because the scale will have changed. I don't know if this is helpful or not. But I'll add it to my list of tweaks to experiment with…)

Last edited by gtoal (March 4, 2015 18:33:21)

MegaApuTurkUltra

Interesting problem! I like interesting problems. I'll think about it and hope no one beats me to the answer! (if there is one)

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

Thepuzzlegame

I'll look into this as well! Although I doubt I'll be much help (aside from bumping up this topic

)

hi!

Hardmath123

You can get a rotation from a combination of shears and X/Y stretches. I'm pretty sure you should be thinking of this as a set of matrix transformations, where you start with the rotate-by-theta 2x2 matrix and decompose it into a series of stretches and shears (you'll end up with 4 matrices, corresponding to a shear and stretch along each axis). Shears are basically Bresenham's line algorithm and stretches are a scalar of that (cheap).

gtoal

Hardmath123 wrote:
You can get a rotation from a combination of shears and X/Y stretches. I'm pretty sure you should be thinking of this as a set of matrix transformations, where you start with the rotate-by-theta 2x2 matrix and decompose it into a series of stretches and shears (you'll end up with 4 matrices, corresponding to a shear and stretch along each axis). Shears are basically Bresenham's line algorithm and stretches are a scalar of that (cheap).

You're spot on. And I think I do need to implement two shears, one for each axis. That was probably what my classmate had originally done and I had forgotten that detail.

A stupid oversight on my part really, because I have used that exact technique elsewhere, in straightening scans of text a little before OCRing. It doesn't work so well for large angles but for small rotational corrections (maybe 5 degrees for example) it's a very good approximation to a rotation (because it doesn't scale the image significantly). True rotations of a large image are way more expensive in comparison. So basically the same trick.

G

MegaApuTurkUltra

Hardmath123 wrote:
You can get a rotation from a combination of shears and X/Y stretches. I'm pretty sure you should be thinking of this as a set of matrix transformations, where you start with the rotate-by-theta 2x2 matrix and decompose it into a series of stretches and shears (you'll end up with 4 matrices, corresponding to a shear and stretch along each axis). Shears are basically Bresenham's line algorithm and stretches are a scalar of that (cheap).

Good work! (Kinda unfair because it was like 10PM when I posted - I had to leave

)
I was looking into decomposing the rotation matrix into a set of shear matrices though and trying to implement it in gtoal's project though…

$(".box-head")[0].textContent = "committing AT crimes since $whenever"

gtoal

gtoal wrote:
I have used that exact technique elsewhere, in straightening scans of text a little before OCRing. It doesn't work so well for large angles but for small rotational corrections (maybe 5 degrees for example) it's a very good approximation to a rotation (because it doesn't scale the image significantly). True rotations of a large image are way more expensive in comparison. So basically the same trick.

There's a catch… in a framebuffer raster implementation you ideally want to do all the filling a line at a time (whether horizontal or vertical doesn't matter too much, although it can in some cases depending on the layout of the video ram).

So either horizontal or vertical shears *while filling* are cheap, because it's the same line you're drawing, only with a displacement of the starting position.

However to apply both horizontal *and* vertical shear, you can't continue to do the filling by axis-aligned lines. You either have to fill pixel by pixel or use sloping lines(*). Which defeats the point of this hack :-(

Now I remember why I only implemented a single shear in the primitive. So any solution that requires both an X and Y shear has to also include an efficient way to implement it…

G
(*: getting adjacent sloping lines to match up exactly opens a particular can of worms to do with rasterisation algorithms that we haven't ever touched on in Scratch, which is quite complex to explain and I wasn't planning to get into quite yet. The problem can be worked around by rasterizing the sloping line once and storing the y offsets in an array of length x, and using that as a lookup table for each line, but it's inelegant. I'll talk about the issues of consistency under translation/rotation/reflection in the context of pixel selection some other day. It's way too big a topic to add on to this discussion.)

Last edited by gtoal (March 1, 2015 15:53:47)

gtoal

MegaApuTurkUltra wrote:
Good work! (Kinda unfair because it was like 10PM when I posted - I had to leave )

Hey, it was 3am where I was and I had to sleep!

G

Hardmath123

gtoal wrote:
Now I remember why I only implemented a single shear in the primitive. So any solution that requires both an X and Y shear has to also include an efficient way to implement it…

I'm afraid that isn't going to happen, though, because any single shear would leave the transformation axis-aligned to one axis. So you'd end up with the problem that the rotation angle and eccentricity of the final shape will be correlated, which isn't what you want.

EDIT: Or is it? Perhaps by transforming an ellipse of some initial eccentricity $e$ by some matrix $M$ gives you a new, rotated ellipse whose eccentricity and angle are a function of M, e. Then you can probably reverse-engineer M and e.

(*: getting adjacent sloping lines to match up exactly opens a particular can of worms to do with rasterisation algorithms that we haven't ever touched on in Scratch, which is quite complex to explain and I wasn't planning to get into quite yet. The problem can be worked around by rasterizing the sloping line once and storing the y offsets in an array of length x, and using that as a lookup table for each line, but it's inelegant. I'll talk about the issues of consistency under translation/rotation/reflection in the context of pixel selection some other day. It's way too big a topic to add on to this discussion.)

Please, go ahead. I'm actually pretty interested in these things—I've considered writing a C-based SVG rasterizer (lovingly named “Piet”) many times, and this discussion might be just the motivation I need.

Last edited by Hardmath123 (March 1, 2015 16:10:00)

gtoal

Hardmath123 wrote:
gtoal wrote:
(*: getting adjacent sloping lines to match up exactly opens a particular can of worms to do with rasterisation algorithms that we haven't ever touched on in Scratch, which is quite complex to explain and I wasn't planning to get into quite yet. The problem can be worked around by rasterizing the sloping line once and storing the y offsets in an array of length x, and using that as a lookup table for each line, but it's inelegant. I'll talk about the issues of consistency under translation/rotation/reflection in the context of pixel selection some other day. It's way too big a topic to add on to this discussion.)

Please, go ahead. I'm actually pretty interested in these things—I've considered writing a C-based SVG rasterizer (lovingly named “Piet”) many times, and this discussion might be just the motivation I need.

When I've worked out the details I'll start a new thread. I'll need to prepare some images first too. May be a few days months.

If I can find the equivalent discussion online I'll post a link sooner but actually I haven't come across it yet. This was something that was discussed when I worked at Acorn Computers on the BBC Micro. Don't think I've seen anyone discuss it in print.

Teaser: have you heard the expression “Good, Cheap, Fast: you can pick any two but you can't have all three”? Well, the issue is like that concerning consistency of which pixels are set when drawing sloping lines: you can have consistency under any two of translation, reflection or rotation, but never all three.

G

Last edited by gtoal (Aug. 26, 2015 23:11:08)

gtoal

Hardmath123 wrote:
gtoal wrote:
Now I remember why I only implemented a single shear in the primitive. So any solution that requires both an X and Y shear has to also include an efficient way to implement it…

I'm afraid that isn't going to happen, though, because any single shear would leave the transformation axis-aligned to one axis. So you'd end up with the problem that the rotation angle and eccentricity of the final shape will be correlated, which isn't what you want.

EDIT: Or is it? Perhaps by transforming an ellipse of some initial eccentricity $e$ by some matrix $M$ gives you a new, rotated ellipse whose eccentricity and angle are a function of M, e. Then you can probably reverse-engineer M and e.

The trick is that there is a mapping of one ellipse to another ellipse like this, but what you are *not* doing is mapping a specific point on one ellipse to the corresponding point on the other ellipse. Take a wide axis-aligned ellipse, and the point that was leftmost (ie where the ellipse cut the major axis) - after applying a vertical shear, that point is still leftmost *but* it is no longer the place where the major axis intersects the ellipse! The outline of the ellipse has been shuffled clockwise a little. Matrix transformations are affine and map a point such as that to the expected point on the rotated ellipse, but these transformations don't work like that.

Upshot is you *can* make the ellipses match but you have to tweak the axis ratios etc to do it, in a very non-intuitive way.

I'll do another remix that has both methods and let you all fit one style to the other by tweaking the parameters with sliders. It may make understanding the problems a little more intuitive that way.

G

Last edited by gtoal (March 1, 2015 17:10:51)

Hardmath123

gtoal wrote:
The trick is that there is a mapping of one ellipse to another ellipse like this, but what you are *not* doing is mapping a specific point on one ellipse to the corresponding point on the other ellipse. Take a wide axis-aligned ellipse, and the point that was leftmost (ie where the ellipse cut the major axis) - after applying a vertical shear, that point is still leftmost *but* it is no longer the place where the major axis intersects the ellipse! The outline of the ellipse has been shuffled clockwise a little. Matrix transformations are affine and map a point such as that to the expected point on the rotated ellipse, but these transformations don't work like that.

Hmm, ok, so now I'm unconvinced that a shear of an ellipse is a different rotated/stretched ellipse. Is there an obvious proof for this?

gtoal

Hardmath123 wrote:
gtoal wrote:
The trick is that there is a mapping of one ellipse to another ellipse like this, but what you are *not* doing is mapping a specific point on one ellipse to the corresponding point on the other ellipse. Take a wide axis-aligned ellipse, and the point that was leftmost (ie where the ellipse cut the major axis) - after applying a vertical shear, that point is still leftmost *but* it is no longer the place where the major axis intersects the ellipse! The outline of the ellipse has been shuffled clockwise a little. Matrix transformations are affine and map a point such as that to the expected point on the rotated ellipse, but these transformations don't work like that.
Hmm, ok, so now I'm unconvinced that a shear of an ellipse is a different rotated/stretched ellipse. Is there an obvious proof for this?

Dunno, not my area. I'd google for: geometry shear ellipse and see what comes up. Meanwhile I've implemented a testbed… http://scratch.mit.edu/projects/50170934/

G

bobbybee

gtoal wrote:
Hardmath123 wrote:
gtoal wrote:
The trick is that there is a mapping of one ellipse to another ellipse like this, but what you are *not* doing is mapping a specific point on one ellipse to the corresponding point on the other ellipse. Take a wide axis-aligned ellipse, and the point that was leftmost (ie where the ellipse cut the major axis) - after applying a vertical shear, that point is still leftmost *but* it is no longer the place where the major axis intersects the ellipse! The outline of the ellipse has been shuffled clockwise a little. Matrix transformations are affine and map a point such as that to the expected point on the rotated ellipse, but these transformations don't work like that.
Hmm, ok, so now I'm unconvinced that a shear of an ellipse is a different rotated/stretched ellipse. Is there an obvious proof for this?

Dunno, not my area. I'd google for: geometry shear ellipse and see what comes up. Meanwhile I've implemented a testbed… http://scratch.mit.edu/projects/50170934/

G

I'm tempted to bruteforce a solution set and apply some machine learning algorithms to create a regression for the data set. Thoughts?

“Ooo, can I call you Señorita Bee?” ~Chibi-Matoran

nXIII

Hardmath123 wrote:
Hmm, ok, so now I'm unconvinced that a shear of an ellipse is a different rotated/stretched ellipse. Is there an obvious proof for this?

https://www.dropbox.com/s/qo8bwtvc7ohij00/EllipseShear.pdf?dl=0

♡ nXIII · GitHub

gtoal

bobbybee wrote:
gtoal wrote:
Meanwhile I've implemented a testbed… http://scratch.mit.edu/projects/50170934/

I'm tempted to bruteforce a solution set and apply some machine learning algorithms to create a regression for the data set. Thoughts?

That *ought* to work as long as you normalise the scale parameter in my testbed to 1.0 (it really isn't needed, you can just scale up both axes) so that there's a single solution. I'll be extremely interested to see what you come up with and whether we can reverse engineer the logic from the final derived function…

Remember to vary the axes as well as the rotation. I think it's a three-dimensional surface.

G

Last edited by gtoal (March 1, 2015 19:45:49)

gtoal

nXIII wrote:
Hardmath123 wrote:
Hmm, ok, so now I'm unconvinced that a shear of an ellipse is a different rotated/stretched ellipse. Is there an obvious proof for this?
https://www.dropbox.com/s/qo8bwtvc7ohij00/EllipseShear.pdf?dl=0

Perfect! (I just knew it was intuitively so; I couldn't justify it but I was sure of it.)

Last edited by gtoal (March 1, 2015 19:16:51)

gtoal

nXIII wrote:
Hardmath123 wrote:
Hmm, ok, so now I'm unconvinced that a shear of an ellipse is a different rotated/stretched ellipse. Is there an obvious proof for this?
https://www.dropbox.com/s/qo8bwtvc7ohij00/EllipseShear.pdf?dl=0

This page seems to have some useful info. http://math.stackexchange.com/questions/185718/ellipse-with-non-orthogonal-minor-and-major-axes

Last edited by gtoal (March 1, 2015 19:47:07)

nXIII

Solved: http://scratch.mit.edu/projects/50183762/

Last edited by nXIII (March 1, 2015 20:03:14)

♡ nXIII · GitHub

gtoal

nXIII wrote:
Solved: http://scratch.mit.edu/projects/50183762/

The Dude Abides!

Colour me impressed.

Here's my interpretation of nXIII's mapping code; I've made a special case for circles because ideally you would want a rotated circle to be rendered identically at all rotations, but that doesn't in fact happen by default - there are slight variations in precisely which pixels are drawn at the top and sides of the circle.

define Draw Rotated Ellipse (x) (y) (x axis) (y axis) (rotation) <filled?>
if <(x axis) = (y axis)> then
    Draw Sheared Ellipse (x) (y) (x axis) (y axis) (filled?) (1) (0)
else
    set [theta v] to ([atan v] of (((y axis) / (x axis)) * ((-1) * ([tan v] of (rotation)))))
    set [shear: dx v] to (((x axis) * (([cos v] of (theta)) * ([cos v] of (rotation)))) - ((y axis) * (([sin v] of (theta)) * ([sin v] of (rotation)))))
    set [shear: dy v] to (((x axis) * (([cos v] of (theta)) * ([sin v] of (rotation)))) + ((y axis) * (([sin v] of (theta)) * ([cos v] of (rotation)))))
    set [shear: x axis v] to ([abs v] of (shear: dx))
    set [shear: y axis v] to (((y axis) * (x axis)) / (shear: x axis))
    Draw Sheared Ellipse (x) (y) (shear: x axis) (shear: y axis) (filled?) (shear: dx) (shear: dy) 
end

I've modified the Ellipse Library so that the interface to drawing an ellipse uses axes and rotation and hides the internal shearing.

Thanks nXIII!

Last edited by gtoal (March 1, 2015 23:30:56)

Discuss Scratch