Panjang kurva kurva Bezier

23

Lihat juga: pertanyaan yang sama di Math.SE

Bagaimana saya bisa menemukan arclength dari kurva Bezier? Misalnya, kurva Bezier linier memiliki panjang:

length = sqrt(pow(x[1] - x[0], 2) + pow(y[1] - y[0], 2));

Tapi bagaimana dengan kurva Bezier kuadratik, kubik, atau n-derajat?

(Tujuan saya adalah memperkirakan resolusi pengambilan sampel sebelumnya, jadi saya tidak perlu membuang waktu memeriksa jika titik berikutnya menyentuh titik sebelumnya.)

Mateen Ulhaq
sumber
1
Anda harus menulis ulang pertanyaan untuk merujuk pada panjang kurva, yang merupakan istilah yang jauh lebih mudah (dan dapat dicari).
Sparr
Saya sarankan memposting ini pada matematika, saya yakin beberapa wajah pintar di sana akan memberi Anda jawaban di salah satu dari mereka font web pintar: p
Tor Valamo
2
@Tor saya lakukan (kemarin), tapi saya sudah diberitahu itu sangat rumit, dan karenanya tidak taktis. [ math.stackexchange.com/q/12186/2736 ]
Mateen Ulhaq
Seharusnya kurva / splines clothoid adalah alternatif untuk beziers, dan memiliki ekspresi arclength bentuk tertutup, tapi saya belum tahu banyak tentang ini. (Mencoba menghasilkan titik jarak yang sama di sepanjang kurva.) Catenary juga memiliki ekspresi panjang busur bentuk tertutup?
endolith

Jawaban:

9

Cara sederhana untuk Beziers kubik adalah dengan membagi kurva menjadi segmen N dan menjumlahkan panjang segmen.

Namun, segera setelah Anda membutuhkan panjang hanya bagian dari kurva (misalnya hingga 30% dari panjang sepanjang), parameterisasi panjang busur akan ikut berperan. Saya memposting jawaban yang cukup panjang pada salah satu pertanyaan saya sendiri tentang Béziers, dengan kode contoh sederhana.

Ivo Wetzel
sumber
Saya melakukan ini untuk LEGO Mindstorms NXT, yang memiliki prosesor yang sangat lemah (48Mhz), jadi saya perlu kecepatan sebanyak mungkin. Saya akan mengambil pendekatan pembagian untuk menghemat beberapa kecepatan, dan mendapatkannya cukup akurat (untuk rendering non-realtime). Saya juga memiliki opsi di mana Anda dapat mengatur nilai 1.0/t(disebut resolution), jadi itu untuk "realtime" (yang terbaik 10fps pada NXT lambat). Setiap iterasi,, t += resolutiondan titik / garis baru ditarik. Bagaimanapun, terima kasih untuk idenya.
Mateen Ulhaq
4

Walaupun saya sudah setuju dengan jawaban yang sudah Anda dapatkan, saya ingin menambahkan mekanisme perkiraan sederhana namun kuat yang dapat Anda gunakan untuk kurva Bézier derajat apa pun: Anda terus membagi kurva menggunakan subdivisi de Casteljau hingga jarak maksimum dari titik kontrol dari sub-kurva ke baseline sub-kurva di bawah beberapa epsilon konstan . Dalam hal itu, sub-kurva dapat diperkirakan dengan garis dasarnya.

Sebenarnya, saya percaya ini adalah pendekatan yang biasanya diambil ketika subsistem grafis harus menggambar kurva Bézier. Tetapi jangan mengutip saya tentang hal ini, saya tidak memiliki referensi saat ini.

Dalam praktiknya akan terlihat seperti ini: (kecuali bahasanya tidak relevan)

public static Line[] toLineStrip(BezierCurve bezierCurve, double epsilon) {
    ArrayList<Line> lines = new ArrayList<Line>();

    Stack<BezierCurve> parts = new Stack<BezierCurve>();
    parts.push(bezierCurve);

    while (!parts.isEmpty()) {
        BezierCurve curve = parts.pop();
        if (distanceToBaseline(curve) < epsilon) {
            lines.add(new Line(curve.get(0), curve.get(1)));
        } else {
            parts.addAll(curve.split(0.5));
        }
    }

    return lines.toArray(new Line[0]);
}
Matthias
sumber
Meskipun ini adalah pendekatan yang baik, saya pernah mendengar tentang ketidakstabilan numerik pada kurva Bezier tingkat tinggi, yang membutuhkan ide lain: memecah kurva tingkat tinggi menjadi kurva kubik yang lebih kecil.
Mateen Ulhaq
Juga, jika tujuan akhir adalah perkiraan yang akurat, mungkin ide yang baik untuk memperkirakan dengan kuadratik alih-alih garis untuk memastikan bahwa kami tidak mengecilkan perkiraan kami di lokasi dengan lengkungan tinggi.
Mateen Ulhaq
2

Panjang busur untuk kurva Bezier hanya bentuk tertutup untuk yang linier dan kuadratik. Untuk kubik, itu tidak dijamin memiliki solusi tertutup. Alasannya adalah panjang busur didefinisikan oleh integral radikal, yang memiliki tertutup hanya untuk polinomial tingkat 2.

Hanya untuk referensi: Panjang Bezier kuadratik untuk poin (a, p) (b, q) dan (c, r) adalah

(a ^ 2 · (q ^ 2 - 2 · q · r + r ^ 2) + 2 · a · (r - q) · (b · (p - r) + c · (q - p)) + ( b · (p - r) + c · (q - p)) ^ 2) · LN ((^ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · √ (a ^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) + a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) / (^ (a ^ 2 + 2 · A · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · q + r) ^ 2) · √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) + a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2) ^ (3/2) + (√ (a ^ 2 - 2 · a · b + b ^ 2 + p ^ 2 - 2 · p · q + q ^ 2) · (a ^ 2 + a · (c - 3 · b) + 2 · b ^ 2 - b · c + (p - q) · (p - 2 · q + r)) - √ (b ^ 2 - 2 · b · c + c ^ 2 + q ^ 2 - 2 · q · r + r ^ 2) · (a · (b - c) - 2 · b ^ 2 + 3 · b · c - c ^ 2 + (p - 2 · q + r) · (q - r))) / (a ​​^ 2 + 2 · a · (c - 2 · b) + 4 · b ^ 2 - 4 · b · c + c ^ 2 + (p - 2 · Q + r) ^ 2)

Di mana LN adalah logaritma natural, dan ^ menunjukkan kekuatan dan root akar kuadrat.

Oleh karena itu, seharusnya lebih mudah dan lebih murah memperkirakan busur dengan aturan lain, seperti poligon atau skema integrasi seperti aturan Simpson, karena akar kuadrat LN adalah operasi yang mahal.

Robert
sumber
2

Saya mengerjakan bentuk ekspresi tertutup panjang untuk Bezier 3 poin (di bawah). Saya belum mencoba mencari formulir tertutup untuk 4+ poin. Ini kemungkinan besar akan sulit atau rumit untuk diwakili dan ditangani. Namun, teknik pendekatan numerik seperti algoritma integrasi Runge-Kutta akan bekerja cukup baik dengan mengintegrasikan menggunakan rumus panjang busur . T&J saya tentang RK45 tentang MSE dapat membantu implementasi RK45.

Berikut adalah beberapa kode Java untuk panjang busur dari 3 titik Bezier, dengan poin a, bdan c.

    v.x = 2*(b.x - a.x);
    v.y = 2*(b.y - a.y);
    w.x = c.x - 2*b.x + a.x;
    w.y = c.y - 2*b.y + a.y;

    uu = 4*(w.x*w.x + w.y*w.y);

    if(uu < 0.00001)
    {
        return (float) Math.sqrt((c.x - a.x)*(c.x - a.x) + (c.y - a.y)*(c.y - a.y));
    }

    vv = 4*(v.x*w.x + v.y*w.y);
    ww = v.x*v.x + v.y*v.y;

    t1 = (float) (2*Math.sqrt(uu*(uu + vv + ww)));
    t2 = 2*uu+vv;
    t3 = vv*vv - 4*uu*ww;
    t4 = (float) (2*Math.sqrt(uu*ww));

    return (float) ((t1*t2 - t3*Math.log(t2+t1) -(vv*t4 - t3*Math.log(vv+t4))) / (8*Math.pow(uu, 1.5)));
Pixel
sumber