ベクター画像で面を塗りつぶしすにはどうすれば良いかを考えている。ベクター画像というのは、絵を表現するのに点の集合(ビットマップ)では無く、線の集合と考える方法で、滑らかに描けるのは良いのだけど、気軽に絵の好きな領域を塗りつぶせないという欠点がある(Flash はうまい事やってる)。だからこの機能は大切なのだ。
マウスの周りをある色で塗りつぶす為には、マウスの周りを取り囲む図形を求めなくてはいけない。マウスの位置からまず近い壁にスタート地点を作って、そこから探索していけば良いだろうという目星はついた。最初はトポロジー的な最短経路を求めれば良いのではと思ったのだが、そうすると世界には内も外も無くなって駄目だった。そこで、とりあえず左回りにグラフを辿る方法に変えた。
ここで問題なのは、「左回り」をどうやって表現するか。ある Y 型の路地があって、どっちが左なのかは見れば簡単に分かるけど、数字でどう表現されるのだろう。簡単のために道路の角度は全部単位ベクトルで表現する事にする。入り口の向きを P 出口を Q とするとき、P と Q の角度を求めれば良い。僕は外積だとか内積だとか言う物が大嫌いなので、自分で導いた http://d.hatena.ne.jp/propella/20050403/p2 の式を使う。
- Qx = RxPx - RyPy
- Qy = RyPx + RxPy
を (Rx, Ry) について解けば、P と Q の角度の単位ベクトルが分かる。この場合、Ry がプラスなら P の向きより左側で、Rx が -1 に近いほど角度が急だと判定出来る(-1 なら 180度逆向き)。計算を自分でするとろくな事が無いので maxima でやってみる。
(%i) f1: Qx = Rx * Px - Ry * Py;
(%i) f2: Qy = Ry * Px + Rx * Py;
(%i) solve ([f1, f2], [Rx, Ry]);
Py Qy + Px Qx Py Qx - Px Qy
(%o) [ [Rx = -------------, Ry = - -------------] ]
2 2 2 2
Py + Px Py + Px
あ！これは以前 http://d.hatena.ne.jp/propella/20050703/p2 でやったのと同じ事だったガックリ。
