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

Question

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

Answer 1

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.

Answer 2

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 this is not what you want, please clarify your question.

Answer 3

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

Answer 4

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.