Clever Geek Handbook

Kurva Bezier. Sedikit tentang persimpangan dan sesederhana mungkin

Pernahkah Anda menemukan membangun jalur (kontinu) untuk melintasi kurva dalam bidang yang ditentukan oleh segmen garis dan kurva Bezier?



Tampaknya bukan tugas yang sangat sulit: menggabungkan segmen kurva dalam satu jalur dan memutarnya "tanpa mengangkat pena". Kurva tertutup melintasi satu arah, cabang-cabang melintasi ke depan dan ke belakang, dan mulai dan berakhir pada simpul yang sama.



Semuanya baik-baik saja sampai jalur mengerikan mulai merangkak keluar dari bawah tangan para desainer, di mana kurva individu dapat berpotongan atau tidak persis berlabuh. Penjelasannya sangat sederhana - secara visual semuanya berbohong sebagaimana mestinya, dan untuk mesin yang akan melewati jalur ini, penyimpangan semacam itu tidak terlihat.



Berbekal pengetahuan tentang penyimpangan maksimum yang diizinkan, saya memulai penelitian, yang hasilnya ingin saya bagikan.



Hal pertama yang saya lakukan adalah mencari tahu bagaimana keadaan hari ini (Oktober 2020) dengan menemukan titik persimpangan kurva. Entah saya mencari di tempat yang salah, atau mungkin saya bertanya, tetapi saya tidak dapat menemukan solusi sederhana. Meskipun, gagasan dengan resultan sepasang polinomial cukup menarik. Banyak algoritme berbeda yang terkait dengan kurva Bezier dikumpulkan di sini .



Yang tidak saya sukai tentang metode yang diketahui dan yang tidak ingin saya lakukan adalah menelusuri akar polinomial secara numerik, atau bahkan menyelesaikan persamaan kuadrat. Saya benar-benar tidak ingin menjelajahi kurva yang ekstrem. Bagaimanapun, saya ingin menghindari pembagian, eksponensial, dan segala sesuatu yang dapat menyebabkan perilaku tidak terdefinisi.



Contoh

, ,



Jadi apa yang harus Anda kerjakan.



  • Poin ditentukan berdasarkan jenis Point, seperti ini:



    using Point = std::array<double, 2>;


    Untuk Pointoperator penjumlahan, pengurangan, perkalian dengan skalar, perkalian skalar didefinisikan.



  • Nilai Rpenyimpangan poin yang dapat diterima ditetapkan.



  • Kurva ditentukan oleh array titik kontrol (kontrol) std::vector<Point>.



  • Kurva yang hampir bersamaan harus ditandai dan, jika mungkin, dihapus, misalnya, jika itu adalah duplikat yang terlupakan (salin-tempel itu jahat).





, , . ( ):



Point point(const std::vector<Point> &curve, double t, int n, int i)
{
    return n == 0 ? curve[i] : (point(curve, t, n - 1, i - 1) * (1 - t) + point(curve, t, n - 1, i) * t);
}


— , :



Point point(const std::vector<Point> &curve, double t)
{
    return point(curve, t, curve.size() - 1, curve.size() - 1);
}


, curve — : , .



— - , R:



template <>
struct std::less<Point>
{
    bool operator()(const Point &a, const Point &b, const double edge = R) const
    {
        for (auto i = a.size(); i-- > 0;) {
            if (a[i] + edge < b[i])
                return true;
            if (a[i] > b[i] + edge)
                return true;
        }
        return false;
    }
};


. , , , . — :



struct Rect
{
    Point topLeft, bottomRight;
    Rect(const Point &point);
    Rect(const std::vector<Point> &curve);
    bool isCross(const Rect &rect, const double edge) const
    {
        for (auto i = topLeft.size(); i-- > 0;) {
            if (topLeft[i] > rect.bottomRight[i] + edge
                || bottomRight[i] + edge < rect.topLeft[i])
                return false;
        }
        return true;
    }
};




void find(const std::vector<Point> &curveA, const std::vector<Point> &curveB,
          double tA, double tB, double dt)
{


1. , . 
    if (m_isSimilarCurve)
        return;


2. , 
    Rect aRect(curveA);
    Rect bRect(curveB);
    if (!aRect.isCross(bRect, R))
        return;


3. R/2, , 
    if (isNear(aRect.tl, aRect.br, R / 2) && isNear(bRect.tl, bRect.br, R / 2)) {
        // 3.1        
        addBest(curveA.front(), curveA.back(), curveB.front(), curveB.back(), tA, tB, dt);
        m_isSimilarCurve = (m_result.size() > curveA.size() * curveB.size());
        return;
    }


4. 
    const auto curveALeft = subCurve(curveA, 0, 0.5);
    const auto curveARight = subCurve(curveA, 0.5, 1.0);
    const auto curveBLeft = subCurve(curveB, 0, 0.5);
    const auto curveBRight = subCurve(curveB, 0.5, 1.0);


5. 
    const auto dtHalf = dt / 2;
    find(curveALeft, curveBLeft, tA, tB, dtHalf);
    find(curveALeft, curveBRight, tA, tB + dtHalf, dtHalf);
    find(curveARight, curveBLeft, tA + dtHalf, tB, dtHalf);
    find(curveARight, curveBRight, tA + dtHalf, tB + dtHalf, dtHalf);


}


- : , t t1 t2?



t = (t2 - t1) t' + t1 . t = t1, t = t2. , ( ) . : k t2 t1, k:



Point point(const std::vector<Point> &curve, double t1, int n, int i, double t2, int k)
{
    return n > k ? (point(curve, t1, n - 1, i - 1, t2, k) * (1 - t2) +
                    point(curve, t1, n - 1, i, t2, k) * t2)
                 : point(curve, t1, n, i);
}


, :



std::vector<Point> subCurve(const std::vector<Point> &curve, double t1, double t2)
{
    std::vector<Point> result(curve.size());
    for (auto k = result.size(); k-- > 0;) {
        result[k] = point(curve, t1, curve.size() - 1, curve.size() - 1, t2, curve.size() - 1 - k);
    }
    return result;
}


, , .



.



  1. t1dan t2bisa apa saja:

    • subCurve(curve, 1, 0)akan memberikan kurva yang "bergerak" dari titik akhir curveke titik awal,
    • subCurve(curve, 1, 2)mengekstrapolasi curvemelampaui titik jangkar terakhir.
  2. Beberapa implementasi metode sengaja dihilangkan karena tidak mengandung sesuatu yang menarik.
  3. Fungsi ini point(curve, t)tidak cocok untuk menghitung banyak titik pada kurva (misalnya, untuk rasterisasi); untuk ini, lebih cocok untuk menghitung menggunakan matriks segitiga.


More articles:


All Articles