Clever Geek Handbook

Courbes de Bézier. Un peu sur les intersections et aussi simple que possible

Avez-vous déjà rencontré la construction d'un chemin (continu) pour traverser une courbe dans un plan défini par des segments de ligne et des courbes de Bézier?



Cela ne semble pas être une tâche très difficile: joindre les segments des courbes en un seul chemin et en faire le tour "sans lever le stylo". Une courbe fermée se déplace dans une direction, les branches traversent en avant et en arrière et commencent et se terminent au même nœud.



Tout allait bien jusqu'à ce que des chemins monstrueux aient commencé à ramper sous les mains des concepteurs, où les courbes individuelles pouvaient se croiser ou ne pas s'accrocher exactement. L'explication était extrêmement simple - visuellement, ils mentent tous comme ils le devraient, et pour la machine qui contournera ce chemin, de tels écarts sont invisibles.



Fort de la connaissance de l'écart maximal admissible, j'ai commencé la recherche dont je souhaite partager les résultats.



La première chose que j'ai faite a été de comprendre comment les choses se passent aujourd'hui (octobre 2020) en trouvant les points d'intersection des courbes. Soit je cherchais au mauvais endroit, soit je demandais peut-être, mais je ne trouvais pas de solution simple. Cependant, l'idée avec la résultante d'une paire de polynômes est assez intéressante. De nombreux algorithmes différents liés aux courbes de Bézier sont rassemblés ici .



Ce que je n’ai pas aimé dans les méthodes connues et ce que je ne veux pas faire, c’est de rechercher numériquement les racines des polynômes, ou même de résoudre des équations quadratiques. Je ne veux vraiment pas explorer les courbes pour les extrêmes. Quoi qu'il en soit, je voudrais éviter la division, l'exponentiation et tout ce qui peut conduire à un comportement indéfini.



Exemple

, ,



Alors, avec quoi devez-vous travailler.



  • Les points sont spécifiés par type Point, comme ceci:



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


    Pour Pointles opérateurs d'addition, de soustraction, de multiplication par un scalaire, des multiplications scalaires sont définies.



  • La valeur de l' Récart admissible des points est définie.



  • Les courbes sont définies par des tableaux de points de contrôle (contrôle) std::vector<Point>.



  • Les courbes presque coïncidentes doivent être marquées et, si possible, supprimées, par exemple s'il s'agit d'un doublon oublié (le copier-coller est mal).





, , . ( ):



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. t1et t2peut être n'importe lequel:

    • subCurve(curve, 1, 0)donnera une courbe qui "se déplace" du point final au point curvede départ,
    • subCurve(curve, 1, 2)extrapole curveau-delà du dernier point d'ancrage.
  2. Certaines implémentations de méthodes sont volontairement omises car elles ne contiennent rien de particulièrement intéressant.
  3. La fonction point(curve, t)ne convient pas pour calculer de nombreux points sur une courbe (par exemple, pour la pixellisation); pour cela, le calcul à l'aide d'une matrice triangulaire est mieux adapté.


More articles:


All Articles