11

直線と2次ベジェ曲線の点を前提として、それらの最も近い点をどのように計算しますか？

ここに画像の説明を入力してください

4

7 に答える 7

7

INRIAからのこの質問に関する科学論文があります：2つのベジェ曲線間の最小距離の計算（PDFはこちら）

于 2011-12-12T12:03:52.477 に答える
6

私はかつて同様のタスクを実行するためのツールを作成しました。ベジェスプラインは通常、パラメトリック3次多項式です。立方体セグメントと線の間の距離の2乗を計算するには、これは2つの多項式関数の間の距離の2乗であり、それ自体が別の多項式関数です。平方根ではなく、距離の2乗を言ったことに注意してください。

基本的に、立方体セグメント上の任意の点について、その点から線までの距離の2乗を計算できます。これは6次の多項式になります。その距離の2乗を最小化できますか？はい。最小値は、その多項式の導関数がゼロの場合に発生する必要があります。したがって、微分して、5次の多項式を取得します。すべてのルートを数値で生成するお気に入りのルート検索ツールを使用します。ジェンキンス＆トラウブ、何でも。複雑な解を除いて、その根のセットから正しい解を選択し、問題の立方体セグメント内にある場合にのみ解を選択します。距離の極大に対応するポイントを除外するようにしてください。

これらはすべて効率的に実行でき、多項式求根アルゴリズム以外の反復オプティマイザーを使用する必要はありません。したがって、開始値を必要とする最適化ツールを使用する必要はなく、その開始値に近い解のみを検索します。

たとえば、3次元の図では、3次元の点のセット（赤）によって生成された曲線を示しています。次に、外側の円にある別の点のセットを取り、内側の最も近い点を計算しました。それぞれから曲線を描き、その曲線まで線を引きます。最小距離のこれらのポイントは、上記のスキームによって生成されました。

ここに画像の説明を入力してください

于 2011-12-12T14:37:04.987 に答える
1

標準分析の観点から問題を定式化します。最小化する量（距離）があるので、この量の方程式を定式化し、一次導関数がゼロになる点を見つけます。曲線のパラメータを使用して、単一のパラメータでパラメータ化しますp。これは、最初のポイントの0と最後のポイントの1の間です。

直線の場合、方程式はかなり単純です。スプラインの方程式からx / y座標を取得し、ベクトル方程式（直線の内積）を介して指定された直線までの距離を計算します。

曲線の場合、分析ソリューションはかなり複雑になる可能性があります。ネルダーミードなどの数値最小化手法を使用するか、1D連続問題があるため、単純な二分法を使用することをお勧めします。

于 2011-12-12T12:05:09.490 に答える
1

1.単純な悪い方法-反復によって、最初の曲線からポイントごとに進み、2番目の曲線からポイントごとに進み、最小値を取得します。2.曲線間の距離の数学関数とこの関数の計算限界を次のように決定します。

| Fcur1（t）-Fcur2（t）| -> 0

Fsはベクトルです。

極値を決定し、最も近い点と最も遠い点を取得するために、これの導関数を計算できると思います

しばらくしてからこれについて考え、完全な回答を投稿します。

于 2011-12-12T12:00:41.653 に答える
1

QBCurve //セグメントの場合、いくつかのヒントを示したいと思います。十分に高速な計算を行うには、まず、アルゴリズムに一種の「バウンディングボックス」を使用することを検討する必要があると思います。P0がQB曲線の最初の点、P2が2番目の点、P1が制御点、P3P4がセグメントであるとしましょう。

  1. P0、P1、P2からP3P4までの距離を計算します
  2. P0またはP2が最も近い点である場合->これはP3P4からの曲線の最も近い点です。終了：=）。
  3. P1が最も近いポイントで、Pi（i = 0または1）が2番目に近いポイントである場合、PiPCとP3P4の間の距離は、必要に応じて十分に正確な、求める距離の推定値です。
  4. より正確にする必要がある場合：P1から最も近いQBcurve上の点であるP1'を計算します：t=0.5のBQC式を適用していることがわかります。-> PiP1'からP3P4までの距離は、さらに正確な見積もりですが、コストがかかります。
  5. P1P1'で定義された線がP3P4と交差する場合、P1'はP3P4からQBCに最も近い点であることに注意してください。
  6. P1P1'がP3P4と交差しない場合は、運が悪いので、苦労する必要があります...

今（そしていつ）あなたが精度を必要とするなら：

曲線のパラメータに分割統治アルゴリズムを使用することを検討してください：これはP3P4から最も近いですか?? P0P1'またはP1'P2??? P0P1'の場合->tは0から0.5の間なので、t=0.25のPmを計算します。今、P3P4から最も近いのはどれですか？P0PmまたはPmP1'?? PmP1'の場合->t= 0.25 + 0.125 = 0.375のPm2を計算します。次に、どちらが最も近いですか？PmPm2またはPm2P1'??? など、6回の反復のように、すぐに正確な解が得られ、tの精度は0.004です。2点間の距離が所定の値を下回ると、検索を停止する場合があります。（2つのパラメーターの違いではありません。パラメーターを少し変更すると、ポイントが遠くなる可能性があるためです）実際、このアルゴリズムの原理は、毎回、セグメントを使用して曲線をより正確に近似することです。

曲線/曲線の場合、無駄な計算を避けるために、最初にそれらを「ボックス化」するので、最初にセグメント/セグメント計算を使用し、次に（多分）セグメント/曲線計算を使用し、必要な場合にのみ曲線/曲線計算を使用します。

曲線/曲線の場合、分割統治法も機能します。説明するのはより困難ですが、理解できるかもしれません。：=）

これで速度/精度のバランスが取れることを願っています：=）

編集：一般的なケースで良い解決策を見つけたと思います:-)各BQCの（内側の）境界三角形を反復する必要があります。したがって、三角形T1、点A、B、Cに「t」パラメーターtA、tB、tCがあります。 。三角形T2、点D、E、F、tパラメータtD、tE、tFを持ちます。最初はtA=0 tB = 0.5 tC = 1.0であり、T2についても同じです。tD= 0、tE = 0.5、tF = 1.0アイデアは、問題がなくなるまでT1および/またはT2を小さな長方形に分割するプロシージャを再帰的に呼び出すことです。到達した精度で。最初のステップは、T1からT2までの距離を計算し、各三角形で最も近いセグメントを追跡することです。最初の「トリック」：T1でセグメントがACの場合、T1で再帰を停止し、曲線1の最も近いポイントはAまたはCのいずれかです。T2で最も近いセグメントがDFの場合、T2で再帰を停止します。 Curve2はDまたはFのいずれかです。両方の再帰を停止した場合->戻り距離=分（AD、AF、CD、CF）。次に、T1に再帰性があり、セグメントABが最も近い場合、新しいT1は次のようになります。必要に応じて再帰を適用し、新しいT1と新しいT2で同じアルゴリズムを呼び出します。T1とT2の間に見つかった距離から、前のT1とT2の間に見つかった距離を引いた距離がしきい値を下回ったときに、アルゴリズムを停止します。関数はComputeDistance（curveParam1、A、C、shouldSplitCurve1、curveParam2、D、F、shouldSplitCurve2、previousDistance）のようになり、ポイントはtパラメーターも格納します。T2についても同じことが言えます。必要に応じて再帰性を適用し、新しいT1と新しいT2で同じアルゴリズムを呼び出します。T1とT2の間に見つかった距離から、前のT1とT2の間に見つかった距離を引いた距離がしきい値を下回ったときに、アルゴリズムを停止します。関数はComputeDistance（curveParam1、A、C、shouldSplitCurve1、curveParam2、D、F、shouldSplitCurve2、previousDistance）のようになり、ポイントはtパラメーターも格納します。T2についても同じことが言えます。必要に応じて再帰性を適用し、新しいT1と新しいT2で同じアルゴリズムを呼び出します。T1とT2の間に見つかった距離から、前のT1とT2の間に見つかった距離を引いた距離がしきい値を下回ったときに、アルゴリズムを停止します。関数はComputeDistance（curveParam1、A、C、shouldSplitCurve1、curveParam2、D、F、shouldSplitCurve2、previousDistance）のようになり、ポイントはtパラメーターも格納します。

距離（曲線、セグメント）はこのアルゴリズムの特定のケースであり、距離（三角形、三角形）と距離（セグメント、三角形）を実装して機能させる必要があることに注意してください。楽しむ。

于 2011-12-12T13:31:37.800 に答える
1

ベジェ曲線と直線の場合

線に最も近い点には、次の3つの候補があります。

  1. 線分に平行なベジエ曲線セグメント上の場所（そのような場所が存在する場合）、
  2. 曲線セグメントの一方の端、
  3. 曲線セグメントのもう一方の端。

3つすべてをテストします。最短距離が勝ちます。

2つのベジェ曲線の場合

正確な分析結果が必要かどうか、または最適化された数値結果で十分かどうかによって異なります。

分析結果

2つのベジェ曲線A（t）とB（s ）が与えられると、それらの局所的な向きA '（t）とB '（s ）の方程式を導き出すことができます。A '（t）= B '（s）が候補となる点のペア、つまり、曲線が局所的に平行である（ t、s ）。確認していませんが、A '（t）-B '（s）=0は解析的に解くことができます。曲線が例で示したもののようなものである場合、その方程式の解は1つだけであるか、まったくないはずですが、2つある可能性があります（または、曲線が同一であるが変換されている場合は無限に多くなります-この場合勝者は常に曲線セグメントの端点の1つになるため、これは無視してかまいません）。

上記の曲線の場合の概要と同様のアプローチで、これらの各ポイントペアと、曲線セグメントの端点をテストします。最短距離が勝ちます。

数値結果

2つのベジェ曲線上の点がA（t）とB（s ）として定義されているとしましょう。距離d（t、s）=|を最小化する必要があります A（t）-B（s）|。これは単純な2パラメーター最適化問題です。制約0≤t≤1および0≤s≤1でd（t、s ）を最小化するsとtを見つけます。

d = SQRT（（xA --xB ）²+（yA --yB）²）なので、関数f（t、s）= [ d（t、s）]²を最小化して平方根計算を保存することもできます。

このような最適化問題には、多くの既成の方法があります。選んで決める。

上記のどちらの場合も、2次ベジェ曲線よりも高次のものは複数の極小値を与える可能性があるため、これには注意が必要です。あなたが与えた例から、あなたの曲線には変曲点がないように見えるので、この懸念はあなたの場合には当てはまらないかもしれません。

于 2011-12-12T20:32:35.713 に答える
0

法線が一致する点が最も近い点です。つまり、線に直交する線を引くということです。。その線が曲線にも直交している場合、交点は最も近い点です

于 2011-12-12T11:43:45.913 に答える