日記（アルゴリズムの工夫）

今日見た夢は思い出せず。F/AからC/Gみたいなコードの流れに、黒鍵を多く含むメロディを弾いていたというおぼろげなイメージはあったが、それ以上を思い出せなかった。

起きてから同じようなことをやってみたけど、合うわけもなく。朝のうちだけは涼しい、ということはない。

昨日から引き続き、winding numberを求めるアルゴリズムで、rayをcastして交わり具合を見ていく方法を実装してみた。

角度を求めて足していく方法と比べて、ray castingのほうが劇的に早くなるというわけでもなかった。この絵の場合で、80秒かかっていた処理時間が70秒になった、という程度だった（色は気分で変えている）。

どちらのアルゴリズムの場合も、多角形の辺の数に比例する時間がかかるので、本質的には辺の本数を最適化するのがよさそうだ、という印象。

その観点からは、タイルを含むBoundary Diskを考えて「タイルの内点ではないこと」を（辺の本数に関係なく）すぐに判定する、という手法のほうが計算量に大きく寄与していると思う。「タイルがすべて相似形」という条件があるので、基本的なタイルでBoundary Diskがわかっていれば、中心の移動と拡大をするだけで、他のすべてのタイルに適用できるのがこの状況下ではありがたい。

と書いていて、ちょっと思いついたことがある。タイルを含む円ではなく、タイルの内部に含まれるなるべく大きめの円を考え、その円に含まれるかどうかで「タイルの内点であること」をすぐに判定できるようにすればよいのではないか。

バウンディングボックスは衝突判定のアルゴリズムでよく使われているイメージがあるけど、領域の内外判定では、バウンディングボックスは「外側である判定」にのみ使われている。だから「内側である判定」のためのオブジェクトがあってもいいはずだ。そういう手法はすでにあると思うけど、どういう名前が付いているのかはまだ知らない。図形に対する内接円みたいなものというのだろうか。

実装は簡単なので、基本となるタイルで原点中心の半径0.5の円としてやってみたところ（本当はちょっと原点を右側にずらして半径2/3くらいにしてもいけるが、理論上のベストな位置と値はわからない）、70秒かかっていた処理が68秒になった、という程度であまり大きな影響がなかった。

まあ確かに通常は円の内部よりは外部のほうが広いので、任意の点が与えられたときにそれがどこに含まれるかという違いでもある。