« Foundation of bezier curve (2) | メイン

Foundation of bezier curve (3)

さて、今度はこれもまたベジェ曲線で問題になる最近傍点の探索問題です。

以下の図のように、ある座標βに最も近いベジェ曲線上αの点を探すにはどうしたらよいでしょう?

Bezier2.png

実は、これについても簡単に求める方法がなく、以下の式の根を求めることになります。

nearest.gif

ここでB(t)は1回目で紹介したベジェ曲線の多項式です。上記の式は5次方程式になり、解の公式が存在しないため数値解析等を利用して解くことになります。

解き方としては以下のものが代表的ですが、他にも色々あるようです。


  • Newton法

  • Bezier Clipping

  • Bisectionning

参考:
Accurate and Efficient Algorithm for the Closest Point on a Parametric Curve
この論文ではBezier Clipping同様にベジェ曲線のConvex hull性を利用しています。

トラックバック

このエントリーのトラックバックURL:
http://antas.jp/mtsys/mt-tb.cgi/862

コメントを投稿

(いままで、ここでコメントしたことがないときは、コメントを表示する前にこのブログのオーナーの承認が必要になることがあります。承認されるまではコメントは表示されません。そのときはしばらく待ってください。)