5

したがって、3D キュービック ベジエ カーブと、カーブに沿った任意の場所に開始ポイントがあり、最初のポイントから特定のワールド空間距離 (弧の長さの距離ではない) 離れたカーブのさらに下にある 2 番目のポイントを見つける必要があります。

もう 1 つの問題は、2 番目の点が曲線の終点に到達しても、まだ目的のワールド空間距離にない場合です。この場合、距離に到達するまで接線に沿って継続する必要があります。

何か案は？

4

2 に答える 2

2

悲しいかな、私はあなたが望む点を与える閉形式の方程式を知りません。おそらく、その点を近似する最も簡単な手法は、 de Casteljau のアルゴリズムを使用して、ベジエ曲線を 2 つの小さなベジエ曲線に再帰的に切り刻むこと です。(a) 曲線のすべての境界点が指定された点に近すぎるか遠すぎる場合、または (b) 曲線のすべての境界点が「十分に近い」場合、再帰は底をつきます。必要な距離 (おそらくそれらはすべて同じピクセル内に収まります)。

特定のポイントから特定の直線距離にある特定のベジエ曲線上のポイントの最大数は4ポイントであると確信しています。(これは、指定されたベジエ曲線に自己交差がある場合に発生する可能性があります)。

編集：

おそらく、回答に飛び込む前に質問全体を読む必要がありますか? 標準の「4 ポイント」ベジエ曲線セグメントは、無限に長い 3 次曲線の 1 つの部分と見なすことができます。1 つの場所に曲がり、ループ、または先端がある場合がありますが、その鋭いカーブから十分に離れた場所では、パスは 2 つの直線に近くなり、それぞれが任意の方向を指します。残念ながら、上記の解決策では、短いベジエ曲線セグメント上にあるポイントのみが検出されます。短いベジエ曲線セグメント上になくても、指定されたポイントから指定された距離にある無限に長いキュービック カーブに沿ったポイントが必要であると想定しています。

== 逆のカステルジョー ==

(再帰的な中間点) de Casteljau のアルゴリズムを逆に実行し、目的の点を含めるのに十分な大きさになるまで、反復ごとに最後のサイズの「2 倍」の新しい 4 点ベジエ曲線を生成できます。(4 つの初期ポイントすべてが指定されたポイントに「近すぎる」場合、2 倍にすることで、最終的に始点が「近すぎる」、終点が「遠すぎる」曲線セグメントが生成されることが保証されます。その後、上記を使用できます。アルゴリズムを使用して、指定されたポイントから目的の距離だけ離れたポイントに収束します)。このアプローチは、足し算、引き算、2 の掛け算、および平均化のみに依存するため、原則として、比較的数値的に堅牢である必要があります。(どの位置 t においても実際に 3 次式を評価することはありません)。

== ゼロ発見 ==

4 点表現から 3 次多項式表現に変換し、任意の根探索アルゴリズムを使用して目的の点の 1 つに収束させることができます。ベジエ曲線の短い部分はほぼ直線であるため、ニュートンの方法はかなりうまく機能するはずです。点と 3 次スプライン間の最小距離の検出のニュートン法方程式 をこの問題に適用できますか? 説明を簡単にするために二分アルゴリズムを使用しますが、これはニュートン法よりも遅く実行されます。

いつものように、3 次ベジエ曲線セグメントは次のように記述できます。

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3.

(残念ながら、この方程式は常に数値的に堅牢であるとは限りません。そのため、多くの人が代わりに de Casteljau のアルゴリズムを使用して再帰的半減を使用しています)。

指定されたポイントの t_given 値を持っている (または見つけることができる) と仮定しています。

x_given = B(t_given).x
y_given = B(t_given).y

与えられた点と曲線に沿った他の点との間の距離は、ピタゴラスの定理によって与えられます。

distance2(t) = ( x_given - B(t).x )^2 + ( y_given - B(t).y )^2.
distance(t) = sqrt(distance2(t)).

探しているポイントは関数のゼロにあります

given_distance2 = given_distance^2.
f(t) = distance2(t) - given_distance2.

指定された距離がゼロではなく、指定されたポイントの t_given < 1 であると仮定すると、二分アルゴリズムは次のように実行されます。

left = t_given
right = 1 // the endpoint of the given Bezier curve segment
while( distance2(right) < given_distance2 ){
    right = right*2
}

この時点で、t_left は目的の距離よりも指定されたポイントに近く、t_right は目的の距離よりも離れています (または正確に等しい場合もあります)。1 つのポイントが近すぎて、別のポイントが遠すぎるため、二分アルゴリズムが機能するはずです。

while( (abs(f(right) is too big) AND (abs(left - right) is too big) ){
    // find midpoint
    midpoint = (t_left + t_right)/2

次にチェックします: 最初のセグメント left...midpoint にゼロまたは midpoint...right が含まれていますか?

    if( f(left)*f(midpoint) < 0 ) then
        // throw away right half
        right = midpoint
    else
        // throw away left half
        left = midpoint
}

return( right )

この時点で、「右」の値は t の値であり、B(right) は対応する点であり、その点から元の指定された点までの距離は (ほぼ) 指定された距離になります。

于 2010-09-13T17:03:41.560 に答える
1

問題のステートメントには、もう少し洗練が必要です。具体的には、開始点 A から N 単位離れた点 B を求める場合、制約が不足しています。A から N の距離にある複数の点が存在する可能性があります。

それはさておき、曲線に沿って設定された間隔で曲線をサンプリングし、A までの直線距離を計算することを妨げているのは、最適ではありませんが、うまくいくでしょう。N距離離れた複数のポイントを処理するには、ルールを考え出す必要があります。最初に見つかったポイントと同じくらい簡単かもしれません。

于 2010-09-12T20:01:51.900 に答える