¿Qué es un algoritmo simple para calcular puntos distribuidos uniformemente en una elipse?

8

Estoy buscando un algoritmo simple para trazar puntos distribuidos uniformemente en una elipse, dados los ejes mayor y menor. Esto es realmente fácil de hacer con un círculo así:

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

(que crea puntos que están a la misma distancia de sus puntos vecinos) pero no puedo encontrar o encontrar una manera de hacer esto en una elipse. (Se prefieren soluciones en AS3, pero no se requieren).

Justin C. Rounds
fuente
3
Para ser claros, ¿quieres que los puntos estén espaciados uniformemente en la circunferencia?
Tenpn

Respuestas:

6

Vuelva a parametrizarlo por la longitud del arco y muestree uniformemente. Si necesita ayuda para hacer los cálculos, lo pediría aquí:
https://math.stackexchange.com/

también se preguntó aquí: /mathpro/28070/finding-n-points-that-are-equidistant-around-the-circumference-of-an-ellipse

Jonathan Fischoff
fuente
¡Guau, esto es más complicado de lo que pensaba! Entonces sí, básicamente estoy tratando de hacer esto quitordie.com/goodEllipse.gif (tomado de este hilo bigresource.com/Tracker/Track-flash-DO1WzX6KNq ). Si yo estoy entendiendo esto correctamente, significa que estoy no buscando hacer los puntos equidistantes de la longitud del arco.
Justin C. Rounds
Creo que quieres trazar los puntos equidistantes por la longitud del arco. Simplemente no hay una buena fórmula para la circunferencia de una elipse. En la página de mathoverflow hay un enlace a esta página en.wikipedia.org/wiki/Circumference que proporciona aproximaciones para la circunferencia que debería poder usar.
Jonathan Fischoff el
Creo que la verdadera lección es que si quieres que las matemáticas sean simples en general, usa polinomios o funciones racionales. Las elipses parecen simples, pero tienen propiedades complejas que las hacen difíciles de calcular. Los polinomios están muy bien curvados y las curvas aproximadas (como las elipses) muy bien.
Jonathan Fischoff el
6

Aproximación razonable

Como ya se indicó en otras respuestas, no hay una forma exacta de hacer esto. Sin embargo, es posible aproximar eficientemente una solución.

Mi fórmula solo manejará el cuadrante superior derecho . Se deberán aplicar varios cambios de signos para manejar otros cuadrantes.

Deje d ser su distancia de arco deseada entre puntos consecutivos. Supongamos que el último punto trazado está en (x, y) .

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

Luego, el siguiente punto debe trazarse en las siguientes coordenadas:

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

Prueba

Deje que el siguiente punto esté en (x + Δx, y + Δy) . Ambos puntos satisfacen la ecuación de elipse:

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

Deshacerse de y en las ecuaciones da:

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

Suponemos que Δx es lo suficientemente pequeño, por lo que reemplazamos f (x + Δx) -f (x) con f '(x) Δx usando la aproximación lineal para f' :

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

Si d es lo suficientemente pequeño, entonces Δx y Δy son lo suficientemente pequeños y la longitud del arco está cerca de la distancia euclidiana entre los puntos. Por lo tanto, la siguiente aproximación es válida:

Δx² + Δy² ~ d²

Reemplazamos Δy en lo anterior y resolvemos para Δx :

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

¿Qué pasa si d no es lo suficientemente pequeño?

Si d es demasiado grande para las aproximaciones anteriores sean válidas, simplemente reemplazar d con d / N , por ejemplo N = 3 , y sólo trazar un punto de N .

Nota final

Este método tiene problemas en los extremos ( x = 0 o y = 0 ), que pueden abordarse utilizando aproximaciones adicionales ( es decir, omitir el último punto del cuadrante, ya sea que esté trazado o no).

El manejo de toda la elipse probablemente será más robusto al rehacer todo usando coordenadas polares. Sin embargo, es algo de trabajo, y esta es una vieja pregunta, así que solo lo haré si hay algún interés en el póster original :-)

sam hocevar
fuente
1
Auto-voto por el arte ASCII.
Jimmy
0

Depende un poco de lo que quieres decir con "uniformemente". Escribí una publicación sobre el uso de puntos suspensivos en mi juego aquí: http://world-create.blogspot.com/2009/01/ellipse-maths.html

De la publicación:

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

Puede obtener puntos espaciados uniformemente alrededor de la elipse por ángulo haciendo:

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

Pero dependiendo de los detalles de su elipse, estos valores podrían agruparse (si hay un final "puntiagudo" para la elipse).

Dave
fuente
0

La respuesta, con el código Java completo, se encuentra en StackOverflow aquí.

Respondido por:

editado el 11 de diciembre de 2013 a las 4:14 John Paul

respondió Dec 11 '13 a las 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
fuente