Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question
2  
Just to be clear, you want the points to be evenly spaced wrt the circumference? –  tenpn Jul 27 '10 at 14:35

3 Answers 3

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

share|improve this answer
1  
I auto-upvote for ASCII art. –  Jimmy Nov 3 '11 at 15:56

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

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

share|improve this answer
    
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

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.