Apa itu algoritma sederhana untuk menghitung titik yang terdistribusi secara merata pada sebuah elips?

Saya mencari algoritma sederhana untuk merencanakan titik-titik yang terdistribusi secara merata pada sebuah elips, mengingat sumbu utama dan minor. Ini sangat mudah dilakukan dengan lingkaran seperti:

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

(yang menciptakan titik yang jaraknya sama dengan titik tetangganya) tetapi saya tidak dapat menemukan atau mencari cara untuk melakukan ini pada elips. (Solusi di AS3 lebih disukai, tetapi tidak diperlukan.)

Parameterisasi ulang dengan panjang busur dan sampel seragam. Jika Anda perlu bantuan melakukan perhitungan, saya akan bertanya di sini:
https://math.stackexchange.com/

itu juga ditanyakan di sini: /mathpro/28070/finding-n-points-that-are-equidistant-around-the-circumference-of-an-ellipse

Perkiraan yang masuk akal

Seperti yang sudah dinyatakan dalam jawaban lain, tidak ada cara pasti untuk melakukan ini. Namun, adalah mungkin untuk memperkirakan solusi secara efisien.

Formula saya hanya akan menangani kuadran kanan atas . Berbagai perubahan tanda perlu diterapkan untuk menangani kuadran lain.

Biarkan d menjadi jarak busur yang Anda inginkan antara titik-titik berturut-turut. Misalkan titik diplot terakhir adalah pada (x, y) .

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

Kemudian titik selanjutnya harus diplot pada koordinat berikut:

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

Bukti

Biarkan titik berikutnya berada di (x + Δx, y + Δy) . Kedua poin memenuhi persamaan elips:

x²/a² + y²/b² = 1
(x+Δx)²/a² + (y+Δy)²/b² = 1

Menyingkirkan y dalam persamaan memberi:

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

Kami menganggap Δx cukup kecil, jadi kami mengganti f (x + Δx) -f (x) dengan f '(x) Δx menggunakan pendekatan linier untuk f' :

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

Jika d cukup kecil, maka Δx dan Δy cukup kecil dan panjang busur dekat dengan jarak euclidian antara titik-titik. Karenanya, perkiraan berikut ini valid:

Δx² + Δy² ~ d²

Kami mengganti iny di atas dan menyelesaikan untuk Δx :

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

Bagaimana jika d tidak cukup kecil?

Jika d terlalu besar untuk perkiraan di atas akan berlaku, cukup mengganti d dengan d / N , misalnya N = 3 , dan hanya merencanakan satu titik dari N .

Catatan akhir

Metode ini memiliki masalah pada ekstrema ( x = 0 atau y = 0 ), yang dapat ditangani dengan menggunakan perkiraan tambahan ( mis. Melewatkan titik terakhir kuadran, apakah itu sebenarnya diplot atau tidak).

Menangani seluruh elips mungkin akan lebih kuat dengan mengulang semuanya menggunakan koordinat kutub. Namun, ini pekerjaan, dan ini adalah pertanyaan lama, jadi saya hanya akan melakukannya jika ada minat dari poster aslinya :-)

Saya jenis tergantung persis apa yang Anda maksud dengan "merata". Saya menulis posting tentang menggunakan elips di permainan saya di sini: http://world-create.blogspot.com/2009/01/ellipse-maths.html

Dari pos:

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

Anda bisa mendapatkan titik yang ditempatkan secara merata di sekeliling elips dengan sudut dengan melakukan:

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

Tetapi tergantung pada spesifikasi elips Anda, nilai-nilai ini dapat dikumpulkan (jika ada ujung "runcing" ke elips).

Jawabannya, dengan kode Java lengkap terletak di StackOverflow di sini

Dijawab oleh:

diedit 11 Des '13 jam 4:14 John Paul

jawab 11 Des 13 pada 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;
}

}