Calculating the lines of best fit for an ellipse

I am trying to calculate the number of lines of best fit for an ellipse; taking into account the specified margin of error (minimum distance from the border).

My solution for the unit circle was this way.

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 just take 2^i

( i

as number of iterations) as the number of segments you want. This algorithm probably O(1)

doesn't work for ellipses (which is why I need it).

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

+3


source to share


2 answers


I can't formulate a good neat answer - working with ellipses is pretty tricky in circles - but here goes step by step:

First - I would tighten the algorithm for a circle using a trigger bit. If you draw a chord (line segment) that spans the angle angle

through the unit of the circle, the maximum distance from the circle to the chord is calculated like this:

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

      

(You can see this if you draw a diagram using the bisector of a circle, chord, and chord.) By inverting this formula, you can calculate the angle given the margin of error. The first line of code gives the exact angle; the second line compresses the angle if necessary, 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, simply calculate the points around the unit circle for the endpoints of the chord: [(1,0), (cos(angle),sin(angle)), cos(2*angle),sin(2*angle)), ... ]

. You will get a regular polygon.

Second - For a circle with a radius, radius

follow 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 endpoints of the chord by multiplying the sin and cos values ​​by the radius.

Third - For an ellipse with maximum and minimum radii major

and minor

I would use the circle formula to calculate the angle again:

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, you can calculate the endpoints of the chord as follows:

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

      

This doesn't always give you the minimum polygon for the ellipse (it will have more chords than needed near the minor axis, especially for very tight ellipses), but you only need 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 recalculate the angle after each chord, and the formula is not straightforward (where "not straightforward" = "hard for me to figure it out").

+3


source


There is an O (1) solution for a circle: you can calculate the number of equal segments to get the sagitta you want . Ellipse is a harder case. The maximum sagitta will be for a chord perpendicular to the semi-major axis (near the foci), so it seems reasonable to choose the transition points of the segments at the ends of the semi-major axis (at least in the first approximation)



+1


source







All Articles