O que é um algoritmo simples para calcular pontos uniformemente distribuídos em uma elipse?

8

Eu estou procurando um algoritmo simples para plotar pontos uniformemente distribuídos em uma elipse, dados os eixos maiores e menores. Isso é realmente fácil de fazer com um círculo como este:

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 cria pontos à mesma distância dos pontos vizinhos), mas não consigo encontrar ou descobrir uma maneira de fazer isso em uma elipse. (As soluções no AS3 são preferidas, mas não necessárias.)

Justin C. Rounds
fonte
3
Só para esclarecer, você quer que os pontos sejam espaçados uniformemente em relação à circunferência?
27410 dezpn

Respostas:

6

Re-parametrize-o pelo comprimento do arco e faça a amostra uniformemente. Se você precisar de ajuda para fazer as contas, eu pediria aqui:
https://math.stackexchange.com/

também foi solicitado aqui: /mathpro/28070/finding-n-points-that-are-equidistant-around-the-circumference-of-an-ellipse

Jonathan Fischoff
fonte
Uau, isso é mais complicado do que eu pensava! Então, sim, basicamente estou tentando fazer isso quitordie.com/goodEllipse.gif (extraído deste tópico bigresource.com/Tracker/Track-flash-DO1WzX6KNq ). Se estou entendendo isso corretamente, significa que não pretendo tornar os pontos equidistantes pelo comprimento do arco.
Justin C. Rounds
Eu acho que você deseja plotar os pontos equidistantes pelo comprimento do arco. Simplesmente não existe uma boa fórmula para a circunferência de uma elipse. Na página mathoverflow, há um link para esta página en.wikipedia.org/wiki/Circumference que fornece aproximações para a circunferência que você deve poder usar.
Jonathan Fischoff
A verdadeira lição que penso é que, se você deseja que a matemática seja simples em geral, use polinômios ou funções racionais. As elipses parecem simples, mas têm propriedades complexas que as tornam difíceis de calcular. Os polinômios são muito bem comportados e as curvas aproximadas (como elipses) muito bem.
Jonathan Fischoff
6

Aproximação razoável

Como já foi dito em outras respostas, não há maneira exata de fazer isso. No entanto, é possível aproximar eficientemente uma solução.

Minha fórmula manipulará apenas o quadrante superior direito . Várias alterações de sinal precisarão ser aplicadas para lidar com outros quadrantes.

Seja d a distância desejada do arco entre pontos consecutivos. Suponha que o último ponto plotado esteja em (x, y) .

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

Em seguida, o próximo ponto deve ser plotado nas seguintes coordenadas:

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

Prova

Seja o próximo ponto em (x + Δx, y + Δy) . Ambos os pontos satisfazem a equação da elipse:

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

Livrar-se de y nas equações fornece:

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

Assumimos que Δx é pequeno o suficiente, então substituímos f (x + Δx) -f (x) por f '(x) Δx usando a aproximação linear para f' :

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

Se d é pequeno o suficiente, então Δx e Δy são pequenos o suficiente e o comprimento do arco está próximo da distância euclidiana entre os pontos. A seguinte aproximação é, portanto, válida:

Δx² + Δy² ~ d²

Substituimos Δy acima e resolvemos para Δx :

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

E se d não for pequeno o suficiente?

Se d for muito grande para as aproximações anteriores para ser válida, simplesmente substituir d com d / N , por exemplo, N = 3 , e só traçar um ponto de N .

Nota final

Este método tem problemas em extremos ( x = 0 ou y = 0 ), que podem ser tratados usando aproximações adicionais ( ou seja, pular o último ponto do quadrante, seja ele realmente plotado ou não).

O manuseio de toda a elipse provavelmente será mais robusto refazendo tudo usando coordenadas polares. No entanto, é um pouco de trabalho, e essa é uma pergunta antiga, então só o farei se houver algum interesse no pôster original :-)

sam hocevar
fonte
11
Voto automaticamente para arte ASCII.
Jimmy
0

Eu meio que depende exatamente o que você quer dizer com "uniformemente". Eu escrevi um post sobre o uso de elipses no meu jogo aqui: http://world-create.blogspot.com/2009/01/ellipse-maths.html

Da postagem:

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

Você pode obter pontos espaçados uniformemente ao redor da elipse por ângulo , fazendo:

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

Mas, dependendo das especificidades da sua elipse, esses valores podem ser agrupados (se houver um final "pontudo" na elipse).

Dave
fonte
0

A resposta, com código Java completo, está localizada no StackOverflow aqui

Respondida por:

editou Dec 11 '13 às 4:14 John Paul

respondeu Dec 11 '13 às 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
fonte