CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

計算幾何学問題「キュラゲの最小包含円を求めよう」の解説記事です!キーワードは「乱択アルゴリズム」 #ゲーム開発

CodeIQ中の人、millionsmileです。

出題者のstakemuraさんによる「計算幾何学」問題の解説記事です。

アクションゲームなどでキャラクターを攻撃するとき、ナイーブに1キャラクターごとに1ピクセル単位で処理していたら、計算時間は大変なことになります。さて、どうやったら物理演算を軽くできるのでしょうか?キーワードは「乱択アルゴリズム」です。

ゲーム開発をしている方は必見の記事です。

===============================
高速化の秘訣は乱数にあり

stakemuraです。

先月、「キュラゲの最小包含円を求めよう」というタイトルで、CodeIQでは初となる計算幾何学の問題を寄稿させて頂きました。いきなりの難問だったにも関わらず24名もの方に挑戦して頂き、中には当方が驚かされるような回答もあったりして、達成感を噛み締めている今日この頃です。さて、挑戦者が用いたプログラミング言語の内訳ですが、以下の通りとなりました。

C++ 7
Ruby 4
Python 3
C# 2
Java 2
Perl 2
Haskell 1
Awk 1

多くの方が、実行速度が最速となるC++を選んだ理由。それは

ちゃんと最適化しないと計算時間が大変なことになるぞ…

という直感が働いた結果なのかなと思います。事実この問題は、厳密解をナイーブなアルゴリズムで求めようとすると、C++でもかなりの計算時間を要します。それこそ、計算時間に制約があるIdeone.com上では、コードレベルでいくら最適化しても無理で、アルゴリズム自体高速化しない限り、実行は不可能でしょう。それでは一体どんな高速化が必要なのでしょうか?

まず大前提ですが、2次元の最小包含円は、2点あるいは3点を選んだ場合のいずれかの組み合わせにおける(線分あるいは三角形の)外接円に相当します。(3次元の最小包含球の場合は、これに4点から成る4面体の外接球が加わる)。したがって頂点数をnとした場合、「最小包含円を求める」=「任意の2点あるいは3点の組み合わせから成る包含円を比較する」問題となり、計算量はO(N3)となります。本設問で用意した点の数はN=1529ですから、それがO(N3)となれば大変な計算量になってしまいます。

実はこの問題は、学術的には乱択アルゴリズム(Randomized Algorithm)を用いることでO(N)問題に帰着できることが証明されています[Welzl, 1991]。乱択アルゴリズムとは、乱数を用いて挙動の一部に無作為性を導入したアルゴリズムのことであり、有名な応用例にクイックソートが挙げられます。Welzlのアルゴリズムを簡潔まとめると、最初にランダムな順番で点に番号を付け、次に1・2番目の2点から構成した包含円を、3番目、4番目…と適応的に拡げることで、最小包含円を求めるというものです。

ただ挑戦者の多くの方は別の乱択アルゴリズム[Ishibata, 2002] を採用していました。その背景には、日本語で分かりやすく解説された資料があること、そして実装がものすごく簡単という事情があったと思います。Ishibataのアルゴリズムは、まず仮中心を決め、仮中心からN個ある点の中で最も遠い点に反復法で近づけるというものです。本当にそんなアルゴリズムで大丈夫か?と突っ込みたくなるくらい計算は単純ですが、実際にコードに落として実行するとちゃんと動くから不思議です。

実はこの乱択アルゴリズムと最遠点という組み合わせは、意外な分野で登場しています。それは、分割型クラスタリングアルゴリズムの代表選手、k-means [Lloyd, 1957]の改良版、k-means++ [Arthur et al. 2007] です。k-meansではクラスタ中心の初期値をランダムに求めますが、k-means++は次のクラスタ中心を求める過程において、最遠点ほど選ばれやすくする(この確率の決め方が実に巧妙で、常に最遠点を選ばせるような決定的アルゴリズムだと外れ値に弱くなる)ことで、計算時間だけではなく、クラスタリング結果の改善にも成功しました。k-means++も実装はとても簡単で、広く用いられています。

乱数を取り入れるだけで、計算が速くなるだけではなく、結果が良くなるというのだから不思議ですよね。さらに近年では、乱択アルゴリズムを大規模な特異値分解に応用することで、既存手法では難しかったレコメンドサービスが実現できるようになったりと目覚しい進歩を遂げています。

以上、計算幾何学と乱拓アルゴリズムの繋がりについて語ってみました。これからはアルゴリズム的にも面白い問題を出していけたらなぁ、と思っています。皆さん、よろしくお願いしますね。

参考文献

[Welzl, 1991] Welzl, Emo (1991), "Smallest enclosing disks (balls and ellipsoids)", in Maurer, H., New Results and New Trends in Computer Science, Lecture Notes in Computer Science 555, Springer-Verlag, pp. 359–370 [ pdf ]
[Ishibata, 2002] 石畑 清. "点の集合を包含する球". 情報処理 43(9), 1009-1015, 2002-09-10 [ pdf ]
[Lloyd, 1957] Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM". IEEE Transactions on Information Theory 28 (2): 129–137. [ pdf ]
[Arthur et al. 2007] Arthur, D. and Vassilvitskii, S. (2007). "k-means++: the advantages of careful seeding". Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. pp. 1027–1035 [ pdf ] ] [ slides ]

===============================
なかなか奥の深い話ですね。
以下、問題文です。

CodeIQに住みついている謎の電脳生物”キュラゲ”が何100体もでるようなアクションゲームを考えてみましょう。

プレイヤーがタッチあるいはマウスクリックしたときに、どのキュラゲを指しているかを判定したいとします。
そのとき、ナイーブに1キャラクターごとに1ピクセル単位で処理していたら、計算時間は大変なオーダーになってしまいます。
この当たり判定を効率化して欲しいと言われたら、あなたはどうしますか?

考えうるアプローチは多数ありますが、応用が効くアプローチの1つに、キャラクターを包含する円(3Dなら球)に近似するという方法があります。様々な図形の中で円を選ぶ理由は、ずばり後の処理が速いから。当たり判定の際に回転の影響を受けませんし、ビリヤードのような物理演算を伴う計算も円なら容易です。

というわけで、キュラゲのビットマップ画像から機械的に生成した点群データから最小包含円を求めてみましょう。
点群データはCSV形式で用意されており、ここ(https://dl.dropboxusercontent.com/u/110505645/CodeIQ/201304/points.zip)からダウンロードして下さい。
なお、CSVのカラム順序はX軸(右方向+)、Y軸(下方向+)となっております。

プログラムの実装について、CSVはダウンロードしたものを標準入力経由で受け取るか、ソースコード内に埋め込む形で取り込むものとし、求めた最小包含円(中心位置・半径)をfloat以上の精度で標準出力に返して下さい。

実装に用いる言語、またアルゴリズムは自由ですが、動作確認のため http://ideone.com/でコンパイル・実行できるようにして下さい。
もし、処理時間の制約からideone.com上での実行が難しい場合は、開発環境に関する情報を添えて提出して下さい。
なおソースコードは1ファイルに納めるようお願い致します。

完成したコードは、テキストファイル(.txt)にはりつけ、ファイルアップロードより提出してください。

この解説記事を読んで、計算幾何学に興味を持った方は、
現在、別の計算幾何学問題がでていますので、挑戦してみてはいかがでしょうか。

問題解いて、stakemuraさんからフィードバックもらうと、より一層、計算幾何学の理解が深まるかも!?

「キュラゲの重心を求めよう」
https://codeiq.jp/ace/stakemura/q328
6月21日(金)AM10:00挑戦受付締切です。
f:id:codeiq:20130603193925p:plain