点を美しく配置するには
今日は朝から
「正方形の中に美しく指定された個数の点を打つ方法」について考えていた。
比戸君と話していて、
とりあえず1辺の頂点数が奇数個であるような正方形格子状に限定して力学的に反発する点を位置エネルギーが最小になるように配置する、という方法である程度配置してみて、その結果から規則性を抽出して高速に美しく配置するアルゴリズムを作ろうと思い立ったのがちょうど100分前。
で、結果は出たんだけど
…3とか7とか10とか11とか14とか…美しくない…。15なんか、なにそれ、イトマキエイ？
>>> draw()
1
*
0.0593424583292
2
- - *
- - -
* - -
0.0770097875568
3
- - *
- - -
* - *
0.0756780540544
4
* - *
- - -
* - *
0.0737931776245
5
* - *
- * -
* - *
0.0751659777989
6
* * *
- - -
* * *
0.0781143972209
7
* * *
- - *
* * *
0.0798704863328
8
* * *
* - *
* * *
0.0825395406399
9
* * *
* * *
* * *
0.07647033352
10
* - * - *
- - - * -
* - * - *
- - - - -
* - * - *
9.37996197841
11
* - * - *
- - - * -
* - - - *
- * - * -
* - * - *
19.8308106198
12
* - * - *
- * - * -
* - - - *
- * - * -
* - * - *
31.0727969616
13
* - * - *
- * - * -
* - * - *
- * - * -
* - * - *
47.1632179509
14
* - * * *
- * - - *
* - - * -
- * - - *
* - * * *
56.0500784318
15
* * - * *
* - * - *
- * - - *
* - - * -
* * * - *
52.5275826956
16
* * - * *
* - * - *
- * - * -
* - * - *
* * - * *
41.2388608049
17
* * * * *
* - - - *
* - * - *
* - - - *
* * * * *
28.7111300459
18
* * * * *
* - - - *
* - * - *
* - * - *
* * * * *
16.9885030081
19
* * * * *
* - * - *
* - - * *
* - * - *
* * * * *
8.46026967115
20
* * * * *
* - * - *
* * - * *
* - * - *
* * * * *
3.58321518517
21
* * * * *
* * - * *
* - * - *
* * - * *
* * * * *
1.30305248293
22
* * * * *
* * - * *
* - * - *
* * * * *
* * * * *
0.52957596566
23
* * * * *
* * * * *
* - * - *
* * * * *
* * * * *
0.299685015833
24
* * * * *
* * * * *
* * - * *
* * * * *
* * * * *
0.203836800487
しょんぼりですな。どうしようか。
正方格子上に配置するのをあきらめれば同心円状に配置する方法が考えられるが…。うーん。
おまけのえぐいソースコード。まぁ、高々48行だけどもね。体に悪い電波が出てそうなコードだ。
class RecPlace:
def __init__(self, num, width):
self.end = width * width
self.width = width
self.minPower = num * num
self.dig([], 0, 0.0, num - 1)
def dig(self, curList, start, curPower, level):
for i in range(start, self.end - level):
x = i % self.width
y = i / self.width
incPower = 0.0
for (px, py) in curList:
incPower += 1.0 / ((px - x) ** 2 + (py - y) ** 2)
nextPower = curPower + incPower
nextList = curList + [(x, y)]
if nextPower > self.minPower:
continue
if level == 0:
self.minPower = nextPower
self.minList = nextList
continue
self.dig(nextList, i + 1, nextPower, level - 1)
def draw():
from math import sqrt, ceil
from time import clock
for n in range(1,25):
start = clock()
print n
# minimal covering square
root = -1
while True:
root += 2
if n <= root * root:
break
r = RecPlace(n, root)
for i in range(root):
for j in range(root):
if (i,j) in r.minList:
print "*",
else:
print "-",
print
print clock() - start
print
Comments
...
by
Nekama
@2005-07-04 13:29
もっと密度を落とさないといけないやろう．．．
格子点を連続近似できるくらい．
...
by
nishio
@2005-07-05 09:58
これは計算を繰り返して収束させるタイプ(local minimumに陥りやすい)じゃなくて全探索なので、密度を落としても収束する場所は変わらないと思う。そもそも3点の時にL型じゃなくてV型に並んで欲しかったのだけどそうはならなかったので、例えば反発力を反２乗じゃなくて反３乗にするとかそういう変更が必要なのかもなぁ、と。あっ、いま試算してみたら反４乗の力でもまだL型の方が優勢か…反６乗なら逆転するようだけど。
あと連続近似できるくらいに密度を落とすってことはそれこそ「格子上に乗る」っていう条件を満たしていないも同然なので目指していた方向と逆だね。
...
by
kisaragi
@2005-07-05 16:16
これみてからNekamaと色々議論してみた。
でもどうやら私の場合「美しいの定義」が若干ずれてるみたいでだめかなぁ。そういえば3のときにＶ字型に並ぶ方法も議論で出てきたかも。どの方法だったかなぁ…。
...
by
Nekama
@2005-07-14 15:04
全ての点間のマンハッタン距離の和を最大にする問題に落とした時だね>kisaragi
格子点上で計算する以上直線距離で計算するのもおかしい気がする．
格子点上の配置という問題だけど，連続座標で各点が半径をもつ剛体だとして座標をだしたあと，最も近い格子点へ引き込むようにするとか．
どっちにしろ3点を3*3の格子点上に配置する場合は結果はL字になるね．
マンハッタン距離の和でLとVが同じポテンシャルを持つ．
距離ノルムの定義をいじってみては？
このページは静的なアーカイブなので新しいコメントは受け付けておりません。ご意見ご感想はお気軽にメールでどうぞ。coreblog「あっとまーく」nishiohirokazu.org。
Trackbacks