Clever Geek Handbook

ベジエ曲線。交差点について少し、できるだけシンプルに

ラインセグメントとベジエ曲線によって定義された平面内の曲線を横断するための（連続的な）パスの構築に遭遇したことがありますか？



カーブのセグメントを1つのパスに結合し、「ペンを持ち上げずに」その周りを回るのは、それほど難しい作業ではないようです。閉じた曲線は一方向にトラバースし、分岐は前後にトラバースし、同じノードで開始および終了します。



巨大な小道がデザイナーの手の下から這い出し始めるまで、すべてが順調でした。そこでは、個々の曲線が交差するか、正確にドッキングしませんでした。説明は非常に単純でした。視覚的にはすべてが本来あるべき位置にあり、このパスをバイパスするマシンの場合、そのような逸脱は目に見えません。



最大許容偏差の知識を持って研究を開始し、その結果を共有したいと思います。



私が最初にしたことは、曲線の交点を見つけることで、今日（2020年10月）の状況を把握することでした。間違った場所を探していたか、尋ねていたのかもしれませんが、簡単な解決策を見つけることができませんでした。ただし、一対の多項式の結果を使用したアイデアは非常に興味深いものです。Bezier曲線に関連する多くの異なるアルゴリズムがここに集められています。



既知の方法について私が気に入らなかったこと、そしてやりたくないことは、多項式の根を数値的に検索すること、あるいは二次方程式を解くことです。私は本当に極端な曲線を探求したくありません。とにかく、分割、指数化、および未定義の動作につながる可能性のあるすべてのものを避けたいと思います。



例

, ,



それで、あなたは何と協力しなければなりませんか。



  • ポイントはPoint、次のようにタイプで指定されます。



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


    ためPointスカラーによる加算、減算、乗算の演算子、スカラー乗算が定義されています。



  • Rポイントの許容偏差の値が設定されます。



  • 曲線は、制御（制御）点の配列によって定義されますstd::vector<Point>。



  • ほぼ一致する曲線にマークを付け、可能であれば、たとえば、重複を忘れた場合は削除する必要があります（コピー＆ペーストは悪です）。





, , . ( ):



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. t1そして、t2任意にすることができます：

    • subCurve(curve, 1, 0)終点curveから始点に「移動」する曲線が得られます。
    • subCurve(curve, 1, 2)curve最後のアンカーポイントを超えて外挿します。
  2. 一部のメソッド実装は、特に興味深いものが含まれていないため、意図的に省略されています。
  3. この関数はpoint(curve, t)、曲線上の多くの点を計算するのには適していません（たとえば、ラスター化の場合）。このためには、三角行列を使用した計算の方が適しています。


More articles:


All Articles