10

ポイント (マウスの位置) が、一連の B-スプライン コントロール ポイントによって定義された曲線上または近くにあるときを判断したいと考えています。

B スプラインに関する情報は、n 個のコントロール ポイント (x、y 座標) のリストです。制御点のリストは、任意の長さ (>= 4) にすることができ、(n−1)/3 の 3 次ベジエ曲線で構成される B スプラインを定義します。ベジエ曲線はすべて 3 次曲線です。曲線の「近く」に定義された距離のパラメータ k,(ピクセル単位) を設定したいと考えています。マウスの位置が曲線の k ピクセル以内にある場合は true、それ以外の場合は false を返す必要があります。

この情報を提供するアルゴリズムはありますか。どのソリューションも正確である必要はありません。1 ピクセル (または座標) の許容誤差で作業しています。

次の質問が役立つようですが、正確な質問には答えていません。特に、最初のリファレンスは 4 つのコントロール ポイントのみのソリューションのようであり、定義したい近さ係数が考慮されていません。

ベジエ曲線に対する点の位置

ベジエ曲線と線分との交点

編集: 曲線の例:

 e, 63.068, 127.26   
    29.124, 284.61   
    25.066, 258.56   
    20.926, 212.47   
        34, 176  
    38.706, 162.87  
    46.556, 149.82  
    54.393, 138.78

フォーマットの説明は次のとおりです。「すべてのエッジには、3n + 1 の位置のリストで構成される pos 属性が割り当てられます。これらは B スプライン制御点です。点 p0、p1、p2、p3 は最初のベジエ スプライン、p3 です。 , p4, p5, p6 は秒など. ポイントはコンマで区切られた 2 つの整数で表され, ポイント (1/72 インチ) で指定された位置の X 座標と Y 座標を表します. pos 属性では、制御点のリストは、開始点 ps および/または終了点 pe の前にある場合があります。これらは、それぞれ「s」または「e」接頭辞が付いた通常の位置表現を持っています。

EDIT2：「e」ポイント（および存在する場合はs）の詳細説明。

pos 属性では、制御点のリストの前に始点 ps および/または終点 pe が続く場合があります。これらは、それぞれ「s」または「e」の接頭辞が付いた通常の位置表現を持っています。p0 に矢印がある場合、始点が存在します。この場合、矢印は p0 から ps に向かっており、ps は実際にはノードの境界上にあります。矢じりの長さと方向はベクトル (ps −p0) で与えられます。矢印がない場合、p0 はノードの境界上にあります。同様に、点 pe は、エッジのもう一方の端にある矢印を指定し、最後のスプライン点に接続します。

4

3 に答える 3

11

これを分析的に行うこともできますが、少し計算が必要です。

ベジェ曲線は、バーンスタイン基底で表すことができます。ここでは 、関連する数学を適切にサポートするMathematicaを使用します。

だからあなたがポイントを持っているなら： 

pts = {{0, -1}, {1, 1}, {2, -1}, {3, 1}};

式。ベジェ曲線の場合： 

f[t_] := Sum[pts[[i + 1]] BernsteinBasis[3, i, t], {i, 0, 3}];

便宜上、バーンスタイン基底を使用していることを覚えておいてください。ただし、ベジェ曲線の任意のパラメトリック表現で問題ありません。

これは次のようになります。

代替テキスト

ここで、ポイント（たとえば、{3、-1}）までの最小距離を見つけるには、関数を最小化する必要があります。 

d[t_] := Norm[{3, -1} - f[t]];

そのためには、最小化アルゴリズムが必要です。便利なものが1つあるので、次のようにします。

NMinimize[{d[t], 0 <= t <= 1}, t]

与える： 

 {1.3475, {t -> 0.771653}}

そしてそれだけです。

HTH！

編集編集について「（n-1）/3立方ベジェ曲線で構成されるBスプライン」。

区分的Bスプライン表現を作成した場合は、すべてのセグメントを反復処理して最小値を見つける必要があります。連続パラメーターでピースを結合した場合、これと同じアプローチで実行できます。

編集

あなたの曲線を解きます。私はそれが何であるかを本当に理解していなかった ので、私は最初のポイントを無視します。

わかりやすくするために、数学の機能の代わりに標準のBスプラインを使用して解決しました。 

Clear["Global`*"];
(*first define the points *)
pts = {{
        29.124, 284.61}, {
        25.066, 258.56}, {
        20.926, 212.47}, {
        34, 176}, {
        38.706, 162.87}, {
        46.556, 149.82}, {
        54.393, 138.78}};

(*define a bspline template function *)

b[t_, p0_, p1_, p2_, p3_] :=
                  (1-t)^3 p0 + 3 (1-t)^2 t p1 + 3 (1-t) t^2 p2 + t^3 p3;

(* define two bsplines *)
b1[t_] := b[t, pts[[1]], pts[[2]], pts[[3]], pts[[4]]];
b2[t_] := b[t, pts[[4]], pts[[5]], pts[[6]], pts[[7]]];

(* Lets see the curve *)

Show[Graphics[{Red, Point[pts], Green, Line[pts]}, Axes -> True], 
 ParametricPlot[BSplineFunction[pts][t], {t, 0, 1}]]

。（画面スペースを節約するために回転！）

代替テキスト

(*Now define the distance from any point u to a point in our Bezier*)
d[u_, t_] := If[(0 <= t <= 1), Norm[u - b1[t]], Norm[u - b2[t - 1]]];

(*Define a function that find the minimum distance from any point u \
to our curve*)
h[u_] := NMinimize[{d[u, t], 0.0001 <= t <= 1.9999}, t];

(*Lets test it ! *)
Plot3D[h[{x, y}][[1]], {x, 20, 55}, {y, 130, 300}]

このプロットは、空間内の任意のポイントから曲線までの（最小）距離です（もちろん、曲線上の値はゼロです）。

代替テキスト

于 2010-11-25T12:38:40.383 に答える
2

まず、お気に入りのアルゴリズムを使用して曲線をビットマップ (白黒) にレンダリングします。次に、必要に応じて、この質問からの情報を使用して、マウス位置に最も近いピクセルを決定します。距離を返すように検索関数を変更できるため、要件と簡単に比較できます。この方法では、1 ～ 2 ピクセルの許容誤差で距離が得られます。

于 2010-11-25T09:58:28.957 に答える
1

定義：点から線分までの距離=元の点からまだ線分上にある最も近い点までの距離。

仮定：ポイントからセグメントまでの距離を計算するためのアルゴリズムがわかっています（たとえば、元のポイントを通過するセグメントの法線のセグメントとの切片を計算します。交差がセグメントの外側にある場合は、最も近い終点を選択しますセグメントの）

  1. deCasteljauアルゴリズムを使用して、線形セグメントの十分なデイジーチェーンに到達するまで3次方程式を細分化します。補足情報「ベジェ曲線の平坦化」セクション
  2. ポイントと結果のセグメント間の最小距離を、ポイントからカーブまでの距離と見なします。セット内のすべての曲線に対して繰り返します。

ポイント2での改良：実際の距離を計算しないでください。ただし、その2乗で、最小の2乗距離を取得するだけで十分です。sqrt呼び出し/セグメントを節約できます。

計算の労力：経験的に、最大範囲（つまりバウンディングボックス）が200〜300の三次曲線は、最大許容値0.5（肉眼で十分）に平坦化されたときに約64の線分になります。

  1. 各deCasteljauステップには、2による12の除算と12の追加が必要です。
  2. 平坦度の評価-8回の乗算+4回の加算（距離を評価するためにTaxiCab距離を使用する場合）
  3. ポイントからセグメントまでの距離の評価には、最大12回の乗算と11回の加算が必要ですが、これはベジェ平坦化のコンテキストではまれなケースであり、平均6回の乗算と9回の加算が予想されます。

したがって、非常に悪いケース（100の直線セグメント/立方体）を想定すると、考慮される立方体あたり約2600の乗算+2500の加算のコストで距離を見つけることができます。

免責事項：

  1. 上記の計算労力評価の数値のデモンストレーションを求めないでください。 「ソースコードを使用する」（注：Java実装）で答えます。
  2. 他のアプローチが可能であり、おそらくより安価です。

よろしく、

エイドリアン・コロミッチ

于 2011-02-17T07:10:48.333 に答える