CODEWITHSUNDEEP
pythonmathgeometry
hiddensunset4
hiddensunset4

Reputation: 6029

Calculating lines of best fit for an ellipse

I'm trying to calculate the number of lines of best fit for an ellipse; given a desired error margin (minimum distance from the boundary).

My solution for a unit circle was thus.

def f(u, v, r):
    mid_uv = (u + v) * 0.5
    N = normalized(mid_uv)

    return N * r

And repeat v = f(u, v, r) until radius - |v| < error.

Then simply take 2^i (i being the number of iterations) as the number of segments required. This algorithm could probably be O(1), and does not work for ellipses (which is what I need it for).

How can I adapt it? Or better yet, is there another solution?

Upvotes: 3

Views: 1052

Answers (2)

Peter Raynham
Peter Raynham

Reputation: 657

I cannot formulate a nice neat answer - working with ellipses is quite a bit more challenging that circles - but here goes, in steps:

First - I would tighten up the algorithm for the circle by using a bit of trig. If you draw a chord (line segment) that spans angle angle through a unit circle, the maximum distance from the circle to the chord is calculated thus:

error = 1 - math.cos( angle / 2 )

(You can see this if you draw a diagram with the circle, chord, and chord's bisector.) Inverting this formula, you can calculate the angle given the tolerable error. The first line of code gives the precise angle; the second line shrinks the angle if needed so that it is an exact fraction of the whole circle.

angle = 2 * math.acos( 1 - error )
angle = (2*math.pi) / math.ceil( (2*math.pi) / angle )

Once you have the angle, it's simple to calculate the points around the unit circle for your chord end-points: [(1,0), (cos(angle),sin(angle)), cos(2*angle),sin(2*angle)), ... ]. You will end up with a regular polygon.

Second - For a circle with radius radius, run the above formulas adjusted as follows:

angle = 2 * math.acos( 1 - error/radius )
angle = (2*math.pi) / math.ceil( (2*math.pi) / angle )

And calculate the chord end-points by multiplying the sin and cos values by the radius.

Third - For an ellipse with maximal and minimal radii major and minor, I would use the circle formula to again calculate an angle:

radius = max( major, minor )
angle = 2 * math.acos( 1 - error/radius )
angle = (2*math.pi) / math.ceil( (2*math.pi) / angle )

If the major radius is in the x direction and the minor radius is in the y direction, then you can calculate the chord end-points like this:

[ (major, 0),
  (major*cos(angle), minor*sin(angle)),
  (major*cos(2*angle), minor*sin(2*angle)),
  ... ]

This does not always give you the minimal polygon for an ellipse (it will have more chords than necessary near the minor axis, especially for very squashed ellipses), but you only have to do the angle calculation once. If you really need to minimize the number of chords, then after drawing each chord, you will need to re-calculate the angle after each chord, and the formula is not straight-forward (where "not straight-forward" = "difficult for me to figure out").

Upvotes: 3

MBo
MBo

Reputation: 80287

There is O(1) solution for circle: you can calculate number of equal segments to obtain needed sagitta. Ellipse is more hard case. Maximum sagitta will for a chord that is perpendicular to larger semiaxis (near focuses), so it seems reasonable to choose the points of junction of segments at the ends of larger semiaxis (at least - as first approximation)

Upvotes: 1

Related Questions