Qu'est-ce qu'un algorithme simple pour calculer des points uniformément répartis sur une ellipse?

8

Je recherche un algorithme simple pour tracer des points uniformément répartis sur une ellipse, étant donné les axes majeurs et mineurs. C'est vraiment facile à faire avec un cercle comme ça:

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

(ce qui crée des points qui sont à la même distance de leurs points voisins) mais je ne peux pas trouver ou trouver un moyen de le faire sur une ellipse. (Solutions en AS3 préférées, mais non requises.)

Justin C. Rounds
la source
3
Juste pour être clair, vous voulez que les points soient régulièrement espacés par rapport à la circonférence?
tenpn

Réponses:

6

Re-paramétrez-le par longueur d'arc et échantillonnez uniformément. Si vous avez besoin d'aide pour faire le calcul, je le demanderais ici:
https://math.stackexchange.com/

il a également été demandé ici: /mathpro/28070/finding-n-points-that-are-equidistant-around-the-circumference-of-an-ellipse

Jonathan Fischoff
la source
Wow c'est plus compliqué que je ne le pensais! Alors oui, j'essaye de faire quitordie.com/goodEllipse.gif (extrait de ce fil bigresource.com/Tracker/Track-flash-DO1WzX6KNq ). Si je comprends bien, cela signifie que je ne cherche pas à rendre les points équidistants par la longueur de l'arc.
Justin C. Rounds du
Je pense que vous voulez tracer les points équidistants par longueur d'arc. Il n'y a tout simplement pas une bonne formule pour la circonférence d'une ellipse. Sur la page mathoverflow, il y a un lien vers cette page en.wikipedia.org/wiki/Circumference qui donne des approximations de la circonférence que vous devriez pouvoir utiliser.
Jonathan Fischoff
Je pense que la vraie leçon est que si vous voulez que les mathématiques soient simples en général, utilisez des polynômes ou des fonctions rationnelles. Les ellipses semblent simples, mais ont des propriétés complexes qui les rendent difficiles à calculer. Les polynômes sont très bien bahaved et les courbes approximatives (comme les ellipses) très bien.
Jonathan Fischoff
6

Approximation raisonnable

Comme déjà indiqué dans d'autres réponses, il n'y a aucun moyen exact de le faire. Cependant, il est possible d'approximer efficacement une solution.

Ma formule ne gérera que le quadrant supérieur droit . Divers changements de signe devront être appliqués pour gérer d'autres quadrants.

Soit d la distance d'arc souhaitée entre des points consécutifs. Supposons que le dernier point tracé soit à (x, y) .

  |
b +-------._  (x,y)
  |         `@-._
  |              `-.
  |                 `.
  |                   \
 -+--------------------+--->
 O|                    a

Ensuite, le point suivant doit être tracé aux coordonnées suivantes:

x' = x + d / sqrt(1 + b²x² / (a²(a²-x²)))
y' = b sqrt(1 - x'²/a²)

Preuve

Soit le point suivant à (x + Δx, y + Δy) . Les deux points satisfont l'équation de l'ellipse:

x²/a² + y²/b² = 1
(xx)²/a² + (yy)²/b² = 1

Se débarrasser de y dans les équations donne:

Δy = b (sqrt(1 - (xx)²/a²) - sqrt(1 - x²/a²))

Nous supposons que Δx est suffisamment petit, nous remplaçons donc f (x + Δx) -f (x) par f '(x) Δx en utilisant l' approximation linéaire pour f' :

Δy = -bxΔx / (a² sqrt(1 - x²/a²))

Si d est suffisamment petit, alors Δx et Δy sont suffisamment petits et la longueur de l'arc est proche de la distance euclidienne entre les points. L'approximation suivante est donc valable:

Δx² + Δy² ~ d²

Nous remplaçons Δy dans ce qui précède et résolvons pour Δx :

Δx ~ d / sqrt(1 + b²x² / (a²(a²-x²)))

Et si d n'est pas assez petit?

Si d est trop grande pour les approximations ci - dessus soient valides, il suffit de remplacer d avec d / N , par exemple N = 3 , et seulement tracer un point sur N .

Note finale

Cette méthode a des problèmes aux extrêmes ( x = 0 ou y = 0 ), qui peuvent être traités en utilisant des approximations supplémentaires ( c'est-à-dire en sautant le dernier point du quadrant, qu'il soit réellement tracé ou non).

La manipulation de l'ellipse entière sera probablement plus robuste en refaisant le tout en utilisant des coordonnées polaires. Cependant, c'est un peu de travail, et c'est une vieille question, donc je ne le ferai que s'il y a un intérêt de l'affiche originale :-)

sam hocevar
la source
1
Je vote automatiquement pour l'art ASCII.
Jimmy
0

Je dépend en quelque sorte de ce que vous entendez par "uniformément". J'ai écrit un article sur l'utilisation des ellipses dans mon jeu ici: http://world-create.blogspot.com/2009/01/ellipse-maths.html

De la poste:

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

Vous pouvez obtenir des points espacés uniformément autour de l'ellipse par l' angle en faisant:

PointAt(0.0f);
PointAt(kHalfPi);
PointAt(kPi);
PointAt(kHalfPi * 3.0f);
PointAt(kTwoPi);

Mais selon les spécificités de votre ellipse, ces valeurs pourraient être regroupées (s'il y a une extrémité "pointue" vers l'ellipse).

Dave
la source
0

La réponse, avec le code Java complet, se trouve ici sur StackOverflow

Répondu par:

édité le 11 décembre 13 à 4:14 John Paul

répondu 11 déc. 13 à 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;
}

}
David S Alderson
la source