# Generating coordinates for 'N' points on the circumference of an ellipse with fixed nearest-neighbor spacing

I have an ellipse with semimajor axis $A$ and semiminor axis $B$. I would like to pick $N$ points along the circumference of the ellipse such that the Euclidean distance between any two nearest-neighbor points, $d$, is fixed. How would I generate the coordinates for these points? For what range of $A$ and $B$ is this possible?

As a clarification, all nearest-neighbor pairs should be of fixed distance $d$. If one populates the ellipse by sequentially adding nearest neighbors in, say, a clockwise fashion, the first and last point added should have a final distance $d$.

-

As long as $d$ is sufficiently small (where "sufficiently small" depends on the eccentricity of the ellipse), you can proceed as follows:

Start at point $P_0$, and set off around the ellipse in steps of (Euclidean) length $d$, leaving point $P_i$ at the $i$th step. When you reach or pass the original point $P_0$, leave a point $P_n$ there, and stop.

If $P_n$ and $P_0$ coincide, we are done, Otherwise, decrease $d$ continuously until they do. Now we have $n$ equally spaced points on the ellipse. And we can repreat this procedure to find $n+1$ equally spaced points, and so on.

There are two things that can go wrong:

1. This procedure works, but the ellipse is so eccentric that $P_{i-1}$ and $P_{i+1}$ are not the nearest neighbours of $P_i$ (because there is a closer point across the semi-minor axis).
2. For some $i$, the position of $P_i$ is not a continuous function of $d$. This can happen if $P_{i-1}$ is near the 'sharp end' of the ellipse, and the line $P_{i-1} P_i$ is normal to the ellipse at $P_i$. This can happen if, roughly, the curvature of the ellipse exceeds $\frac{1}{2d}$ at some point.
-

Perhaps I am misinterpreting your question, as I think there is a very simple way to do this. Given the ellipse, and given $N$, take $d$ very small compared to $A/N$, pick a point on the ellipse, then going around the ellipse clockwise (say) pick points such that each is at distance $d$ from the preceding one. Locating each point is a simple matter of finding the intersection with the ellipse of a circle of radius $d$ centered at the previous point.

-
If I take $d$ very small to $\frac{A}{N}$ then won't the two terminal points won't have a nearest-neighbor distance of $<<d$? –  Ness Oct 14 '11 at 8:54
@Ness: it may, it may not. It's hard to tell unless you actually do it... –  Guess who it is. Oct 14 '11 at 8:59
I think the OP wants the distance between the first and last points to be $d$ too. So the question is not trivial. –  TonyK Oct 14 '11 at 9:03
@TonyK, right, that's what I was trying to say. If I don't care about this nearest-neighbor pair, the problem is trivial. –  Ness Oct 14 '11 at 9:13
I just adding a (hopefully) appropriate clarification to the problem description. –  Ness Oct 14 '11 at 9:18

To find such points exactly amounts to solving a system of $2N$ or so quadratic equations. A practical way could be the following: Choose the points $$z_k:=\bigl(A\cos{2\pi k\over N}, B\sin{2\pi k\over N}\bigr)\quad(0\leq k\leq N)$$ $(z_0=z_N)$ as starting set and update the $z_k$, $0<k<N$, recursively in the following way: Each $z_k$ is replaced by the point $z_k'$ on the arc $(z_{k-1},z_{k+1})$ which is at equal distance from $z_{k-1}$ and $z_{k+1}$. This point can be found by solving a single quadratic equation. I conjecture that this procedure converges "linearly" to the unique solution of the problem with $z_0=(A,0)$.

-

I will assume that $A$, $B$ and $N$ are given, and that $d$ is unknown.

There is always a solution. Let $L$ be the perimeter of the ellipse. An obvious constraint is $N\,d<L$. Take $d\in(0,L/N)$. As explained in Gerry Myerson's answer, pick a point $P_1$ on the ellipse, and then pick points $P_2,\dots,P_N$ such that $P_{i+1}$ is clockwise from $P_i$ and the euclidean distance between $P_i$ and $P_{i+1}$ is $d$. If $d$ is small, $P_N$ will be short of $P_1$, while if $d$ is large, it will "overpass" $P_1$. In any case, the position of $P_N$ is a continuous function of $d$. By continuity, there will be a value of $d$ such that $P_1=P_N$. It is also clear that this value is unique.

To find $P_N$ for a given $d$ you need to solve $N-1$ quadratic equations. To compute the value of $d$, you can use the bisection method.

Edit: TonyK's objections can be taken care of if $N=2\,M$ is even. Take $P_1=(A,0)$ and follow the procedure to find points $P_2,\dots,P_{M+1}$ in the upper semiellipse such that $P_{i+1}$ is clockwise of $P_i$ and at distance $d$, and $P_{M+1}=(-A,0)$. The the sought solution is $P_1,\dots,P_{M+1},\sigma(P_M),\dots,\sigma(P_2)$, where $\sigma(P)$ is the point symmetric of $P$ with respect to the axis $y=0$.

If $N=2\,M+1$ is odd, I believe that there is also a symmetric solution, but I have to think about it.

-
See my answer for objections to this argument! –  TonyK Oct 14 '11 at 10:03
@TonyK I have edited my answer. –  Julián Aguirre Oct 14 '11 at 11:37
Your solution for even $M$ doesn't answer my first point. If the ellipse is flat enough, it may be that $P_{M+1}$ is closer to $P_{M-1}$ than it is to $P_M$. –  TonyK Oct 14 '11 at 11:42
So by symmetry we could also have $P_3$ closer to $P_1$ than $P_2$? –  Julián Aguirre Oct 14 '11 at 13:14
Sorry, I meant $P_{M+2}$ is closer to $P_M$ than to $P_{M+1}$. So by symmetry $P_2$ is closer to $P_{N-1}$ than to $P_1$. Draw yourself an ellipse with $A=5, B=1$, and take $N=8$. Then you'll see what I mean. –  TonyK Oct 14 '11 at 14:44

Assuming you have a starting point along the ellipse, position P, generate the next candidate points by intersecting the ellipse with a circle of radius d, where d is the desired distance between adjacent points

Then choose the candidate which is of the desired winding. Winding can be calculated by considering the vector from the origin of the ellipse to position P and the vector from position P to the candidate position.

-