質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.51%

  • C#

    9036questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

  • Unity

    5500questions

    Unityは、ユニティテクノロジーが開発したゲームエンジンです。 主にモバイルやブラウザ向けのゲーム製作に利用されていましたが、3Dの重力付きゲームが簡単に作成できることから需要が増え、現在はマルチプラットフォームに対応しています。 言語はC言語/C++で書かれていますが、C#、JavaScript、Booで書かれたコードにも対応しています。

  • C

    4527questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • アルゴリズム

    500questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

二次元座標、指定した座標に存在するオブジェクト(図形)の逆引き方法

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,694

ElecDove

score 237

いつもお世話になっております。

現在簡易的なCAD(2D)を作っております。

色々模索している状況ではありますが、
図形を二次元平面に並べたときに、
指定されたある点を占有している図形を求めるにはどうすればよいでしょうか

例えば長方形がいくつか、座標平面に存在するとして、
点(5,2)を占有している長方形は何番か、みたいなことが知りたいです

まさか、すべての図形に対してループ文で、「お前は点(5,2)を占有しているか?」なんて聞くのは違うと思いますし(この方法だと平面に存在する図形が多くなればなるほど、特定に時間がかかるので)、、、

方針としてどのようなものがありますでしょうか

下の図で説明させていただきますと、
①(2,3)に存在する図形はあるか、という入力に対して、
四角形Iを返すような方法、

同様に②(5,6)では
四角形II、四角形IIIを返し、

③では「存在しません」を返します

この例ではいずれも四角形の領域内(③以外)ですが、線分上や円弧上、が最終的な目標です(CADでは図形が閉じているとは限らず、むしろ選択の対象はある線(直線または曲線)なので

イメージ説明

(もしかしたらゲームなんかでこの考え方があるんじゃないかと思い、タグに一応Unityを入れさせていただきました)

--追記--

お二方から回答いただき、今回の方針としては、(範囲を絞り込んで)すべての図形に対して座標占有の有無の問い合わせをする、ということで実装したいと思います。

ところで、まだ疑問が残るのでこちらにも回答いただけると助かります

  • - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

人間が、このような図形を見てある座標を指さした場合、
(重なっているかは別として)ピンポイントでそこに描かれている図形を知ることができます

しかし、プログラム上で似たようなことを実現しようとしたら、
範囲を絞り込む等したとしても、最終的には、その周辺に存在する図形すべてに対して「ある座標」を占有しているかどうか問い合わせるのが普通、ということでしょうか

人間がやるように、ピンポイントで図形を見つけるにはそれこそ、すべての座標において(といっても、0.1、0.01単位でみていくと無数になる)インデックスを作らなければならないという、非現実的なことになりますでしょうか

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 4

+2

まさか、すべての図形に対してループ文で、「お前は点(5,2)を占有しているか?」なんて聞くのは違うと思いますし(この方法だと平面に存在する図形が多くなればなるほど、特定に時間がかかるので)、、、 

...なんで? たかだかO(N)でしょ? 図形いっこについての存在判定に1μ秒かかったとして、図形1000個で1㍉秒。それじゃご不満ですか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/04/20 11:45

    回答ありがとうございます

    この方法でいいのでしょうか

    図形の数は、最大で数万程度を考えています

    人間が、グラフに図形を書いて、ある点を指さした場合は、
    ピンポイントで一発で、その図形を特定できます(とりあえず重なっているとかは考えずに)

    しかし、プログラム上で実現する場合は、(考え方としては)すべての図形に対してその点を占有しているか確認するのが妥当、ということになりますでしょうか

    実際のCADシステムなどではどのような実装をしているのか、合わせてご教授いただけると助かります

    キャンセル

  • 2017/04/20 11:59

    妥当か否かは要求次第だし性能次第。もっとも簡単な方法(=総当たり)でお試し実装すりゃえぇやん。
    それで満足するパフォーマンス出るんならそれでよし。まずは実装/実測じゃないですかね?

    もうちょびっと速くしたいってんなら、たとえば数万の図形情報を左端の位置でソートしておけば、とある座標を指定したとき「絶対に占有しない」図形の排除はO(logN)でできますよね(binary-searchによって)

    キャンセル

checkベストアンサー

+1

図形がいくつあるのか知りませんが、全部に聞く以外にないと思います。
逆引きできるよう各点にインデックスを作るのは現実的ではありません。

図形の大まかな位置とサイズを示すプロパティがあるのではないかと思いますが、それである程度絞り込んでおけばいいのではないでしょうか?
最終的なヒットテストには Region.IsVisible メソッドが使えるのではないかと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/04/20 11:47

    回答ありがとうございます

    >逆引きできるよう各点にインデックスを作るのは現実的ではありません。
    これは、図形が移動するたびにインデックスを作り直さなければならないから、ということでしょうか

    >それである程度絞り込んでおけばいいのではないでしょうか?
    ある程度絞り込んでも、その中ではすべての図形に対してループする、ということですよね

    この方針で考えてみたいと思います

    キャンセル

  • 2017/04/20 11:54

    インデックスを作り直さなければならないどころか、
    分解能を上げていくにつれてインデックスの数が爆発的に増えることに気が付きました

    確かに非現実的ですね

    キャンセル

  • 2017/04/20 11:54

    WYSIWYG なら数万の図形が全部バラバラというわけではなく、おそらくグループ化されているのではないかと思います。であれば、グループ化した時点で含まれる図形の Region を合成したものをグループの Region とすれば、グループの数だけヒットテストすればいいことになるので、数がかなり減らせるのではないでしょうか?

    キャンセル

  • 2017/04/20 11:57

    仰る通り、グループ化されております

    具体的な絞り込み方のアドバイス感謝です

    まずはとりあえず、全図形探索で実装してみて、
    パフォーマンスを見つつ、グループ化していきたいと思います

    キャンセル

  • 2017/04/24 10:07

    >逆引きできるよう各点にインデックスを作るのは現実的ではありません。
    もう一画面分のメモリを確保し、そこにインデックスに基づくRGB値で同時に描画を行い(アンチエイリアスなし)マウスでクリックした位置のRGB値を調べてインデックスに変換するという操作を行えば、倍率が変わろうと画面のサイズは固定ですのでいけるんじゃないでしょうか?識別できるインデックスの範囲はRGB値の範囲になってしまいますが数万のオーダーなら大丈夫なのではないかと、最前面の図形しか選択できないという欠点はありますが......

    キャンセル

  • 2017/04/24 10:10 編集

    100ピクセル×100ピクセルで1万です。また画像を使うんだったら配列を使った方が速いと思います。静止画ではなく、配置・移動・拡大縮小をリアルタイムに行う必要があります。

    キャンセル

  • 2017/04/24 11:11

    1万あれば1万を全探索するという事ではなく
    クリックされた座標でインデックス値が返るという形です
    100ピクセル×100ピクセル×24bit ≒ 29KB程度です
    1980*1080 なら6MB程度となりますのでメモリ的には
    そう問題ではないかと

    また普通のCADソフトでは配置・移動・拡大縮小の最中や直後に
    選択操作は行われないと思われます
    ですので0.1秒でオブジェクト追加orアフィン変換・画面表示を行ったとしたら
    その後0.1秒でもう一画面分の方も再描画すればいいのではないでしょうか?

    キャンセル

  • 2017/04/24 11:47

    それでは、回答されたらいかがでしょうか?

    キャンセル

  • 2017/04/24 12:39

    すみません
    Zuishinさんが書かれた
    「逆引きできるよう各点にインデックスを作る」
    というのはよくよく考えてみれば結構いい案だと感じましたので
    こちらにコメントいたしました

    Zuishinさん自身がこういった可能性も含めた上で
    現実的ではないと評価されるのでしたら
    そうなのだと思います
    失礼いたしました

    キャンセル

  • 2017/04/24 12:58

    いえ、現実的でないと言うのは私が勝手に思ったことですから。よく練ればば十分なパフォーマンスが得られるのかもしれません。

    キャンセル

0

基本的には総当りでやってもそれほど重い処理ではないと思います。
最初の方もおっしゃっていますが、例え数万個あってもそれほど処理時間はかからないかと。

ただ、判定する図形が複雑化してくる可能性がある場合はまたちょっと話が変わってきます。

その場合はまず、ざっくりと判定するためのBox、いわゆるAABB(Axis-Aligned Bounding Box:軸並行境界ボックス)と呼ばれる、対象図形を四角ですっぽりと覆う判定のための範囲矩形を計算しておきます。
そして判定が必要なときはそれとの判定を行います。

参考: その11 AABBと点の最短距離

もしその判定で「含まれている」と判断された場合には、続けて詳細の形を元に「本当に」含まれているか確認する、という手順で処理を行います。

ちなみに、判定するオブジェクトがさらに爆発的に増える場合は「4分木分割」などを利用して、判定するは何をさらに限定することもできます。

参考: その8 4分木空間分割を最適化する!(理屈編)

これは、空間をいくつかの格子に分割して、それぞれの格子に含まれる図形同士だけで判定を行うため、非常に判定処理が早くなります。
とはいえ、実装も多少複雑になるので、判定数的に無理が出てきたときに考え始めるのでいいかと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/05/02 12:44

    御礼が遅くなり申し訳ありません

    皆様からの回答で、方向性はわかりましたしあとはパフォーマンスの問題なんだな、と感じています。

    いただいたリンク先が非常に勉強になり、今回質問した件以外にもさまざまなテクニックが紹介されており非常に助かりました。

    キャンセル

0

私自身は理解していないのですが、平面走査法というのがニーズにあっていると思います

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • C#

    9036questions

    C#はマルチパラダイムプログラミング言語の1つで、命令形・宣言型・関数型・ジェネリック型・コンポーネント指向・オブジェクティブ指向のプログラミング開発すべてに対応しています。

  • Unity

    5500questions

    Unityは、ユニティテクノロジーが開発したゲームエンジンです。 主にモバイルやブラウザ向けのゲーム製作に利用されていましたが、3Dの重力付きゲームが簡単に作成できることから需要が増え、現在はマルチプラットフォームに対応しています。 言語はC言語/C++で書かれていますが、C#、JavaScript、Booで書かれたコードにも対応しています。

  • C

    4527questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • アルゴリズム

    500questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。