さて、今度はこれもまたベジェ曲線で問題になる最近傍点の探索問題です。
以下の図のように、ある座標βに最も近いベジェ曲線上αの点を探すにはどうしたらよいでしょう？
実は、これについても簡単に求める方法がなく、以下の式の根を求めることになります。
ここでB(t)は1回目で紹介したベジェ曲線の多項式です。上記の式は5次方程式になり、解の公式が存在しないため数値解析等を利用して解くことになります。
解き方としては以下のものが代表的ですが、他にも色々あるようです。
参考：
Accurate and Efficient Algorithm for the Closest Point on a Parametric Curve他
この論文ではBezier Clipping同様にベジェ曲線のConvex hull性を利用しています。
だいぶ間があきましたが続きです。
de Casteljauのアルゴリズムではtを定めたのち、次の6つの式をまず計算します。
この式に出てきたベクトルを下記のように選んで新しいベジェ曲線を２つ作ります。すると、曲線の形を維持したままtの位置で分割された2つのベジェ曲線を得ることができます。
参考：
The Essentials of CAGD
http://www.farinhansford.com/books/essentials-cagd/
だいぶ遅くなりましたが今年も手稲高校から4名のみなさんに来て頂き、プログラミングを体験してもらいました。
去年はProcessingを利用しましたが、見ていると構文エラーが出た時にかなりつらいようでしたので
今年はビジュアルプログラミング環境で行くべ、ということで
MIT Media Lab の Scratch(http://scratch.mit.edu/) を利用することにしました。
カリキュラムとしては物体の動かし方を学んでもらってから、最終的にpongっぽいものをつくるというかんじでやってみました。
ことしのみなさんはLOGOやC/C++、なでしこ（！）の経験者という強者ぞろいだったため、事前に用意したネタが尽きてしまうというトラブルもありましたが、おおむね喜んで頂けたようです。
当日作ったスケッチを以下に貼ります。実行にはブラウザへのSun Java プラグインインストールが必要です。
(英語が間違ってるのに気付きましたが直してもサムネイルが更新されません！ぎゃー）
最近ベジェ曲線をいじいじしていたのですが、案外衝突判定とか切断のまとまった情報がなかったので書いておきます。
とりあえずここでは三次ベジェ曲線を取り上げます。Adobe Illustratorとかでお馴染みのアレです。(以下図版はWikipediaより引用)
三次ベジェ曲線は次の式によって与えられます。
ここでtは長さを表すパラメータで0≦t≦1です。P0（始点）が0、P4（終点）が1になります。P1,P2は制御点です。
ベジェ曲線はふつうの直線の描画とことなり、媒介変数tを動かしてそのtの時のx,y座標を求める、というやり方でしか描画ができなかったりします。
さて、このパスを適当なtの位置（長さ）を決めて、パスの形をそのままにそこで切断するとした時、どのようにしたらよいでしょうか。
これには、de Casteljau's algorithmというのを使います。de Casteljauはベジェ曲線を考えた人ですが、これを使うと新しいコントロールポイントの位置が多項式を逐次的に計算していくだけで簡単に決まります。(続く)
参考：
The Essentials of CAGD
http://www.farinhansford.com/books/essentials-cagd/
今日も今日なでCocoaアプリを書いていたわけですが、
ドはまりしたことがあったのでここで書いておこうかと。
アプリケーションの描画の際に、
今までカスタムビュー上にそのまま描画していた部分を、
テキストやパスなどのベクタデータも含めて
半透明合成等のピクセル合成処理をかけないといけなくなったので、
一度NSBitmapRepresentaionをバックエンドに持たせたNSImageにデータを描画し、
一種のラスタライズを行ってからそのNSImageをカスタムビュー上に描画しなおすことにしました。
この方針でおおよそもくろみ通りうまくいっていたのですが、
テキストを描画していた部分をこの方法に置き換えてみたところ、
文字の天地が逆になってしまうという問題が発生してしまいました。
色々往生してみたところ、cocoa-devで同じようなハマりをしている人が見つかりました。
focusが当たっているビューの座標系が上下反転させた状態で、
NSImageにlockFocusでfocusを当てて画像上に文字を書くと、この症状が起きるようです。
Cocoaの仕様的にどうにもならないようでしたので、
NSImageにsetFlipped:YESを設定した状態で反転したビットマップを作り、
さらにそのあとにNSAffineTransformで上下反転マトクリクスを作成して
現在のグラフィクスコンテキストに結合し、
上下反転コピーを行ったビットマップをもう一個作ることで
なんとなく対処できました。
一応予定の見栄えにはなったのですが、
2回ビットマップができるので大変無駄臭いような気がします…。
自前のピアソンの積率相関係数のpython実装をscipy.stats.pearsonrに変更するだけで30倍くらい処理速度が上がってびっくらこきました。すごい…。
ところでscipyで書いたものをJavaに移植したいなあ、と思ったのですが、Commons mathでも予想以上に線形代数や統計関係が充実していました。sparse matrixとか特異値分解とかも入っているので、よっぽど速度が必要な場合以外はJNI-BLASバインディングを使わなくてもよさそうです。そのうち比較してみますが。
Javaの場合演算子オーバーライドがないですので微妙にまどろっこしい印象はいなめませんがしかたないですね。
一個前のエントリと関連して、PythonでWebサーバ上のHTMLをスクレイピングしてくるべーということをやろうとしたのですが、これはScrapemark : http://arshaw.com/scrapemark/docs/examples/というのを使うと大変簡単にできました。
使い方はまあ簡単で
>>> scrape("""
<div id='content'>
{{ before_table }}
<table />
</div>
""",
url="http://example.com")>>> {'before_table': 'Look at these data points'}
みたいなかんじです。
HTMLの繰り返しになっているところの中身をリスト化してとってくることもできます。これは
>>> scrape("""
<body>
{*
<div class='section' id='{{ [section_ids] }}' />
*}
</body>
""",
html)>>> {'section_ids': ['nav', 'content', 'footer']}
というかんじで大変使い勝手が良いですねー。開発元のexampleを見ると、もっと構造化したデータも取ってこれるようです。
RubyでNokogiriとかするより楽な気が致しますねえ。
あと、スーパー便利な事に結果にはユニコード化された文字列が入ってきますので扱いも楽ちんです。
