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

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;
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.)

• Just to be clear, you want the points to be evenly spaced wrt the circumference? – tenpn Jul 27 '10 at 14:35

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/

• Wow this is more complicated than I thought! So yes, basically I am trying to do this quitordie.com/goodEllipse.gif (taken from this thread bigresource.com/Tracker/Track-flash-DO1WzX6KNq). If I'm understanding this correctly, it means that I am not looking to make the points equidistant by arc length. – Justin C. Rounds Aug 12 '10 at 14:46
• I think you do want to plot the points equidistant by arc length. There is just not a nice formula for the circumference of a ellipse. On the mathoverflow page there is a link to this page en.wikipedia.org/wiki/Circumference that gives approximations for the circumference that you should be able to use. – Jonathan Fischoff Aug 12 '10 at 18:40
• The real lesson I think is that if you want the mathematics to be simple in general, use polynomials or rational functions. Ellipses seem simple, but have complex properties that make them tricky to calculate with. Polynomials are very well bahaved and approximate curves (like ellipses) very well. – Jonathan Fischoff Aug 12 '10 at 19:37

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 :-)

• I auto-upvote for ASCII art. – Jimmy Nov 3 '11 at 15:56

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 ).

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

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;
}

}
`