- ベストアンサー
探索アルゴリズム
aという対象の位置は(x,y) その周辺10の距離内にいるモノを見つけたい このモノというのはたくさんあるとします。モノの座標は一覧としてもっています。 ｘ+10, x-10,y+10,y-10を境界にifで処理するとモノ一つに対して4度処理を必要として、モノの数だけ処理をする必要があり非効率だと思ったのですが他の効率的な方法が思い浮かびません なにかいい方法はありますか？
- who_ray_sis
- お礼率17% (15/87)
- CGI
- 回答数3
- ありがとう数13
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
- ベストアンサー
点（モノ）の数だけ処理するのを避けたいなら、 R木のように事前にデータを整理する必要があります。 いきなり探索するとしたら、総当りしかないでしょう。 また、「距離」は一般にはユークリッド距離を指します。 二つの点 (x1,y1) と (x2,y2) のユークリッド距離は √((x1-x2)^2 + (y1 - y2)^2) で求まります。 例として点(0,0)と(9,9)の距離は、約12.7になります。 つまり、(0,0)と(9,9)の距離は10を大きく超えています。 > ｘ+10, x-10,y+10,y-10を境界にifで処理すると とのことですが、それでは正しい判定はできません。 No.2さんの言うように、2点間の距離を計算して 2点間の距離をif文一回で判定すべきでしょう。 ユークリッド距離でなく、市街地距離やチェス盤距離で 内外判定したいなら、上の境界とif文ででもできますが。
関連するQ&A
- 経路探索のアルゴリズムを改善したい
実際はFlashで書いていましたが、アルゴリズムに関してなので、 多種方面の方にご教示・助言を頂きたいと思い、 わかる範囲での C# に書き換えこちらのカテゴリーで質問しています。 ■ ２次元配列に格納されているマップ情報を使い、特定の場所からの最短経路を全て出す ・マップに格納されている情報は、通行 可/不可 のみ ・経路の探索進行方向は縦横左右のみ ・障害物がないマス全てへの最短経路を求める ・障害物により辿りつけないマスは求める内容から除外 上記の目的・条件をもとに下記のようになりました。 C#だとほんの一瞬ですが、マップをこれより少し広くして行うと、Flash上では反復回数制御により強制的に止まってしまうため、探索用関数を改善したいと思っています。 同じ結果が得られれば全く違う内容でも構いません、何か良い案がありましたら、よろしくお願いします。 （ここでは静的なマップ内容ですが、実際は障害物の有無が動的に変わります） using System; namespace ConsoleApplication1 { class Program { static int count; static int[][] chMap;//歩数格納用配列 static bool[][] myMap;//マップ格納用配列 const int mx = 10; static void Main(string[] args) { int[] stP = { 1, 2 };//探索開始位置{Y,X} chMap = new int[mx][]; for (int i = 0; i < chMap.Length; chMap[i++] = new int[mx]) ; bool o = true;//障害物なし 通行可能 bool x = false;//障害物あり 通行不可能 myMap = new bool[mx][]; myMap[0] = new bool[mx] { o, o, o, o, o, o, o, o, o, o }; myMap[1] = new bool[mx] { o, o, o, o, o, o, o, x, o, o }; myMap[2] = new bool[mx] { o, o, o, o, o, o, o, x, o, o }; myMap[3] = new bool[mx] { o, o, o, o, o, o, o, x, o, o }; myMap[4] = new bool[mx] { o, o, o, o, o, o, o, x, o, o }; myMap[5] = new bool[mx] { x, x, x, o, o, o, o, x, o, o }; myMap[6] = new bool[mx] { o, o, o, o, o, x, x, x, o, o }; myMap[7] = new bool[mx] { o, o, o, o, o, x, o, o, o, o }; myMap[8] = new bool[mx] { o, o, o, o, o, x, o, o, o, o }; myMap[9] = new bool[mx] { o, o, o, o, o, x, o, o, o, o }; Write: count = 0; for (int Y = 0; Y < myMap.Length; Y++) { for (int X = 0; X < myMap[Y].Length; X++) { Console.Write(myMap[Y][X] ? "□ " : "■ "); chMap[Y][X] = myMap[Y][X] ? myMap.Length * myMap.Length : -1; } Console.WriteLine(); } Console.WriteLine(); G2P(stP[0], stP[1], 0); for (int Y = 0; Y < chMap.Length; Y++) { for (int X = 0; X < chMap[Y].Length; X++) { Console.Write(chMap[Y][X] == 0 ? "★ " : chMap[Y][X] == -1 ? "■ " : chMap[Y][X] == myMap.Length * myMap.Length ? "-- " : chMap[Y][X].ToString("00 ")); } Console.WriteLine(); } Console.WriteLine("\n探索用関数を " + count.ToString() + " 回 通りました"); Console.ReadKey(); goto Write; } //探索用関数 static void G2P(int y, int x, int n) { ++count; if (y < 0 || x < 0 || y >= myMap.Length || x >= myMap.Length) return; chMap[y][x] = n; if (x + 1 < mx && chMap[y][x + 1] > n + 1 && myMap[y][x + 1]) { G2P(y, x + 1, n + 1); } if (x - 1 >= 0 && chMap[y][x - 1] > n + 1 && myMap[y][x - 1]) { G2P(y, x - 1, n + 1); } if (y + 1 < mx && chMap[y + 1][x] > n + 1 && myMap[y + 1][x]) { G2P(y + 1, x, n + 1); } if (y - 1 >= 0 && chMap[y - 1][x] > n + 1 && myMap[y - 1][x]) { G2P(y - 1, x, n + 1); } } } }
- ベストアンサー
- C・C++・C#
- プログラミング初心者です。お知恵を貸してください。
閲覧ありがとうございます。 最近プログラミングを学び始めたのですが以下の処理がうまくいかず悩んでいます。 if (画像の現在位置X + 40 < タッチした位置の座標X, 画像の現在位置X - 40 > タッチした位置の座標X, 画像の現在位置Y + 40 < タッチした位置の座標Y , 画像の現在位置Y - 40 > タッチした位置の座標Y){ touch = true; } 画像の真ん中（添付した画像の水色の枠内）にポインタを置くとtouchがtrueになるようにしたいのですが真ん中以外にポインタを置いてもtouchがtrueになってしまいます。 数学も苦手で不等号の向きが間違っているのかなんなのか解りません。お知恵を貸してください。
- 締切済み
- C・C++・C#
- 距離、方位角から座標を求める方法
A点とB点があったとします。 求めたいのはB点の座標です。 わかっている情報は次の３つです。 ・A点の座標（x座標、y座標） ・A点とB点間の距離 ・A点からB点を見たときの方位角です。 この情報から求めようとすると、 B地点の座標はA地点から、 x座標が距離×sin（方位角）分、ずれた位置になり、 y座標が距離×cos（方位角）分、ずれた位置になる。 ここまでは分かってるんですが、 ここから座標に変換する方法が分かりません。 どうか教えてもらえますでしょうか？ よろしくお願いします。
- 締切済み
- 数学・算数
- n角形の重心を求めるアルゴリズム
平面2次元のn角形の頂点のデータがあります。n点の座標ですから(x,y)がn個並んでいます。そのような図形の図心（重心）の座標を計算するアルゴリズムがないでしょうか。最終的にはプログラムとして離散的な処理をするため、１％ぐらいの誤差は許容範囲です。n角形と言ってもせいぜいn=3,4,5,6程度です。 欲を言うと、３次元も考えており、平面に含まれることが分かっているn個の点（３次元空間内）を平面の２次元空間に変換して重心を求め、それを３次元空間に引き戻せば３次元での重心となります。そのためにも２次元での重心の座標を求めるアルゴリズムが必要なのです。 よろしくお願いします。
- ベストアンサー
- 数学・算数
- c言語によるアルゴリズム
やりたいことは、たくさんの画像をいくつかのグループ(1グループに画像が数十種類)用意し、入力画像とそれらを比較します。そして、最も入力画像に似ている画像があるグループを選び出します。画像自体はx-y座標に点がある程度です。似た画像かどうかは、openCVのcvMatchShapesを使おうかと考えています。 参考 http://opencv.jp/sample/matching.html 画像を呼び出そうと思うと、一つ一つ画像名から呼び出すと思うのですが、大量の画像を呼び出すことを考えると、画像名を全て書いていたのではプログラムが長くなると思います。何かいい方法はないでしょうか。 また、座標値がわかっていますので、数値でグループを特定できる方法があれば、そちらの方法を教えてもらいたいです。 こちらはプログラミング、画像処理ともに初心者です。他にいい方法があれば，それも教えてもらえるとうれしいです。よろしくお願いします。
- 締切済み
- C・C++・C#
- 長方形の重心位置を3点の座標から求める方法
XY平面内に描かれた長方形の3点の角の座標（X,Y)から長方形の重心位置(X,Y)を求める方法を知りたいです。 エクセル上に3点のX,Y座標を入力すれば重心位置が求まるようにしたいのですが・・・ 具体的な計算式を教えていただけないでしょうか？
- ベストアンサー
- 数学・算数
- どちらが効率的/美しい書き方ですか？
以下のようなコードがあるとします。 if (x > 10) { y = 100; } else { y = 0; } このコードは以下のようにも書けます。 y = 0; if (x > 10) { y = 100; } 上記の2つを処理効率、コードの美しさ（可読性）の観点から見ると、どちらが推奨される書き方でしょうか。
- 締切済み
- その他（プログラミング・開発）
- エクセルで回転する座標の出し方
エクセルで回転する座標の出し方 （例） 座標Ｘ100、Ｙ100の点から好きな角度を回したときのＸ、Ｙの座標の求め方 回転中心はＸ0、Ｙ0 回転方向は反時計回り 例で言えば Ｘ141.421、Ｙ0 が０度 Ｘ0、Ｙ141.421 が９０度 Ｘ-141.421、Ｙ0 が１８０度 Ｘ0、Ｙ-141.421 が２７０度 エクセルでの問題点は 1.角度計算がラジアンになる デグリも関数はあるけど書式がわからない 無理やり（PI()/180）などを使ってるがアークタンジェントでは書式がわからない 2.正と負の計算式・答えが負になるときの処理ができない 回転角度が２７０度とか 今電卓で打っているのは 100/100＝ATAN ----------------------最初の角度 100*100+100*100の答えのルート--------回転中心からの直線距離 最初の角度+動かしたい角度------------求めたい座標の角度 SIN求めたい座標の角度*直線距離-------Ｙ座標 答え COS求めたい座標の角度*直線距離-------Ｘ座標 答え 最初のＸ、Ｙ座標と 動かしたい角度を入れると答えが出るような 物が作りたいです よろしくお願いします エクセル2000 ＷＩＮＸＰ
- ベストアンサー
- オフィス系ソフト
- キーボードでポインタの位置を決める
C言語を用いて、プログラミングを行っています。 マウスのように、キーボードで x, y座標を入力し、 その座標にカーソルが移動するようにしたいのですが、 座標情報をどのように処理すれば、カーソルの位置が移動してくれるのかわかりません。 恐れ入りますが、どなたかご教授いただけないでしょうか。
- ベストアンサー
- C・C++・C#
- 角度を変えて、縮小した場合の中心座標の求め方
座標が左上基準になっています。 キャンバス座標 x:1000 y:1000 の位置に 四角形 400 × 200 を 配置すると x:1000 y:1000のままですが、ここから 四角形を縮小して、角度を変えると 左上の座標の位置が変わってしまいます。 四角形の左上の座標を求める式と、 できればその四角形の中心座標を求める式を教えてください。
- ベストアンサー
- 数学・算数
補足
距離10以内という意味でした。 すいません言葉足らずでした。