You are invited to Log in or Register a free Frihost Account!

Maths Brains only

chasbeen
Hello

Here's the problem. {see new addendum below}

I have generated an ellipse on a graph.

To make this more "visual" here are the coordinates...
149.1 62.5 148.6 63.8 148 65.1 147.3 66.3 146.6 67.6 145.7 68.8 144.9 70.1 143.9 71.3 143 72.5 141.9 73.6 140.9 74.7 139.9 75.6 138.8 76.6 137.7 77.5 136.6 78.3 134.4 79.8 133.2 80.3 131 81.4 128.8 82.1 126.6 82.6 124.5 82.7 122.5 82.5 119.8 81.7 117.9 80.3 116.2 78.2 115.3 76.5 114.8 74.6 114.5 72.4 114.7 69 114.8 67.9 115.4 65.4 115.8 64.1 116.8 61.6 117.3 60.4 118 59.1 118.7 57.8 119.5 56.6 120.4 55.4 121.3 54.2 122.2 53 123.2 51.8 124.2 50.7 125.2 49.7 126.3 48.7 127.4 47.8 128.5 46.9 129.6 46.1 130.8 45.4 133 44.2 135.3 43.3 136.4 42.9 139.6 42.2 140.7 42.2 143.6 42.4 145.4 43 147 43.9 148.7 45.5 150.2 47.9 150.8 49.8 151.1 51.9 151.1 54.1 150.9 56.4 150.4 58.8 150 60 149.1 62.5 M149.1 62.5 150 60 150.4 58.8 150.9 56.4 151.1 54.1 151.1 51.9 149.6 51 148.3 49.1 147 47.8 145.7 46.5 144.5 45.2 142.5 44 140.7 42.2 138.5 42.4 136.4 42.9 134.1 43.7 133 44.2 130.8 45.4 129.6 46.1 128.5 46.9 127.4 47.8 126.3 48.7 124.2 50.7 124.2 50.7 123.2 51.8 122.2 53 121.3 54.2 120.4 55.4 119.5 56.6 118.7 57.8 118 59.1 117.3 60.4 116.8 61.6 115.8 64.1 115.4 65.4 114.8 67.9 114.7 69 114.5 71.3 114.8 74.6 117.5 74.8 118.7 76.7 120 78 121.3 79.3 123.2 80 125.2 81.2 126.6 82.6 128.8 82.1 131 81.4 133.2 80.3 134.4 79.8 136.6 78.3 137.7 77.5 138.8 76.6 139.9 75.6 140.9 74.7 141.9 73.6 143 72.5 143.9 71.3 144.9 70.1 145.7 68.8 146.6 67.6 147.3 66.3 148 65.1 148.6 63.8 149.1 62.5

Each XY pair (Eg the first pair and last pair are 149.1 62.5) is a single point but I want to reduce this "Verbose" output to cubic bezier.

Is there any way you can think of doing that?

The summary output will be made up of these cubic bezier statements (1 shown) :
M100,200 C100,100 250,100 250,200

Note that in the above example C100,100 250,100 make up the control points of the cubic bezier.
M100,200 is the start point and is on the line(Start)
250,200 is the end point and is on the line(End)

What you have to think about is that the points always lie on the perimeter of an ellipse (Even a circle is an ellipse)

This means that your solution will yield an answer made up of 2 or 4 command statements like M100,200 C100,100 250,100 250,200.

You can also rely on the fact that there will always be 60 times xy coordinates.

This is hard and should only be attempted by a guy pretty sweet at Math!!

I thought a bit more. The above 64 points would be traversed so that each opposite point could be assessed for distance between (Pythagorous). Once this distance is found then max diameter is known. This also means that you would find the minimum diameter by using the offsets from these.

Eg: Max diameter found at Point 20 and Point 52. Assumed Point 36 and Point 4 for Min diameter.
Indi
Least squares.
chasbeen
Thanks for the input but I don't see how.
Additional Addendum:The solution will include as it's output 4 cubic bezier discriptions and not 2 (Since cubic beziers cannot perfectly describe an ellipse but get bl**** close with a 4 cubic bezier discriptions.)
I understand and am perfecting the question.
Indi
My bad, i assumed when you asked for math "brains" only, you didn't want to get bogged down in the elementary minutia, you just wanted the straight answer. ^_^;

Alright, here's how i would do it in the general case:
1. Start with the general equation of an ellipse: g(x,y) = Ax² + Bxy + Cy² + Dx + Ey + F = 0
2. You want the { A, B, C, D, E, F } that minimizes g(x,y) for all your input points.
3. You need the uncertainty in your input points: σ = √(1/(N - 6) * ∑(Axᵢ² + Bxᵢyᵢ + Cyᵢ² + Dxᵢ + Eyᵢ + F))
4. Your probability exponent is: χ² = √(∑((Axᵢ² + Bxᵢyᵢ + Cyᵢ² + Dxᵢ + Eyᵢ + F)²/σ²))
5. Partially differentiate that wrt each of { A, B, C, D, E, F }, and you'll have a system of six equations with six unknowns.
6. Solve that system for equations for each of { A, B, C, D, E, F }.
7. Now you have equations you can use to find the general ellipse equation with any set of (greater than 6) input points.
8. Decompose the general ellipse equation as you see fit for whatever SVG code you're using to render the ellipse.

You could also try a more direct solution, assuming you've settled on a specific set of SVG instructions to render your ellipse. However, getting the general ellipse equation first then transforming it to your specific SVG instruction set would be smarter because:
1. If you ever change your SVG instruction set (for example, from a single bezier to multiple ones, or just rendering the ellipse with the ellipse command, and some transforms) your changes to the code are simple.
2. The ellipse data (major/minor radius, rotation, center) are all clearly encoded in the general equation, so you can easily display them as needed.
3. It's almost certain that if you do some searching you can find someone who has already solved a least squares ellipse fit to the general ellipse equation, so you probably don't need to do any derivation at all for that part.
4. With the general equation, you can probably just lift code from Inkscape (assuming your project is open source, too) to generate the path code given ellipse parameters, because Inkscape does everything with paths.

So basically, by breaking the problem up into points->general ellipse equation->SVG path code, you can probably find already solved solutions for both steps separately.

************************************************************************

If all this made you go cross-eyed, the problem is that you haven't clearly specified your problem, so i had to make the most general assumptions for the broadest possible case. It's possible you have dozens of simplifying assumptions you never stated.

For example, will your points always be angularly equally spaced around the ellipse? (ie, you have 60 points - can you always be sure that point 0 is at 0° and point 30 is at 180°?) If so, you can find the ellipse centre trivially, then translate to (0, 0) to knock out two parameters from the problem.

Will your ellipse always be aligned to the x and y axes? If so, you can drop another parameter or two.

If you can know that the ellipse is oriented to the x and y axes and you can translate it to the origin, you can reduce the equation to a trivial yᵤ = mxᵤ + c least squares line fit (where yᵤ = y² and xᵤ = x²).

So, what simplifying assumptions can you make about the source data?
chasbeen
Indi

thanks for the contribution.

I found a URL that itself describes the solution...
http://www.whizkidtech.redprince.net/bezier/circle/

The author himself expressed surprise at the solution not being readily available..

You can visit the connected software tool which needs further optimization.
http://www.irunmywebsite.com/raphael/svgsource.php