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

8

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.)

Justin C. Rounds
sumber
3
Untuk lebih jelasnya, Anda ingin titik-titiknya ditempatkan secara merata di sekelilingnya?
Tenpn

Jawaban:

6

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

Jonathan Fischoff
sumber
Wow ini lebih rumit dari yang saya kira! Jadi ya, pada dasarnya saya mencoba melakukan ini dengan exitordie.com/goodEllipse.gif (diambil dari utas ini bigresource.com/Tracker/Track-flash-DO1WzX6KNq ). Jika saya memahami ini dengan benar, itu berarti bahwa saya tidak ingin membuat poin sama panjangnya dengan busur.
Justin C. Rounds
Saya pikir Anda ingin memplot poin dengan jarak yang sama. Tidak ada formula yang bagus untuk keliling elips. Pada halaman mathoverflow ada tautan ke halaman ini en.wikipedia.org/wiki/Circumference yang memberikan perkiraan untuk keliling yang seharusnya bisa Anda gunakan.
Jonathan Fischoff
Pelajaran sebenarnya yang saya pikirkan adalah jika Anda ingin matematika menjadi sederhana secara umum, gunakan polinomial atau fungsi rasional. Elips tampak sederhana, tetapi memiliki sifat kompleks yang membuatnya sulit untuk dihitung. Polinomial sangat baik bahaved dan kurva perkiraan (seperti elips) sangat baik.
Jonathan Fischoff
6

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
(xx)²/a² + (yy)²/b² = 1

Menyingkirkan y dalam persamaan memberi:

Δy = b (sqrt(1 - (xx)²/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 :-)

sam hocevar
sumber
1
Saya auto-upvote untuk seni ASCII.
Jimmy
0

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).

dave
sumber
0

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

}
David S Alderson
sumber