2

4 点で定義された 3 次ベジエがあります。接線が特定のベクトルに等しい 3 次ベジエに沿って時間 t を見つける必要があります。この問題は一見したように単純ではありません。最初に基本的な数学を説明して、どのようにアプローチしたかを説明します。これにより、欠陥と、おそらくより良い解決策を見つけることができます。

2D キュービック ベジエとその接線は、次の方程式で定義できます。具体的には接線:

T(t) = -3(1-t)^2 * P0 + 3(1-t)^2 * P1 - 6t(1-t) * P1 - 3t^2 * P2 + 6t(1-t) * P2 + 3t^2 * P3

2D ベクトル用に展開します。

T_x(t) = -3(1-t)^2 * x0 + 3(1-t)^2 * x1 - 6t(1-t) * x1 - 3t^2 * x2 + 6t(1-t) * x2 + 3t^2 * x3
T_y(t) = -3(1-t)^2 * y0 + 3(1-t)^2 * y1 - 6t(1-t) * y1 - 3t^2 * y2 + 6t(1-t) * y2 + 3t^2 * y3

次に、時間 t を求めたい接線を表すベクトル (x, y) もあります。

これらは単純な 2 次方程式なので、方程式を解くだけで済みます。2 つの外積 (vx0 * vy1 - vy0 * vx1) を取り、0 について解くことができます。これにより、3 次ベジエのタンジェントが与えられたタンジェント ベクトルと等しい場合がわかり、t について解くことができます。(ベクトルが接線の反対側にあるかどうかは気にしないので、ベクトルが (1, 0) の場合は (-1, 0) も検索します)。Mathematica では、この外積アプローチを使用して t を解くと、次のようになります。

Solve[(-3(1-t)^2*x0+3(1-t)^2*x1-6t(1-t)*x1-3t^2*x2+6t(1-t)*x2+3t^2*x3)*y-(-3(1-t)^2*y0+3(1-t)^2*y1-6t(1-t)*y1-3t^2*y2+6t(1-t)*y2+3t^2*y3)*x==0,t,Reals]

Mathematica は次のように出力します:

{{t->ConditionalExpression[(x0 y-2 x1 y+x2 y-x y0+2 x y1-x y2)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)-\[Sqrt]((x1^2 y^2-x0 x2 y^2-x1 x2 y^2+x2^2 y^2+x0 x3 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x0 y y2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2-x x0 y y3+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)^2),(x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&y2<y3)||(x<(x2 y-x3 y)/(y2-y3)&&y<0&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&y2<y3&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&x>(x2 y-x3 y)/(y2-y3)&&y2>y3)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&y>0)||(y<0&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3))]},

{t->ConditionalExpression[(x0 y-2 x1 y+x2 y-x y0+2 x y1-x y2)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)+\[Sqrt]((x1^2 y^2-x0 x2 y^2-x1 x2 y^2+x2^2 y^2+x0 x3 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x0 y y2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2-x x0 y y3+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x0 y-3 x1 y+3 x2 y-x3 y-x y0+3 x y1-3 x y2+x y3)^2),(x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&y2<y3)||(x<(x2 y-x3 y)/(y2-y3)&&y<0&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2>y3)||(x<(x2 y-x3 y)/(y2-y3)&&y2<y3&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y>0)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y<0&&x>(x2 y-x3 y)/(y2-y3)&&y2>y3)||(x0<(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3)&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&y>0)||(y<0&&y2<y3&&x>(x2 y-x3 y)/(y2-y3)&&x0>(x1^2 y^2-x1 x2 y^2+x2^2 y^2-x1 x3 y^2+x x2 y y0-x x3 y y0-2 x x1 y y1+x x2 y y1+x x3 y y1+x^2 y1^2+x x1 y y2-2 x x2 y y2-x^2 y0 y2-x^2 y1 y2+x^2 y2^2+x x1 y y3+x^2 y0 y3-x^2 y1 y3)/(x2 y^2-x3 y^2-x y y2+x y y3))]}}

こちらが見やすい画像です。つまり、これらのケースのほとんどは変数が重複しているため、見た目よりもはるかに単純です。(両方の条件ケースは同一であり、二次方程式を解いたため、解は方程式の正または負のケースです)。コード形式では、これは簡単に確認できます。

var temp1 = (tx2 - tx3) / (y2 - y3);
var temp2 = (tx1 * tx1 + tx2 * tx2 + tx2 * (ty0 + ty1 - 2 * ty2) + tx1 * (-tx2 - tx3 - 2 * ty1 + ty2 + ty3) + tx3 * (ty1 - ty0) + ty1 * ty1 - ty0 * ty2 + ty2 * ty2 + ty0 * ty3 - ty1 * (ty2 + ty3)) / (tangent.y * (tx2 - tx3 - ty2 + ty3));
console.log ('Temp1: ', temp1, ' Temp2: ', temp2);
if
(
    tangent.x < temp1 &&
    (
        tangent.y < 0 && 
        (
            x0 < temp2 && y2 < y3 ||
            x0 > temp2 && y2 > y3
        ) ||
        tangent.y > 0 &&
        (
            x0 < temp2 && y2 > y3 ||
            x0 > temp2 && y2 < y3
        )
    ) ||
    tangent.x > temp1 &&
    (
        tangent.y < 0 &&
        (
            x0 < temp2 && y2 > y3 ||
            x0 > temp2 && y2 < y3
        ) ||
        tangent.y > 0 &&
        (
            x0 < temp2 && y2 < y3 ||
            x0 > temp2 && y2 > y3
        )
    )
)
{
    var tx0ty0 = tx0 - ty0;
    var ty1tx1 = ty1 - tx1;
    var tx2ty2 = tx2 - ty2;

    var temp6 = 2 * (tx0ty0 + tx2ty2) + 4 * ty1tx1;
    var temp5 = tx0ty0 + 3 * (tx2ty2 + ty1tx1) + ty3 - tx3;
    var temp7 = temp6 * temp6 - 4 * (tx0ty0 + ty1tx1) * temp5;
    var temp3 = Math.sqrt(temp7);
    var temp4 = 2 * temp5;
    var t1 = (temp6 - temp3) / temp4;
    var t2 = (temp6 + temp3) / temp4;
}

問題が 2 次であるため、予想どおり 2 つの可能な時間が得られます。JS でのインタラクティブな例を次に示します。この例では、ハードコーディングされた (0.707, 0.707) の正接ベクトルを使用しています。(つまり、その座標系で下向きと右向きのベクトル)。

ただし、上記のコードには問題があります。不等式と平方根の計算で浮動小数点エラーを修正しても、明確に定義されていない場合があります。y2 - y3 が 0 の場合と同様に、ゼロ除算になります。これには微妙な点もあります。特定のケースでは、temp4 の有効な結果がゼロに非常に近くなり、正しい結果が生成されるか、浮動小数点の問題が原因で t1 と t2 の値が予想よりもはるかに大きくなります。これは、t1 または t2 が 0.5 の場合に特に気付きました。対角線をひっくり返してもう一度解くと、いくつかのエッジケースが解決する可能性があると考えていましたが、そのアプローチには自信がありません.

私が望むのは、おそらくコード例を使用した、試行錯誤されたアプローチ、または奇妙なエッジケースなしでこれに取り組む別の方法です。

4

1 に答える 1

3

この問題には、いくつかの特殊なケースが考えられます。たとえば、ベジエ アークがカスプを形成したり、直線や単一の点になったりすることもあります (すべての制御点が同一であると考えてください)。特殊なケースのない単一の直接式を持つことは不可能です。

として定義されているtx*y'(t) - ty*x'(t) = 0場所として問題を提起し(および同様に)、取得した Maxima で解決します。x'(t)a_x*t^2 + b_x*t + c_xy

ここに画像の説明を入力

と

ここに画像の説明を入力

一般的なケースの 2 つのソリューションとして。

もちろん、分母がゼロでない場合にのみ有効であり、この場合、方程式の解は次のように簡略化されます。

ここに画像の説明を入力

この計算の Javascript 実装は次のとおりです。

tvals = []; // Array of solutions
var den = 2*ax*ty - 2*ay*tx;
if (Math.abs(den) < 1E-10) {
    var num = ax*cy - ay*cx;
    var den = ax*by - ay*bx;
    if (den != 0) {
        var t = -num / den;
        if (t >= 0 && t <= 1) tvals.push(t);
    }
} else {
    var delta = (bx*bx - 4*ax*cx)*ty*ty + (-2*bx*by + 4*ay*cx + 4*ax*cy)*tx*ty + (by*by - 4*ay*cy)*tx*tx;
    var k = bx*ty - by*tx;
    tvals = [];
    if (delta >= 0 && den != 0) {
        var d = Math.sqrt(delta);
        var t0 = -(k + d) / den;
        var t1 = (-k + d) / den;
        if (t0 >= 0 && t0 < 1) tvals.push(t0);
        if (t1 >= 0 && t1 < 1) tvals.push(t1);
    }
}

http://raksy.dyndns.org/beztan.htmlでインタラクティブな例を確認するか、 https ://youtu.be/5PKQUtytrlQでビデオを確認できます。

于 2016-01-17T10:31:19.650 に答える