円に円を詰める問題が解けなかったのでsqliteで検索できるようにしてみた

2020年10月13日 07:25

この note について

タイトルでは数学っぽいタイトルになってますが、データベースのお話です。sqlite のことしかお話ししませんので、数学的な知見を得たい方はリンクをたどるか各自で調べてください。
最後の方に検索方法についてまとめてあります。データベースの作成については解説を一通り読んでください。一度作ればずっと使えます。

はじめに

大きな円に小さな円を充填するとき、最大でどれくらい詰められるのか。この一般解を求めるのは至難の業らしいのですが、これを計算してくれるサイトがあります。

https://ja.wolframalpha.com/examples/mathematics/geometry/packing-and-covering-problems/geometric-packing-in-2d/

しかし、いちいち入力しなければならないし、ソースも見当たりません。どこにソースがあるかわかる人、教えてください。

これとは別に円充填問題を頑張って求めて最適解を載せたサイトがあります。以下は円に円を詰める問題の2014年時点での最適解を載せたものになります。

http://hydra.nat.uni-magdeburg.de/packing/cci/

このサイトでは半径1の円の中に詰めたい円の数に合わせてその半径の最大値を連続で1～2600まで、その後飛び飛びで5000まで、それぞれの最適解を集めたものが掲載されています。
この最適解を利用して、詰める円の半径からその最密充填数（最大の充填可能な個数）を検索したり、最密充填数となる詰める円の半径を求めたいと思います。

検索方法の提案

C++ の std::map::find でキーバリュー型の検索をかけようかと思ったのですが、テーブルの大きさが半端じゃないんでメモリが足りなくなるかもしれません。そこで組み込み系でよく使う sqlite を使うことにしました。MySQL等、他の RDBMS を使ってる人はそちらを使っても良いでしょう。データベースを使って他のプログラミング言語からクエリを発行すれば様々な使い方ができると思います。

sqlite のインストールや操作方法は他のサイトに譲ります。私は Linux や Cygwin を使っているのでパッケージ管理プログラムでインストールしています。sqlite の操作については以下のサイトを参考にしました。Windows へのインストール方法も載っています。

https://www.dbonline.jp/sqlite/

座標データファイルのダウンロードと tsv 化

N=1 から連続で 2600 まで、それ以降は飛び飛びで5000まで、計 2736 種類ですが、充填数の最適解が求められていて、充填する円の半径や各円の中心の座標をテキストファイルとしてダウンロードできます。

まずは中心座標ファイルをダウンロードし、展開します。

$ mkdir cci && cd cci
$ wget http://hydra.nat.uni-magdeburg.de/packing/cci/txt/cci_coords.tar.gz
$ tar xvzf cci_coords.tar.gz

以下のコマンドでデータベースにインポートするためのタブ区切りファイル (tsv) を作成します。途中ファイルがないというエラーが出ますが気にしないでください。

$ for i in {1..5000};do cat cci$i.txt | sed -e "s%^%$i\t%" | awk '{print $1"\t"$2"\t"$3"\t"$4;}' ;done | tee all_center.tsv

以下のような tsv ファイルができます。

半径データファイルのダウンロードと tsv 変換

詰め込む円の最大充填数とその半径のデータを並べたファイルがあるのでダウンロードして tsv にします。

$ wget http://hydra.nat.uni-magdeburg.de/packing/cci/txt/radius.txt
$ cat radius.txt | awk '{print $1 "\t" $2;}' > radius.tsv

以下のような tsv ファイルができます。

1       1.000000000000000000000000000000
2       0.500000000000000000000000000000
3       0.464101615137754587054892683012
4       0.414213562373095048801688724210
5       0.370191908158750137702237641058
6       0.333333333333333333333333333333
7       0.333333333333333333333333333333
8       0.302593388348611302909204224934
9       0.276768653914155215717770973808
10      0.262258924190165855095630653709
11      0.254854701717148909608835737700
12      0.248163470571686841544054487132
13      0.236067977499789696409173668731
14      0.231030727971008638446179972284
15      0.221172539086390937264316484926
16      0.216664742924422421010647936933
17      0.208679665570499743200080125264
18      0.205604646759568224693193969093
19      0.205604646759568224693193969093
20      0.195224011018748878291305694833

データベース側の準備

先ほど作った tsv をインポートする準備をします。
まずはあくまで好みですが、標準でヘッダー表示をオン、表示をラインモードにするべく、 ~/.sqliterc というファイルを作成します。内容は以下の cat コマンドの結果を参考にしてください。MySQLっぽい表示にしたい場合は line ではなく table にしてください。

$ cat ~/.sqliterc
.headers on
.mode line

次にデータベースを新規に作成します。

$ sqlite3 cci.db
-- Loading resources from /home/ani/.sqliterc
SQLite version 3.32.3 2020-06-18 14:00:33
Enter ".help" for usage hints.
sqlite>

cci.db はファイル名で、カレントディレクトリにない場合はパス付で指定します。システムを移行する際、このファイルをコピーするだけでデータベースを移行できます。ちなみに拡張子は .sqlite とする人の方が多いです。

次に超基本的な使い方、起動と終了を解説します。
新規作成の時と同様、シェルに sqlite3 データベース名 と打って起動することでデータベースに接続できます。起動すると sqlite> とプロンプトが出るので、そこに .exit と入力することで終了します。

ではまずテーブルを作成していきます。

sqlite> CREATE TABLE cci_radius(num integer, radius real);
sqlite> CREATE TABLE center_coord(num integer, serial integer, x real, y real );

次に tsv をインポートします。

sqlite> .mode tabs
sqlite> .import ./radius.tsv cci_radius
sqlite> .import ./all_center.tsv center_coord
sqlite> .mode line

以上でデータベースの準備は終了です。
次は実際の検索について解説して行きます。

ここでテーブルを一つにしなかったのは、データベースを小さくして検索を少しでも速くするためです。半径も中心座標のテーブルの列に加えると実数型の同じデータが、例えば num = 5000 の行で 5000 個、その一つ前が 4495 なので 4495 個、全部合わせると 386万220 個、この列を num と半径だけのテーブルに分けることで 2736個の実数型データで済むようになります。num も同様に同じ数で膨れていますが、こちらは検索するための大事なキーなので省略はできません。

充填可能な円の数からその半径を知る

目的はタイトルの通り、半径1の円にN個詰められる円の最大の半径を検索するには以下のようなクエリを送ります。

select radius FROM cci_radius WHERE num = N;

まずは試しに、5～8個詰められる最大の半径をそれぞれ検索します。

sqlite> select radius FROM cci_radius WHERE num = 5;
radius = 0.37019190815875
sqlite> select radius FROM cci_radius WHERE num = 6;
radius = 0.333333333333333
sqlite> select radius FROM cci_radius WHERE num = 7;
radius = 0.333333333333333
sqlite> select radius FROM cci_radius WHERE num = 8;
radius = 0.302593388348611

注目すべきは 6個のときと 7個のときの半径が同じだということです。つまり、radius が 0.333333333333333 のときに詰められる個数を検索すると複数の答えが出る可能性があることを、幸いにもかなり初期の段階で知ることができました。この後にもいくつか出てきます。このことは次に記す逆の検索で重要な要素となります。

詰める円の半径から最密充填数を求める

先ほどとは逆に詰める方の円の半径から最密充填数を検索する方法です。
まず半径の指定方法です。半径が大きいほど詰められる数は減るので、最大数を求めるには where radius >= （半径）で検索し、それを降順に並べて一番上の一行を取得すればOKです。もし同じ半径で複数の行が存在しても大きい方が答えになるので二行目以降は必要ありません。

ここでは詳しく解説しませんが、where radius = 0.3141592… などと適当に打っても 0.333333333333333 と正確にコピペしても結果は出ません。この辺りについては実数型の精度について調べてください。

ではまず先ほど出した 8個の時の半径に近い値で検索します。
今回は実験的に半径も含めて 4行表示してみます。

sqlite> SELECT * FROM cci_radius WHERE radius >= 0.30 ORDER BY num DESC LIMIT 4;
  num = 8
radius = 0.302593388348611

  num = 7
radius = 0.333333333333333

  num = 6
radius = 0.333333333333333

  num = 5
radius = 0.37019190815875

望み通り一番上に 8個と出ています。ここで先ほど注目すべきだと書いた 6個か 7個のときの半径に近い 0.33 で一行だけ検索してみます。

sqlite> SELECT num FROM cci_radius WHERE radius >= 0.33 ORDER BY num DESC LIMIT 1;
  num = 7

6個ではなく 7個という結果が得られました。

「せっかくだから俺は、もっと大きな数を選ぶぜ！」

とは言ってもこのデータベースで検索できるのは 5000 までです。

sqlite> select radius FROM cci_radius WHERE num = 5000;
radius = 0.0133233215603473

つまり、半径が約 0.0133 より小さい円はすべて 5000個になってしまいますので注意してください。

sqlite> SELECT num FROM cci_radius WHERE radius >= 0.01 ORDER BY num DESC LIMIT 1;
 num = 5000
sqlite> SELECT num FROM cci_radius WHERE radius >= 0.001 ORDER BY num DESC LIMIT 1;
 num = 5000

また、連続しているのも 2600 までなので、それ以降は準備された値でしか検索できません。

充填数から充填した各円の中心座標を検索する

次は中心座標の表を検索します。
まずは充填数から、充填する円の中心と、最高密度となるように詰めた各円の中心座標との相対座標を検索します。

今回は試しに 8個で最密となるように充填した各円の座標を検索します。

select serial,x,y FROM center_coord WHERE num = 8;

以下のような結果が出力されます。（ .mode table にしてあります）

+--------+--------------------+--------------------+
| serial |         x          |         y          |
+--------+--------------------+--------------------+
| 1      | -0.302593388348611 | -0.628341645367214 |
| 2      | 0.302593388348611  | -0.628341645367214 |
| 3      | -0.679921171839088 | -0.155187570571976 |
| 4      | 0.679921171839088  | -0.155187570571976 |
| 5      | 0.0                | 0.0                |
| 6      | -0.545254445070411 | 0.434825910113495  |
| 7      | 0.545254445070411  | 0.434825910113495  |
| 8      | 0.0                | 0.697406611651389  |
+--------+--------------------+--------------------+

充填する円の半径から各円の中心座標を検索する

やっと２つに分けたテーブルを相互に活用するときが来ました。
充填する円の半径から外周となる円の中心から各円の中心への相対座標が得る方法です。
今回は試しに半径 = 0.33 で検索してみます。

中心座標のテーブルには半径が含まれていないので、半径のテーブルで半径から最密充填数を検索し、その値をサブクエリ（副問合せ）の入れ子にして中心座標のテーブルで検索します。

select serial,x,y FROM center_coord WHERE num = (SELECT num FROM cci_radius WHERE radius >= 0.33 ORDER BY num DESC LIMIT 1);

以下のような検索結果が出ます。

+--------+--------------------+--------------------+
| serial |         x          |         y          |
+--------+--------------------+--------------------+
| 1      | -0.333333333333333 | -0.577350269189626 |
| 2      | 0.333333333333333  | -0.577350269189626 |
| 3      | -0.666666666666667 | 0.0                |
| 4      | 0.0                | 0.0                |
| 5      | 0.666666666666667  | 0.0                |
| 6      | -0.333333333333333 | 0.577350269189626  |
| 7      | 0.333333333333333  | 0.577350269189626  |
+--------+--------------------+--------------------+

これは円の充填数が７個の時と同じ結果となります。

検索方法まとめ

目的別に検索方法をまとめておきます。個数を N、半径を R とします。

※データベースを作るところは解説をきちんと読んでください。

・充填可能な円の数からその半径を知る

select radius FROM cci_radius WHERE num = N;

・詰める円の半径から最密充填数を求める

SELECT num FROM cci_radius WHERE radius >= R ORDER BY num DESC LIMIT 1;

・充填数から充填した各円の中心座標を検索する

select serial,x,y FROM center_coord WHERE num = N;

・充填する円の半径から各円の中心座標を検索する

select serial,x,y FROM center_coord WHERE num = (SELECT num FROM cci_radius WHERE radius >= R ORDER BY num DESC LIMIT 1);

最後に

この note は、あるゲーム開発者からの質問に答える形で書いたものです。コンソール機などスタンドアローンなシステムではこのままだと使いにくいかもしれませんが、サーバーサイドに仕事を割り振れるタイプのゲームでは使えそうです。

C/C++やスクリプト言語から操作するところまで書きたかったんですが、長くなりそうなので、ここでひと区切りとさせていただきます。

この記事が気に入ったらサポートをしてみませんか？