- 題名: Rectangleの重なり確認の高速化
- 日時: 2012/06/14 19:07:42
- ID: 30575
- この記事の返信元:
- （なし）
- この記事への返信:
- [30576] Re[1]: Rectangleの重なり確認の高速化2012/06/15 7:51:20
- ツリーを表示
DOBON.NETプログラミング掲示板過去ログ
今はテストで固定の「string text = System.String.Format("番号{0}", i);」を対象にして
その場で10001個生成しながらすべての処理を行っていますが、
実際に使う際には、テキストのアイテムは「操作中に」都度増えていくものですか？
それとも、ファイルやDBから一気に読んできたものをループで今のように一括で求めなけばならないものですか？
前者なら、指定フォントでのサイズ情報だけはアイテムが作られるタイミングで一緒に求めて持っておくことで
時間を分散できますが。
（…その場合でもフォントの変更をかけた際には全アイテムの再計算ですけどね。）
気になったのですが、
[1]「列」毎にばらばらで計算されて、下の段のアイテムの開始位置が隣の列とずれていってもよいのですか？
[2]アイテムが最終的に段・列できれいな格子状に配置されるのがよいのですか？
（多分欲しいのは[2]ですよね？）
で、ですが。
送った順に配置するだけのようですから…その前提で書きます。
「time / _RulerPixelUnit」を使うことで横（「列」）がある個数になれば次の「段」になる仕組みなのですから、
前の「段」の同じ「列」位置のボックスのサイズと位置さえ分かれば別途の処理で検証に行ったりしなくてもY開始位置を求められると思います。
（※もちろん、「time / _RulerPixelUnit」で求められる「段」が0段目の際には存在しない段を見に行ってしまいますから
前の段を見ないようにします。最初の段は固定の開始位置で。0にするか10にするか知りませんが。）
[1]の場合：
同じ「列」にある、直前の段のアイテムの「Y開始位置＋高さ」に空けたい固定の隙間分（10とか）を加算した値が
その列の次の段のY開始位置になると思います。
[2]の場合：
もし他の列も考慮して段のY開始位置を揃えてきれいな五目格子にしたい場合は、
前の段の中で、「段」内の一番高さが大きくなったアイテムの「Y開始位置＋高さ」に、空けたい固定の隙間分（10とか）を加算した値が、
今設定したい方の「段」の全アイテムのY開始位置です。
（書くまでもないですが、今のアイテムの「段」はtimeと_RulerPixelUnitの商、「列」はtimeと_RulerPixelUnitの剰余で求められます。）
変なこと書いてたらすみません。
おはようございます。 私の理解力不足でよく読み取れず変なことを書きましたが、30581に図入りで書き込みをいただきとてもよく判りました。 …失礼しました。（が、またもや違ったら、すみません。） まず気になるのですが、 measureStringの引数に中途半端に大きめな「1000」を指定してありますが、 文字列がひとつのアイテム内では折り返さない予定（そこまで長い文字列は来ない）という意味合いでしょうか、 それとも折り返して高さ自体が変動することもちゃんと想定はしておきたいのでしょうか。 もしアイテム内での折り返しも想定しておきたい場合、今のコードでは問題があると思います。 無限ループ内で位置チェックをしながら段階的にずらすようですが、 その際のずらし量（スキップ量）が「System.Convert.ToInt32(size.Height + 10f)」、 つまり今回のアイテムの高さを基準にしているため、 今回のアイテムがたまたま折り返しのある２行分のボックスになった際を考えると、 無限ループの一回目で何かと位置が重なると、次の候補位置は本来目標としたい「１行分下の位置」ではなく、 一気に「２行下の位置」になってしまいます。 （自分のY開始位置を求める際に自アイテムの高さを使用してスキップしてはだめです。飛びすぎますので。） （ところどころ変な縦の隙間ができてきれいに揃わなくても別に重ならなければよいなら、 気にしないで大丈夫な性質のものですが。） 「縦を間引いて高速化する＆折り返しも想定はする」、ある程度動くコードを添付します。 （自宅のPCにはVB Expressしかないので少し判りにくいかもしれませんが、内容はC#そのままです。…会社行けばStudioあるんですが。） 家のしょぼいPCで試すと、元コードをそのままVB.NETに変えたものと直接比較して（数十倍くらい）速くなりました。 このコード自体もそれなりに正しく動くと思いますが、 いい加減なコードそのものより方法の方の話として、 ・二次元配列FILLで使用領域を管理。（※コードサンプルは、この配列が溢れない想定でしか組んでません。横方向だけはfor文にインラインifつけてますが。） ・その際、横方向はドットか何かしらのレベルで細かいまま管理するが縦方向は単に「行」（段）として管理して縦だけでも数を劇的に減らす。 ・「行」のサイズは、あまりよいとは言えないと思うがとりあえず「あ」で算出。ここは色々トレードオフで考えてちゃんと検討してください。 ・現在の最下利用行を変数currentmaxYで記憶しておくことで、配列の続きがまだあってもそれより下を無駄に検証しないようにして速度を上げる。 という形で扱うようにしてみました。 ※適当に二次元配列として書いて処理開始時にredimしてますが、 C#ではジャグにするとか何かしらのコレクションを使うとか、適当に他のものを想像してください。 縦横方向のマス状態を管理できればよいだけなので。 （妙な時間ですがこれから寝ますので…おやすみなさい。）
分類:[.NET]
こんにちは。
数万件の形の違う図形(四角)を連続して横位置に配置します。
このとき、それぞれの図形のX軸は決まっているのですが
Y軸は図形が重ならないように配置したいのです。
以下のように図形をコレクションに入れて
重なりを確認しているのですが、件数が多くて速度が出ません・・・
＜スクリプトソース（一部抜粋）＞
private List<TextItem> _TextList = new List<TextItem>();
private List<Rectangle> _DrawList = new List<Rectangle>();
private DrawControl()
{
using (Graphics g = this.CreateGraphics())
{
for (int i=0; i<=10000; i++)
{
string text = System.String.Format("番号{0}", i);
double time = i;
Rectangle rect = CalculateItemBounds(g, text, time);
_TextItems.Add(new TextItem(text, time, rect));
}
g.Dispose();
}
}
private Rectangle CalculateItemBounds(Graphics graphics, string text, double time)
{
StringFormat sf = new StringFormat(StringFormatFlags.MeasureTrailingSpaces);
SizeF size = graphics.MeasureString(text, this.Font, 1000, sf);
int x = System.Convert.ToInt32(time / _RulerPixelUnit);
int y = 0;
int w = (int)size.Width;
int h = (int)size.Height;
Rectangle rect = new Rectangle(x, y, w, h);
while (true)
{
if (CheckItemBounds(rect))
{
break;
}
rect.Y += System.Convert.ToInt32(size.Height + 10f);
}
_DrawList.Add(rect);
return rect;
}
private bool CheckItemBounds(Rectangle rect)
{
foreach (Rectangle r in _DrawList)
{
if (r.IntersectsWith(rect))
{
return false;
}
}
return true;
}
何か良い案は無いでしょうか？
個人的には白紙の用紙に図形を書いていき
余白部分が取得できるような方法が出来ればと思っているのですが
方法がいまいち分かりません。