Was ist ein einfacher Algorithmus zur Berechnung gleichmäßig verteilter Punkte auf einer Ellipse?

8

Ich suche nach einem einfachen Algorithmus, um gleichmäßig verteilte Punkte auf einer Ellipse zu zeichnen, wenn man die Haupt- und Nebenachse berücksichtigt. Mit einem Kreis wie diesem ist das wirklich einfach:

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

(wodurch Punkte erzeugt werden, die den gleichen Abstand zu ihren Nachbarpunkten haben), aber ich kann auf einer Ellipse keinen Weg finden oder herausfinden, dies zu tun. (Lösungen in AS3 bevorzugt, aber nicht erforderlich.)

Justin C. Runden
quelle
3
Um ganz klar zu sein, möchten Sie, dass die Punkte gleichmäßig über den Umfang verteilt sind?
Tenpn

Antworten:

6

Parametrieren Sie es nach Bogenlänge neu und probieren Sie es gleichmäßig aus. Wenn Sie Hilfe beim Rechnen benötigen, würde ich Sie hier fragen:
https://math.stackexchange.com/

Es wurde auch hier gefragt: /mathpro/28070/finding-n-points-that-are-equidistant-around-the-circumference-of-an-ellipse

Jonathan Fischoff
quelle
Wow das ist komplizierter als ich dachte! Also ja, im Grunde versuche ich dies zu tun quititie.com/goodEllipse.gif (entnommen aus diesem Thread bigresource.com/Tracker/Track-flash-DO1WzX6KNq ). Wenn ich das richtig verstehe, bedeutet dies, dass ich nicht versuche, die Punkte durch die Bogenlänge äquidistant zu machen.
Justin C. Runden
Ich denke, Sie möchten die Punkte in gleichem Abstand zur Bogenlänge darstellen. Es gibt einfach keine schöne Formel für den Umfang einer Ellipse. Auf der Mathoverflow-Seite befindet sich ein Link zu dieser Seite en.wikipedia.org/wiki/Circumference , der Annäherungen für den Umfang enthält, den Sie verwenden sollten.
Jonathan Fischoff
Die eigentliche Lehre, die ich denke, ist, wenn Sie möchten, dass die Mathematik im Allgemeinen einfach ist, verwenden Sie Polynome oder rationale Funktionen. Ellipsen scheinen einfach zu sein, haben aber komplexe Eigenschaften, die ihre Berechnung schwierig machen. Polynome sind sehr gut bahaved und ungefähre Kurven (wie Ellipsen) sehr gut.
Jonathan Fischoff
6

Angemessene Annäherung

Wie bereits in anderen Antworten erwähnt, gibt es keine genaue Möglichkeit, dies zu tun. Es ist jedoch möglich, eine Lösung effizient zu approximieren.

Meine Formel behandelt nur den oberen rechten Quadranten. Es müssen verschiedene Vorzeichenwechsel angewendet werden, um andere Quadranten zu handhaben.

Sei d Ihr gewünschter Bogenabstand zwischen aufeinanderfolgenden Punkten. Angenommen, der letzte geplottete Punkt liegt bei (x, y) .

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

Dann sollte der nächste Punkt an den folgenden Koordinaten aufgezeichnet werden:

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

Beweis

Der nächste Punkt sei bei (x + Δx, y + Δy) . Beide Punkte erfüllen die Ellipsengleichung:

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

Wenn Sie y in den Gleichungen loswerden, erhalten Sie :

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

Wir nehmen an, dass Δx klein genug ist, also ersetzen wir f (x + Δx) -f (x) durch f '(x) Δx unter Verwendung der linearen Näherung für f' :

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

Wenn d klein genug ist, sind Δx und Δy klein genug und die Bogenlänge liegt nahe am euklidischen Abstand zwischen den Punkten. Die folgende Annäherung ist daher gültig:

Δx² + Δy² ~ d²

Wir ersetzen oben Δy und lösen nach Δx :

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

Was ist, wenn d nicht klein genug ist?

Wenn d zu groß ist für die oben genannten Annäherungen gültig zu sein, einfach ersetzen d mit d / N , zum Beispiel N = 3 , und nur einen Punkt aus plotten N .

Schlussbemerkung

Diese Methode hat Probleme bei Extrema ( x = 0 oder y = 0 ), die mit zusätzlichen Näherungen behoben werden können ( dh den letzten Punkt des Quadranten überspringen, unabhängig davon, ob er tatsächlich gezeichnet ist oder nicht).

Die Handhabung der gesamten Ellipse wird wahrscheinlich robuster sein, wenn das Ganze mit Polarkoordinaten wiederholt wird. Es ist jedoch eine Arbeit, und dies ist eine alte Frage, also werde ich es nur tun, wenn das Originalplakat Interesse zeigt :-)

Sam Hocevar
quelle
1
Ich stimme automatisch für ASCII-Kunst.
Jimmy
0

Ich hänge irgendwie genau davon ab, was du mit "gleichmäßig" meinst. Ich habe hier einen Beitrag über die Verwendung von Ellipsen in meinem Spiel geschrieben: http://world-create.blogspot.com/2009/01/ellipse-maths.html

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

Sie können Punkte erhalten, die gleichmäßig um die Ellipse verteilt sind, indem Sie Folgendes tun:

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

Abhängig von den Besonderheiten Ihrer Ellipse können diese Werte jedoch zusammengefasst werden (wenn die Ellipse ein "spitzes" Ende aufweist).

Dave
quelle
0

Die Antwort, mit voller Java - Code wird auf Stackoverflow befindet sich hier

Beantwortet von:

bearbeitet 11. Dezember 13 um 4:14 John Paul

antwortete am 11. Dezember 13 um 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
quelle