n次有理ベジエ曲線と線分の最短点

左:オレンジの丸は曲線の制御点(ドラッグで移動、ダブルクリックで重み w を編集)。青い四角は線分の端点(ドラッグで移動)。 右:曲線から線分(を含む直線)への垂直距離関数 f(t) の微分 f'(t)=0 を、 g(t) = Num'(t)・Den(t) − Den'(t)・Num(t) という 2n−1 次 のベジエ関数として計算し、その制御多角形の凸包とともに表示します。 g(t)=0 の根はベジエクリッピング法で求めています。g(t) の制御点が作る凸包と y=0 の直線(フラットライン)との交差範囲によって 根を含みうる t の区間を絞り込み、絞り込みが不十分な場合は区間を二分してそれぞれを再帰的に処理する、という手順を収束するまで繰り返します。 この方法は凸包性質を利用しているため、通常のサンプリングよりも少ない反復回数で高精度に根へ収束します。 左のグラフを操作すると右のグラフが連動して更新されます。

曲線と線分
曲線 C(t)
制御点 Pi
線分端点 A, B
線分上の最短点
曲線上の最短点
距離関数の微分 g(t)(2n−1次)と凸包
g(t) の曲線
制御点の凸包
計算中...