What is a simple algorithm for calculating evenly distributed points on an ellipse?

Question

I am looking for a simple algorithm to plot evenly distributed points on an ellipse, given the major and minor axes. This is really easy to do with a circle like so:

var numberOfPoints = 8;
var angleIncrement = 360 / numberOfPoints;
var circleRadius = 100;
for (var i = 0; i < numberOfPoints; i++) {
    var p = new Point();
    p.x = (circleRadius * Math.cos((angleIncrement * i) * (Math.PI / 180)));
    p.y = (circleRadius * Math.sin((angleIncrement * i) * (Math.PI / 180)));
}

(which creates points that are the same distance apart from their neighboring points) but I can't find or figure out a way to do this on an ellipse. (Solutions in AS3 preferred, but not required.)

Answer 1

Re-parameterize it by arc length and sample uniformly. If you need help doing the math, I would ask it here:
https://math.stackexchange.com/

it was also asked here: https://mathoverflow.net/questions/28070/finding-n-points-that-are-equidistant-around-the-circumference-of-an-ellipse

Answer 2

Reasonable approximation

As already stated in other answers, there is no exact way to do this. However, it is possible to efficiently approximate a solution.

My formula will only handle the upper right quadrant. Various sign changes will need to be applied to handle other quadrants.

Let d be your desired arc distance between consecutive points. Suppose the last plotted point is at (x,y).

  |
b +-------._  (x,y)
  |         `@-._
  |              `-.
  |                 `.
  |                   \
 -+--------------------+--->
 O|                    a

Then the next point should be plotted at the following coordinates:

x' = x + d / sqrt(1 + b²x² / (a²(a²-x²)))
y' = b sqrt(1 - x'²/a²)

Proof

Let the next point be at (x+Δx,y+Δy). Both points satisfy the ellipse equation:

x²/a² + y²/b² = 1
(x+Δx)²/a² + (y+Δy)²/b² = 1

Getting rid of y in the equations gives:

Δy = b (sqrt(1 - (x+Δx)²/a²) - sqrt(1 - x²/a²))

We assume Δx is small enough, so we replace f(x+Δx)-f(x) with f'(x)Δx using the linear approximation for f':

Δy = -bxΔx / (a² sqrt(1 - x²/a²))

If d is small enough, then Δx and Δy are small enough and the arc length is close to the euclidian distance between the points. The following approximation is therefore valid:

Δx² + Δy² ~ d²

We replace Δy in the above and solve for Δx:

Δx ~ d / sqrt(1 + b²x² / (a²(a²-x²)))

What if d is not small enough?

If d is too large for the above approximations to be valid, simply replace d with d/N, for instance N = 3, and only plot one point out of N.

Final note

This method has problems at extrema (x = 0 or y = 0), that can be dealt with using additional approximations (ie. skipping the last point of the quadrant, whether it's actually plotted or not).

Handling the whole ellipse will probably be more robust by redoing the whole thing using polar coordinates. However, it's some work, and this is an old question, so I'll only do it if there is some interest from the original poster :-)

Answer 3

I kinds of depends exactly what you mean by "evenly". I wrote a post about using ellipses in my game here: http://world-create.blogspot.com/2009/01/ellipse-maths.html

From the post:

class Ellipse
{
  Vector3 m_centre;
  Vector3 m_up;
  Vector3 m_along;
  float m_h;
  float m_l;
};

Vector3 Ellipse::PointAt(float t)
{
  float c = cos(t);
  float s = sin(t);

  return m_h * c * m_up + m_l * s * m_along + m_centre;      
}

You can get points evenly spaced around the ellipse by angle by doing:

PointAt(0.0f);
PointAt(kHalfPi);
PointAt(kPi);
PointAt(kHalfPi * 3.0f);
PointAt(kTwoPi);

But depending on the specifics of your ellipse these values could be bunched up ( if there is a "pointy" end to the ellipse ).

Answer 4

The answer, with full Java code is located on StackOverflow here

Answered by:

edited Dec 11 '13 at 4:14 John Paul

answered Dec 11 '13 at 3:48 Dave

package com.math;

public class CalculatePoints {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    /*
     * 
    dp(t) = sqrt( (r1*sin(t))^2 + (r2*cos(t))^2)
    circ = sum(dp(t), t=0..2*Pi step 0.0001)

    n = 20

    nextPoint = 0
    run = 0.0
    for t=0..2*Pi step 0.0001
        if n*run/circ >= nextPoint then
            set point (r1*cos(t), r2*sin(t))
            nextPoint = nextPoint + 1
        next
        run = run + dp(t)
    next
 */


    double r1 = 20.0;
    double r2 = 10.0;

    double theta = 0.0;
    double twoPi = Math.PI*2.0;
    double deltaTheta = 0.0001;
    double numIntegrals = Math.round(twoPi/deltaTheta);
    double circ=0.0;
    double dpt=0.0;

    /* integrate over the elipse to get the circumference */
    for( int i=0; i < numIntegrals; i++ ) {
        theta += i*deltaTheta;
        dpt = computeDpt( r1, r2, theta);
        circ += dpt;
    }
    System.out.println( "circumference = " + circ );

    int n=20;
    int nextPoint = 0;
    double run = 0.0;
    theta = 0.0;

    for( int i=0; i < numIntegrals; i++ ) {
        theta += deltaTheta;
        double subIntegral = n*run/circ;
        if( (int) subIntegral >= nextPoint ) {
            double x = r1 * Math.cos(theta);
            double y = r2 * Math.sin(theta);
            System.out.println( "x=" + Math.round(x) + ", y=" + Math.round(y));
            nextPoint++;
        }
        run += computeDpt(r1, r2, theta);
    }
}

static double computeDpt( double r1, double r2, double theta ) {
    double dp=0.0;

    double dpt_sin = Math.pow(r1*Math.sin(theta), 2.0);
    double dpt_cos = Math.pow( r2*Math.cos(theta), 2.0);
    dp = Math.sqrt(dpt_sin + dpt_cos);

    return dp;
}

}