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

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

ただいまの
回答率

88.93%

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

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 2,758

ElecDove

score 257

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

現在簡易的な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/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

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

  • ただいまの回答率 88.93%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

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