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

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

先日のエントリに引き続き、Quick Selectアルゴリズムについて考えてみたいと思います。Quick Selectアルゴリズムを考えるに至った動機は、メディアンを選択することでした。今回は以下の9個の要素を持つ配列を使って考えてみましょう。ここでは、配列のイン…

先日のエントリではメディアンの選択にsort()を用い、より効率のよいメディアンの選択方法を課題としました。さて、今回そのアイデアの一つとして紹介するのはQuick Selectというアルゴリズムです。Quick Selectというアルゴリズム名は一般的ではないかもし…

さて、先日のエントリにて、メディアンを加味した2d木の構築を紹介しました。コードの見通しを簡潔にする目的もあり、メディアンの選択にはsort()を用いました。 #!/usr/bin/python -t from operator import itemgetter from random import seed, randint de…

先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成し…

前回のエントリに引き続き、連続したビット群の総数を求めるアルゴリズムを考える予定でしたが、今回は空間分割データ構造に関するエントリにしました。人力検索はてなに以下のような問題が提示されていたのがきっかけでした。 二次元の値(x, y)をもつ集合P …

先日のエントリにて掲載した問題の回答を検証するに当たり、コードを書いてみました。問題は以下のようなものでした。 さて、この問題には「壊してもよいブロック」と「必ず残るブロック(確定のブロック)」が一つずつあるようです。それは一体どれでしょうか…

任天堂から発売された立体ピクロスにはまっています。これは面白い。ピクロスDS等の平面でのピクロスとは異なった趣を持ち、また全く異なる要素を持ったパズルであるよう感じます。任天堂 ++ 細かいルールは任天堂の立体ピクロスのページを参照して頂くとし…