Q&A
回答ありがとうございます
＞逆引きできるよう各点にインデックスを作るのは現実的ではありません。
これは、図形が移動するたびにインデックスを作り直さなければならないから、ということでしょうか
>それである程度絞り込んでおけばいいのではないでしょうか？
ある程度絞り込んでも、その中ではすべての図形に対してループする、ということですよね
この方針で考えてみたいと思います
いつもお世話になっております。
現在簡易的なCAD(2D)を作っております。
色々模索している状況ではありますが、
図形を二次元平面に並べたときに、
指定されたある点を占有している図形を求めるにはどうすればよいでしょうか
例えば長方形がいくつか、座標平面に存在するとして、
点(5,2)を占有している長方形は何番か、みたいなことが知りたいです
まさか、すべての図形に対してループ文で、「お前は点(5,2)を占有しているか？」なんて聞くのは違うと思いますし(この方法だと平面に存在する図形が多くなればなるほど、特定に時間がかかるので)、、、
方針としてどのようなものがありますでしょうか
下の図で説明させていただきますと、
①(2,3)に存在する図形はあるか、という入力に対して、
四角形Iを返すような方法、
同様に②(5,6)では
四角形II、四角形IIIを返し、
③では「存在しません」を返します
この例ではいずれも四角形の領域内(③以外)ですが、線分上や円弧上、が最終的な目標です(CADでは図形が閉じているとは限らず、むしろ選択の対象はある線(直線または曲線)なので
(もしかしたらゲームなんかでこの考え方があるんじゃないかと思い、タグに一応Unityを入れさせていただきました)
--追記--
お二方から回答いただき、今回の方針としては、(範囲を絞り込んで)すべての図形に対して座標占有の有無の問い合わせをする、ということで実装したいと思います。
ところで、まだ疑問が残るのでこちらにも回答いただけると助かります
人間が、このような図形を見てある座標を指さした場合、
(重なっているかは別として)ピンポイントでそこに描かれている図形を知ることができます
しかし、プログラム上で似たようなことを実現しようとしたら、
範囲を絞り込む等したとしても、最終的には、その周辺に存在する図形すべてに対して「ある座標」を占有しているかどうか問い合わせるのが普通、ということでしょうか
人間がやるように、ピンポイントで図形を見つけるにはそれこそ、すべての座標において(といっても、0.1、0.01単位でみていくと無数になる)インデックスを作らなければならないという、非現実的なことになりますでしょうか
回答4件
0
まさか、すべての図形に対してループ文で、「お前は点(5,2)を占有しているか？」なんて聞くのは違うと思いますし(この方法だと平面に存在する図形が多くなればなるほど、特定に時間がかかるので)、、、
...なんで? たかだかO(N)でしょ? 図形いっこについての存在判定に1μ秒かかったとして、図形1000個で1㍉秒。それじゃご不満ですか?
投稿2017/04/20 02:37
総合スコア16614
0
ベストアンサー
図形がいくつあるのか知りませんが、全部に聞く以外にないと思います。
逆引きできるよう各点にインデックスを作るのは現実的ではありません。
図形の大まかな位置とサイズを示すプロパティがあるのではないかと思いますが、それである程度絞り込んでおけばいいのではないでしょうか？
最終的なヒットテストには Region.IsVisible メソッドが使えるのではないかと思います。
投稿2017/04/20 02:41
総合スコア28660
インデックスを作り直さなければならないどころか、
分解能を上げていくにつれてインデックスの数が爆発的に増えることに気が付きました
確かに非現実的ですね
WYSIWYG なら数万の図形が全部バラバラというわけではなく、おそらくグループ化されているのではないかと思います。であれば、グループ化した時点で含まれる図形の Region を合成したものをグループの Region とすれば、グループの数だけヒットテストすればいいことになるので、数がかなり減らせるのではないでしょうか？
仰る通り、グループ化されております
具体的な絞り込み方のアドバイス感謝です
まずはとりあえず、全図形探索で実装してみて、
パフォーマンスを見つつ、グループ化していきたいと思います
>逆引きできるよう各点にインデックスを作るのは現実的ではありません。
もう一画面分のメモリを確保し、そこにインデックスに基づくRGB値で同時に描画を行い（アンチエイリアスなし）マウスでクリックした位置のRGB値を調べてインデックスに変換するという操作を行えば、倍率が変わろうと画面のサイズは固定ですのでいけるんじゃないでしょうか?識別できるインデックスの範囲はRGB値の範囲になってしまいますが数万のオーダーなら大丈夫なのではないかと、最前面の図形しか選択できないという欠点はありますが......
100ピクセル×100ピクセルで1万です。また画像を使うんだったら配列を使った方が速いと思います。静止画ではなく、配置・移動・拡大縮小をリアルタイムに行う必要があります。
1万あれば1万を全探索するという事ではなく
クリックされた座標でインデックス値が返るという形です
100ピクセル×100ピクセル×24bit ≒ 29KB程度です
1980*1080 なら6MB程度となりますのでメモリ的には
そう問題ではないかと
また普通のCADソフトでは配置・移動・拡大縮小の最中や直後に
選択操作は行われないと思われます
ですので0.1秒でオブジェクト追加orアフィン変換・画面表示を行ったとしたら
その後0.1秒でもう一画面分の方も再描画すればいいのではないでしょうか?
それでは、回答されたらいかがでしょうか？
すみません
Zuishinさんが書かれた
「逆引きできるよう各点にインデックスを作る」
というのはよくよく考えてみれば結構いい案だと感じましたので
こちらにコメントいたしました
Zuishinさん自身がこういった可能性も含めた上で
現実的ではないと評価されるのでしたら
そうなのだと思います
失礼いたしました
いえ、現実的でないと言うのは私が勝手に思ったことですから。よく練ればば十分なパフォーマンスが得られるのかもしれません。
0
基本的には総当りでやってもそれほど重い処理ではないと思います。
最初の方もおっしゃっていますが、例え数万個あってもそれほど処理時間はかからないかと。
ただ、判定する図形が複雑化してくる可能性がある場合はまたちょっと話が変わってきます。
その場合はまず、ざっくりと判定するためのBox、いわゆるAABB（Axis-Aligned Bounding Box：軸並行境界ボックス）と呼ばれる、対象図形を四角ですっぽりと覆う判定のための範囲矩形を計算しておきます。
そして判定が必要なときはそれとの判定を行います。
参考: その11 AABBと点の最短距離
もしその判定で「含まれている」と判断された場合には、続けて詳細の形を元に「本当に」含まれているか確認する、という手順で処理を行います。
ちなみに、判定するオブジェクトがさらに爆発的に増える場合は「4分木分割」などを利用して、判定するは何をさらに限定することもできます。
これは、空間をいくつかの格子に分割して、それぞれの格子に含まれる図形同士だけで判定を行うため、非常に判定処理が早くなります。
とはいえ、実装も多少複雑になるので、判定数的に無理が出てきたときに考え始めるのでいいかと思います。
投稿2017/04/20 03:00
総合スコア2283
御礼が遅くなり申し訳ありません
皆様からの回答で、方向性はわかりましたしあとはパフォーマンスの問題なんだな、と感じています。
いただいたリンク先が非常に勉強になり、今回質問した件以外にもさまざまなテクニックが紹介されており非常に助かりました。
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2017/04/20 02:45
2017/04/20 02:59