4
$\begingroup$

Hello all. This is probably a simple problem for you guys, but my geometry is a bit rusty and I am hoping that you can help.

I am trying to arrange an arbitrary number of objects around the circumference of an ellipse. My first stab at the problem resulted in the use of a simple rotational matrix like this (note that I am using graphical Cartesian coordinates where y increases down from the top of the screen).

def rotate(x, y, theta)
  x_p = (x * Math.cos(theta)) - (y * Math.sin(theta))
  y_p = (y * Math.cos(theta)) + (x * Math.sin(theta))
  return [x_p, y_p]
end

That is obviously a circle, so I use the x coordinate and feed it into the equation of my ellipse to get the y(s).

This works and does what it is supposed to, but the problem is that I am only incrementing theta to find my points, so obviously they are not equidistant around the circumference of the ellipse. That is what I am after, and any help would be greatly appreciated.

You can find a description of the problem with pictures in this thread:

http://www.bigresource.com/Tracker/Track-flash-DO1WzX6KNq/

$\endgroup$
20
  • $\begingroup$ Can you just put a link to the image? $\endgroup$
    – S. Donovan
    Commented Jun 13, 2010 at 22:31
  • 1
    $\begingroup$ Let C be the value of the complete elliptic integral of the second kind. n is the number of points. First find C then solve complete elliptic integral of the second kind set equal to (c/n)m for m=1 to n/4. (use symmetry to get the other 3/4ths of the points. I don't know if there is a more painless way. $\endgroup$
    – S. Donovan
    Commented Jun 13, 2010 at 22:40
  • 2
    $\begingroup$ One thing you might do is this: parametrize the ellipse (probably as Will suggests). Then, the norm of the vector ($\partial x / \partial \theta$, $\partial y / \partial \theta$) gives you the speed with which you are traversing the ellipse at time $\theta$. So, if $s(\theta)$ is this speed, and $\theta_1$ is close to $\theta_2$, an approximation of the distance along the ellipse from $\theta_1$ to $\theta_2$ is given by $(\theta_2 - \theta_1) s(\theta_1)$. A better approximation is $(\frac{1}{6}s(\theta_1)+\frac{1}{6}s(\theta_2)+\frac{2}{3} s((\theta_2-\theta_1)/2))(\theta_2-\theta_1)$ $\endgroup$ Commented Jun 14, 2010 at 0:00
  • 2
    $\begingroup$ you can use AGM to speed up elliptic integral evaluation paramanands.wordpress.com/2009/08/12/… $\endgroup$
    – SandeepJ
    Commented Jun 14, 2010 at 0:46
  • 2
    $\begingroup$ I don't know why everyone assumes that "even spaced along the circumference" refers to the arc length and not to plain old Euclidean distance, as in Agol's answer. biged781, can you, please, clarify what YOU mean by "evenly spaced"? Also, how large is the typical number of points and what are the tolerances? $\endgroup$ Commented Jun 15, 2010 at 5:42

5 Answers 5

6
$\begingroup$

This answer assumes you are interested in finding $n$ points on an ellipse such that the arc lengths between successive points are equal.

As others mentioned, this problem involves an elliptic integral, which has no elementary expression. However, many scientific computation libraries are able to compute this function numerically, and you can take advantage of that. It looks like you're using Python; one possibility here would be the GNU Scientific Library (gsl) for which Python bindings are available.

Say your ellipse is parametrized by $x(t) = a \cos t$, $y(t) = b \sin t$ where $a$ is the semimajor and $b$ the semiminor axis. Let $e = \sqrt{1-b^2/a^2}$ be the eccentricity. The arclength from $(x(0), y(0)) = (a,0)$ counterclockwise to $(x(t), y(t))$ is given by $s(t)=a E(t,e)$, where $E(t,e) = \int_0^t \sqrt{1-e^2 \sin^2\theta}d\theta$ is the "incomplete elliptic integral of the second kind". gsl implements this function as gsl_sf_ellint_E. The total arc length of your ellipse is $S = s(2\pi)$, which you can compute, so you need to find the value $t_k$ such that $s(t_k) = kS/n$, for each $k=0,\dots,n$. That is, you must solve for $t$ in the equation $s(t) = kS/n$.

But you are able to compute $s(t)$ numerically, and you also know the derivative $s'(t) = a \sqrt{1 - e^2 \sin^2 t}$ thanks to the fundamental theorem of calculus. Using this, it is a standard procedure to solve the equation iteratively using something like Newton's method. You could implement it yourself with a bit of reading, or use one of gsl's more sophisticated implementations, e.g. gsl_root_fdfsolver_steffenson.

$\endgroup$
1
  • $\begingroup$ Thank you! I am using Ruby in a somewhat constrained environment (a video game engine that is somewhat specific in the way it workd), but I am certain that I can find an equivalent or at least some source code. I always try to understand what I am doing first, but yeah, I am just a lowly software developer =) $\endgroup$ Commented Jun 15, 2010 at 21:27
3
$\begingroup$

I'll attempt to answer your question by misinterpreting it.

As pointed out in the comments, computing elliptic integrals is not going to be easy. But what if you wanted to find $n$ points arranged around an ellipse which form the vertices of an equilateral polygon? Now the answer to the question is given by a real algebraic variety. It's possible that this question may be computationally more tractable.

There are $2n$ variables $(x_i,y_i)$, $i=1,\ldots,n$, and $2n-1$ equations: $$ \frac{x_i^2}{a^2}+\frac{y_i^2}{b^2}=1,\ i=1,\ldots, n,$$ $$(x_i-x_{i+1})^2+(y_i-y_{i+1})^2=(x_{i+1}-x_{i+2})^2+(y_{i+1}-y_{i+2})^2, i=1,\ldots, n-1,$$ indices taken $(\mod n)$.

Also, for geometric reasons, one expects $n-1$ components to this variety, each of which is a circle. For example, if $n=5$, one would expect two solutions which are oriented in different directions, and two solutions which are star shaped. As one moves around the circle, the solution should move around.

Thus, one expects this variety to be a complete intersection defined by quadratic equations. There are methods from algebraic geometry to find solutions to such equations. There are versions of Newton's recursion which may be effective for finding a numerical solution. The dihedral symmetry might further constrain the solutions. Maybe someone could point you to some references if this sort of solution would suffice for your application?

$\endgroup$
5
  • $\begingroup$ Thank you very much, I will look more closely at this when I get a chance. I also saw an allusion to this method on another site. Thanks again! $\endgroup$ Commented Jun 14, 2010 at 22:09
  • $\begingroup$ Your use of the nomenclature "regular polygon" is misleading: all you require is that the sides be the same. A true regular polygon is inscribed in the circle, so it can be inscribed in an ellipse only for $n\leq 4.$ $\endgroup$ Commented Jun 15, 2010 at 5:33
  • 2
    $\begingroup$ The number of components is much larger than $n$ (and closer to $2^n$) unless you impose additional inequalities saying that the points are distinct, or the polygon convex. $\endgroup$
    – T..
    Commented Jun 15, 2010 at 22:19
  • $\begingroup$ Good point - I suppose these will fold up the n-gon to lower order equilateral polygons. $\endgroup$
    – Ian Agol
    Commented Jun 16, 2010 at 16:21
  • $\begingroup$ They would correspond to equilateral paths or cycles of size at most $n$, together with a closed walk of length $n$ on this graph (a graph homomorphism from the cycle $C_n$ of length $n$ to the equilateral thing). Or the same thing modulo rotations/reflections of the homomorphed $C_n$ graph. $\endgroup$
    – T..
    Commented Jun 17, 2010 at 7:28
1
$\begingroup$

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

}
$\endgroup$
0
$\begingroup$

an easier method to compute the arclength can be found under 'circumference of an ellipse on wikipedia - a good algebraic approx to the ecliptic integrals' solution envolving functions no more complex than sqrt (). I have been looking at this, it does give the correct circumferance, but I am having issues with making my incremental angle increase from the knowledge of the arc length increment! (this is probably trivial in comparison, any ideas?)

$\endgroup$
0
$\begingroup$

If a practical solution is sought For the problem of getting the euclidean distances equal then start with the approximate solution from the question, perhaps fix one point (or don't) and apply an iterative method to improve things. One possibility is a Newton's method for the sum of the squares of the differences of the squared distances.

$\sum(d_i-d_{i-1})^2$ where $d_i=(x_i-x_{i+1})^2+(y_i-y_{i+1})^2$

Perhaps Lagrange Multipliers for the minimization of $\sum d_i$ would yield a solution with points equally spaced and consecutive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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