先日のエントリでは、射影(Projection)を用いた領域検索について解説し、簡単な実装を行いました。今回はその実装をリファクタリングしてみます。 では、早速始めましょう。先日のコードをジェネレータとしてsequential_search()関数にまとめたコードから開…

先日のエントリでは、矩形の交差判定を行う際の用語の紹介を行いました。今回のエントリでは、射影(Projection)という技法を紹介します。一見、射影は単純なことを難しく表現しているだけに感じられるかもしれません。しかし、計算幾何や領域検索を考えるに…

先日のエントリではマンハッタン幾何を紹介し、総当たりによる実装を行いました。その際、水平と垂直の線分を縮退した矩形とみなし、交差判定を行いました。今回のエントリでは、矩形の交差判定アルゴリズムを考えるための用語の解説を行います。また、次回…

先日kd-treeについてのエントリを記載したことは、自分にとって計算幾何の面白さを再認識する良い機会となりました。計算幾何で用いられる幾何学的アルゴリズムは比較的若く、今でも進化の過程にあります。また、人間には単純に見える問題も計算機にとっては…