HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2017
0228
スペースサイズの違う矩形を隙間なく並べたい。3解決


スペース

リンク

2017/2/28(Tue) 14:14:43|NO.78334

サイズの違う矩形を隙間なく並べたいのですが、
矩形の数が多くなってくるとどうしても処理に時間がかかってしまいます。
もっと効率のいい処理方法があるとは思うのですが、なかなかな思いつきません。
どうか皆様のお力添えを頂けないでしょうか?

#include "d3m.hsp" #include "hspmath.as" randomize sx=800:sy=800 screen 0,sx,sy dim 矩形sx,100 dim 矩形sy,100 dim 矩形posx,100 dim 矩形posy,100 dim 矩形_判定用X,100 dim 矩形_判定用Y,100 point_a = 0,0;点A 開始時間.0 = d3timer() repeat 100 矩形数=cnt 追加posx=0:追加posy=0:追加sx=100-((cnt/10)*10):追加sy=100-((cnt/10)*10);新たに追加する長方形のサイズ 追加sx+(追加sx\2):追加sy+(追加sy\2);偶数にする 追加_被り判定用X=(追加sx)/2:追加_被り判定用Y=(追加sy)/2;被り判定で使う。 最小距離=double(sx+sy) 追加可能フラグ=0;どこにも追加できない時は0、どこかに追加できる時は1 ;様々な組み合わせで既にある長方形の横に置いてみる。 ;最終的な位置は最も0,0(左上)に近かった場所する。 repeat 矩形数;X ct0=cnt repeat 矩形数;X 追加posx=矩形posx.ct0+矩形sx.ct0+1;右側に置いてみる。 追加posy=矩形posy.cnt gosub*被りチェック 追加posx=矩形posx.ct0;下側に置いてみる。 追加posy=矩形posy.cnt+矩形sy.cnt+1 gosub*被りチェック 追加posx=矩形posx.ct0+矩形sx.ct0+1;右下に置いてみる。 追加posy=矩形posy.cnt+矩形sy.cnt+1 gosub*被りチェック loop loop if 矩形数!0:{ if 追加可能フラグ=0:stop;どこにも追加できないので停止 矩形sx.矩形数=追加sx 矩形sy.矩形数=追加sy 矩形posx.矩形数=最適posx 矩形posy.矩形数=最適posy 矩形_判定用X.矩形数=(矩形sx.矩形数)/2 矩形_判定用Y.矩形数=(矩形sy.矩形数)/2 }else{;一番最初の長方形は左上に追加 矩形sx.矩形数=追加sx 矩形sy.矩形数=追加sy 矩形posx.矩形数=追加posx 矩形posy.矩形数=追加posy 矩形_判定用X.矩形数=(矩形sx.矩形数)/2 矩形_判定用Y.矩形数=(矩形sy.矩形数)/2 } ;描画 color rnd(200),rnd(200),rnd(200) boxf (矩形posx.矩形数),(矩形posy.矩形数),(矩形posx.矩形数+矩形sx.矩形数)-1,(矩形posy.矩形数+矩形sy.矩形数)-1 title ""+(d3timer()-開始時間.0)+"ms" await loop stop *被りチェック if 追加posx+追加sx<=sx & 追加posy+追加sy<=sy:{;画面からはみ出てないか確認 被りフラグ=0;これが1なら被りあり repeat 矩形数 if(((追加posx+追加_被り判定用X)-(矩形posx.cnt+矩形_判定用X.cnt))/(追加_被り判定用X+矩形_判定用X.cnt) | ((追加posy+追加_被り判定用Y)-(矩形posy.cnt+矩形_判定用Y.cnt))/(追加_被り判定用Y+矩形_判定用Y.cnt)) == 0 { 被りフラグ=1:break } loop if 被りフラグ=0:{ point_b = 追加posx,追加posy 距離=distance2(point_a, point_b);0,0(左上)との距離を計算。今までより近かったら記録。 if 最小距離>=距離:最小距離=距離:最適posx=追加posx:最適posy=追加posy:追加可能フラグ=1 } } return



この記事に返信する


スペース

リンク

2017/2/28(Tue) 16:37:17|NO.78337

一部、修正し忘れた箇所がありました。


追加posx=0:追加posy=0:追加sx=100-((cnt/10)*10):追加sy=100-((cnt/10)*10);新たに追加する長方形のサイズ



追加posx=0:追加posy=0:追加sx=rnd(100)+10:追加sy=rnd(100)+10;新たに追加する長方形のサイズ



motchy

リンク

2017/3/1(Wed) 04:14:51|NO.78341

(GitHub の private Gist を貼っつけたら突然 flag されたので codetter で出直し...)

これは面白い問題ですね。
画面をスプレッドシートとして扱い、空き領域を「セル」で管理したら爆速でした。

http://codetter.com/?p=1227

いやぁ〜 モジュール変数 最高!
現状ではセルを右及び下向きの単方向リストにしていますが、双方向にすれば高速化できそうです(行,列の挿入が少し面倒になりますが)。



スペース

リンク

2017/3/1(Wed) 10:40:53|NO.78342

>>motchyさん
「スプレッドシートとして扱う」というのは全く思いつかなかったので、目から鱗が落ちました。
motchyさんのおかげで数日悩んでいた問題は解決です。
わざわざ約400行もの長いソースコードを書いていただき本当に本当にありがとうございました。



ONION software Copyright 1997-2021(c) All rights reserved.