やまかわのログ: math アーカイブ

最近ベジェ曲線をいじいじしていたのですが、案外衝突判定とか切断のまとまった情報がなかったので書いておきます。

とりあえずここでは三次ベジェ曲線を取り上げます。Adobe Illustratorとかでお馴染みのアレです。(以下図版はWikipediaより引用)

三次ベジェ曲線は次の式によって与えられます。

ここでtは長さを表すパラメータで0≦t≦1です。P0（始点）が0、P4（終点）が1になります。P1,P2は制御点です。
ベジェ曲線はふつうの直線の描画とことなり、媒介変数tを動かしてそのtの時のx,y座標を求める、というやり方でしか描画ができなかったりします。

さて、このパスを適当なtの位置（長さ）を決めて、パスの形をそのままにそこで切断するとした時、どのようにしたらよいでしょうか。

これには、de Casteljau's algorithmというのを使います。de Casteljauはベジェ曲線を考えた人ですが、これを使うと新しいコントロールポイントの位置が多項式を逐次的に計算していくだけで簡単に決まります。(続く)

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

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

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

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

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

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

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

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

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

やまかわのログ