« 2010年08月 | メイン

2010年10月 アーカイブ

2010年10月14日

Foundation of bezier curve (2)

だいぶ間があきましたが続きです。

de Casteljauのアルゴリズムではtを定めたのち、次の6つの式をまず計算します。

decas.gif

この式に出てきたベクトルを下記のように選んで新しいベジェ曲線を2つ作ります。すると、曲線の形を維持したままtの位置で分割された2つのベジェ曲線を得ることができます。

splitted.gif

参考:
The Essentials of CAGD
http://www.farinhansford.com/books/essentials-cagd/

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性を利用しています。