問題タブ [distance]

私は1 つの赤いポリゴンと50 個のランダムに配置された青いポリゴンを持っています - それらは地理的な2D 空間にあります。赤い多角形とそれに最も近い青い多角形の間の最短距離を見つけるための最速/最速のアルゴリズムは何ですか?

ポリゴンの頂点を構成するポイントを距離をテストするための値として取得するのは、必ずしも最も近いポイントではない可能性があるため、単純なケースではないことに注意してください。

したがって、最終的には、答えは、特異な赤のポリゴンに最も近い青のポリゴンを返す必要があります。

これは思ったより難しいです！

特定のアドレスの近接度でソートされた、保存されているアドレスのリストを表示する方法を実装したいと思います。

リスト内のアドレスはデータベーステーブルに保存されます。別々の部分には別々のフィールドがあるので（郵便番号、都市名などのフィールドがあります）、それは単なる巨大なものではありませんvarchar。これらはユーザーが入力したものであり、システムの性質上、必ずしも完全ではない場合があります（郵便番号が欠落しているものもあれば、市や州にすぎないものもあります）。

これはイントラネットアプリケーション用ですが、インターネットWebサービスへのアクセスなどの外部リソースの使用に問題はありません。自分でやるのが簡単でない限り、私は実際に自分自身を転がすよりもそれを好むでしょう。GoogleまたはYahoo!の場合 すでに無料のサービスを提供しているので、ぜひチェックしてみてください。キーワードは、この機能のためにこのプロジェクトに追加のコストを導入する自由がないので、無料でなければならないということです。これは、いわばボーナスの「特典」です。

多くの実店舗が「場所を探す」機能を実行しているように、私はこれを考えています。適切にソートされた単純なテーブルに表示し、距離（たとえば、マイル）を表示するのは素晴らしいことです。地図のマッシュアップを表示するのはさらにクールですが、距離を取り戻して、その後の表示と並べ替えをすべて処理するだけで、間違いなく生きることができます。

単純な距離アルゴリズムの問​​題は、データの性質です。アドレスの全部または一部が未定義である可能性があるため、緯度/経度座標のような便利なものはありません。また、私が郵便番号を要求したとしても、住所の90％はおそらく同じ5つの郵便番号を持っているでしょう。

驚くほど高速である必要はありませんが、待ち時間が原因でページに表示されるまでに7秒以上かかるものは、私たちが知っているように、平均的なユーザーが待つには長すぎる可能性があります。そのような架空のサービスが、一度に1つずつクエリを実行するのではなく、一度にアドレスのバッチを送信することをサポートしている場合、それは素晴らしいことです。それでも、アドレスのリストが合計で50を超えるとは思わないでください。

ここにあるものと同様の距離チャートを相互参照して作成し(例は道路距離の相互参照チャート)、理想的には、SQL Server 2008 (できれば Express バージョン) にデータを保存します。これらのプロパティ/能力が必要です

• すべての列には、同じ名前の対応する行があります（つまり、私の例のようにスペルミスはありません）。
• 1 つの行と列の交点で値を変更すると、ミラーの交点 (列と行) が更新されるか、ミラー データが無視される可能性があります。
• 距離値は、エンド ユーザーが編集できる必要があります。
• エンド ユーザーは、列/行のペアを追加、削除、または名前変更できる必要があります。
• エンド ユーザーは、列を並べ替えて、行を自動的に移動できる必要があります。
• 何百ものペアが存在する可能性があります。
• 検索クエリは、出発地と目的地 (行と列) を指定して距離を見つける必要があります。

距離チャートは、Excel で簡単に実装できます。これを考えると、私の方がいいのでしょうか...

• Excel をユーザー編集 UI として使用し、SQL の「もの」を新しいデータで更新しますか?
• データのクエリでパフォーマンスの問題が発生する場合でも、データ ソースとして Excel を使用していますか?
• ここで詳しく説明されている、まだ発見されていない天才のストロークを回答に使用していますか?

これはこの質問のフォローアップです。

私はこれにこだわっているようです。基本的に、標準的な度数システムの座標を参照するように、または国際日付変更線に沿って南極から北への距離を測定し、次に日付のその時点から始まる東の距離を測定するために、前後に変換できる必要があります。ライン。これを行うために (およびいくつかのより一般的な距離測定のものと同様に)、2 つの緯度/経度ポイント間の距離を決定する 1 つの方法と、緯度/経度ポイント、方位、および距離を取得して返す別の方法があります。そのコースの終わりの緯度/経度ポイント。

私が定義した2つの静的メソッドは次のとおりです。

そして、これが私がそれをテストするために使用している関数です:

「終了」値は appx である必要があります。72.0 / 31.5。しかし、代わりに約 1.25 / 0.021 を得ています。

どこかで単位を変換するのを忘れたり、何か愚かなことを見逃しているに違いないと思います...どんな助けも大歓迎です!

更新 1:

メートルを返す距離関数を (正しく) 書きましたが、コメントに間違ってキロメートルを書いてしまいました... もちろん、今日戻ってきたときは混乱しました。とにかく、これで修正されました。endOfCourse メソッドの因数分解エラーを修正しました。また、そのメソッドでもラジアンから度数に戻すのを忘れていたことに気付きました。とにかく: 正しい緯度番号 (71.99...) を取得しているように見えますが、経度番号はかなりずれています (11.5 ではなく 3.54 になります)。

更新 2: 以下で説明するように、テストでタイプミスがありました。現在はコードで修正されています。ただし、経度の数値はまだ間違っています。現在、11.5 ではなく -11.34 になっています。これらの行に何か問題があるに違いないと思います：

このThis pageから、郵便番号とその緯度/経度などのデータベースを取得しました 。次のフィールドがあります。

郵便番号、LATITUDE、LONGITUDE、CITY、STATE、COUNTY、ZIP_CLASS

データはテキスト ファイルにありましたが、MySQL テーブルに挿入しました。私の質問は、上記のフィールドを使用して、ユーザーが Web サイトに入力できる 2 つの郵便番号間の距離を計算するにはどうすればよいですか? PHP で動作するコードを歓迎します

レーシングゲームで使用するアルゴリズムを探しています。マップ/レベル/トラックはランダムに生成されるため、マップを最大限に活用する 2 つの場所 (スタートとゴール) を見つける必要があります。

• アルゴリズムは二次元空間内で動作することです
• 各ポイントから次のポイントまでは 4 方向にしか移動できません。上下左右
• ポイントはブロックされているかブロックされていないかのいずれかのみであり、ブロックされていないポイントのみを通過できます

距離の計算に関しては、適切な言葉がないため、「鳥の道」であってはなりません。A と B の間に壁 (または他の遮断領域) がある場合、A と B の間のパスは長くなります。

どこから始めればよいかわかりません。コメントは大歓迎です。提案されたソリューションは疑似コードで優先されます。

編集：そうですね。gs のコードを調べた後、もう一度試してみました。Pythonではなく、今回はC++で書きました。それでも、Dijkstras アルゴリズム、フラッドフィル、およびHosam Alys ソリューションを読んだ後でも、重要な違いを見つけることができません。私のコードはまだ動作しますが、あなたが実行しているように見えるほど速くはありません。完全なソースはパスティにあります。唯一の興味深い行 (推測) は、78 ～ 118 行の Dijkstra バリアント自体です。

しかし、ここでの主な問題は速度ではありません。誰かがアルゴリズムの違いを指摘するのに十分親切であれば、私は本当に助けていただければ幸いです.

• Hosam Alys アルゴリズムでは、すべてのノードではなく境界からスキャンする唯一の違いは?
• ダイクストラスでは、歩いた距離を追跡して上書きしますが、フラッドフィルではそうではありませんが、それだけですか?

Location.distanceToメソッドを使用して距離を計算する際に問題が発生しています。

私の距離計算が 12,637,795 メートルを示している理由を誰か教えてもらえますか?

皆さん、道路建設に携わる友人のために何かを研究しています。彼は、ポイント間の距離または面積を測定するために使用できる何らかのデバイスを必要としています。過去に GPS プログラミングを行ったことがありますが、モバイル デバイス用であり、精度にあまり感銘を受けませんでした。それはかなり前のことで、テクノロジーは改善されたと思いますが、受信機としてどのデバイスを使用すればよいかわかりません。カスタムアプリケーションを実行できるようにする必要があるため、モバイルデバイスはおそらく問題外になるため、USBポートを介して接続するものは機能するでしょうか? ラップトップや PC で動作する u-blox PCI ハードを見つけました。ここにいる誰かがそれを経験したことがありますか？おそらく他に調べる必要があるデバイスはありますか？

これについて私が得ることができる助けに感謝します。ありがとうございました。

線分を構成する 2 つの点を持つ円があります。1 つの端点から線が交差する円の端までの距離を計算するにはどうすればよいですか?

私はグーグルマップを使用している人々の場所を示すプロフィールウェブサイトに取り組んでいます。

私はグーグルマップを実装しました、そして今それはあなたが見ている人がどこに住んでいて、あなたがどこに住んでいるかを示します。

コードはここにあります：

ただし、2つの場所が離れている場合は、ズームレベルを変更して、地図に収まらないようにします。それを修正する方法がわかりません。

次のステップは、2つのポイント間の視覚的なルートと、そのルートをたどるときの距離を地図に表示させたいということです。Googleマップサイトで試してみましたが、この機能があることはわかっています。実装方法に関するドキュメントが見つかりません。

それとも、グーグルマップに行き、準備されたページを提供するハイパーリンクを作成する方が良いでしょうか？それも方法がわかりません。