日記（巻き数、Bounding Ball）

今日見た夢は思い出せず。ノコノコレースみたいなものを走っていたような印象がぼんやりとあるものの、それ以上は思い出せなかった。

昔、夏休みに登校日というのがあったような、あるいはなかったような気がするが、最近の小学生はZOOMでオンラインミーティングをやるらしい。

昨日、winding number（巻き数）の計算の話を書いたが、そもそも角度の計算もしなくていいアルゴリズムがあることを知る。与えられた点から出る半直線（ray）と多角形の辺との交わりを数えるときに、半直線をどちらから横断しているかで1を足すか引くか、とやっていくようだ。crossing numberを求めるアルゴリズムにちょっと手を加えるだけでできるので、逆三角関数も使わない。交差判定に外積を使うくらいだけど、rayの向きを固定していれば（たとえばx軸に水平あるいは垂直）それすら不要かもしれない。そんなことないか。このアルゴリズムに何かそこまでデメリットがある感じでもなさそうだし、どう考えてもこっちのほうがいい感じがする。

ただ、各タイルのBounding Ballを考えて、明らかに外部にある点を早めに除外するだけでも処理はかなり軽くなっているのを実感した。

昨日のものよりも細部まで描くようにしても、処理時間はかなり短かかった（ちゃんと計ってないけど）。色合いは気分で適当に変えている。

考えてみると、タイルのサイズが小さくなっても数千角形としてデータを持っているのがかなり無駄な気がしてきた。うまく間引けば、小さいサイズのタイルに対しては処理が軽くなるはず。

このアルゴリズムをふまえると、crossing numberはwinding numberから偶奇性だけの情報を取り出した数というのがよくわかる。