地理空間ルーティング

私はロジスティクスプログラマーです。私は、ルートがいくつかの地理空間的ポイント（緯度、経度）で構成される「オフルート」であるかどうかを確認するよう求められました。地理空間ルーティング

ポイントがルートに近いかどうかを判断するための最良のアルゴリズムとは何ですか？私はC＃とSQL Serverを使用しますが、使用するアルゴリズムが分かっていれば、実際にはそれほど問題にはなりません。

私は

が最も近い2つのポイントを見つけて、三角形の面積は、特定の限界を超えているか否かを決定すると考えられてきました。
すべての点のペアについてベクトルを使用して、それらのどれかがGPSポイントによって定義されたベクトルと「類似」であるかどうかをチェックして、ポイントIがルート内で「次」であると判断します。

私は数学の学位は持っていませんが、正しい用語と検索エンジンがあれば何でも処理できます。

私は少なくとも4000回の計算を1時間に1回行う必要があります。そのため、マッピングソリューションを使用することは、ボリュームのためにおそらく受け入れられません。

2012-01-18 Doug Heeren

だろうを見てみましょうするためのいくつかの良い議論。三角測量の解決法は、非常に離れた2つの地点が、地点がわずかに外れていても大きな表面積を持つ三角形を生成するため、機能しません。私はより良い解決策を持っているかどうかはわかりません私に何か考えてくれてありがとう。 –

どのバージョンのSQL Serverを使用していますか？ lat/long以外のバスの場所に関する属性はありますか？バスID、ルートIDなどは正しい道路/ルートに結びつけることができますか？ – RyanDalton

@ RyanDalton 2005残念ながら。私が理解しているように、2012は空間データに関するいくつかの素晴らしい機能を持っていました。私はmongoやその他のデータベースを使っているわけではありませんが、リアルタイム情報を持つ別のデータベースを設定して維持するためにもう少し作業が必要になります。 –

Googleの「Along-track distance」について、あなたは一般的に航空機で使用される式を見つける必要があります。あるいは、cross-track distanceもあなたが望むものにすることができます。

出典

2012-01-18 21:57:17

ありがとう、これは私が探していた答えに見えます。 –

あなたは、あなたのクエリ点を取り、最も近い点と最も近い線分を見つけ、2-Dにおける線分のシーケンスとして、既存のルートを取ることができますか？その最も近いポイント/線分までの距離は、あなたが気にする距離です。

比較的低い緯度（60度以下）に固執している場合、緯度と経度をメルカトル図法のように単純にフラットであるかのように扱うことができます。

もしそうでなければ、座標系をいくつかのルートポイントを通って走っている大きな円に対して相対的に変換することができます。

何百万というルートポイントを扱っているのでなければ、CPU時間に問題はないはずです。各ラインセグメントの

出典

2012-01-18 22:08:43

それは私が考えてきた式の1つですが、経路の形によっては動作しない場合があります。それらのほとんどは直線の近くにどこにもなく、それらのうちのいくつかは彼ら自身の上に二重に戻っています。時間がかかればさらに複雑になりますが、別の質問のためにそれを保存しました。 –

方法次...

反復に関する全ての線分

lineSegSlope =計算スロープを通じて

現在の線と交差疑問点からふり線を引きますセグメント。これは、lineSegSlopeを反転して-1を掛けて新しい勾配を取得し、ターゲットポイントX、Y、および新しい勾配をy-y1 = b *（x-x1）に代入することによって行われます。あなたのXは、あなたのYはY1になり、X1に入り、そしてあなたのnewSlopeは、線分の方程式を作るB.

に入ります。

2つの線を重ねて描画する場合、各角が90度のところにXを描く必要があります。

二行

の交点を計算するには、交点とあなたの新しい点間の距離を計算します。許容値よりも大きい場合は、新しいポイントが大きすぎます。

これは混乱のように見えますが、うまくいけばうまくいくはずです。

出典

2012-01-18 22:26:17

ルート上のポイントと問題のポイントの角度は、私がそれを推論したときにこれを捨てるものです。線分が点から遠く離れているが、ルートの2つの点の角度が、線が延長された点に非常に近くなるようなものである場合、誤った答えが生じる。私は少しこれを理解するために苦労しているので、私はこれに間違った応答を持つかもしれません。 –

私はあなたが言っていることを見て、良いキャッチ。私はその場合、線分の実際の端が最も近い点であると思います。次に、ターゲットポイントから線分の終点までの距離を計算することができます。ここにはちょっとした問題があります。 –

新しいGPSポイントをルート沿いのさまざまな場所に挿入するのが簡単な方法です。まず最初の点P0の前に挿入し、次に最初の点P0とP1の間に挿入します。最後の点として挿入するまで続きます。それをある場所に挿入しようとするたびに、回路の合計距離を計算し、最短距離を保存してください。これは、脚の距離を事前に計算し、その合計を格納することによって高速化できます。新しいポイントを挿入している脚の脚の距離を減算し、ポイントP（n）からGPSポイントまでの新しい距離をP（n + 1）に加算して距離を確認します。その最短距離が許容範囲内にある場合は、それを受け入れることができます。

これはおそらく「最良の」アルゴリズムではありませんが、時間と空間の両方の複雑さのためにルート内のポイント数のO（n）です。あなたのルートには膨大な数のポイントがある場合を除いて、各チェックは1秒よりかなり短くなるはずです。したがって、これはあなたの時間要件の範囲内にあるはずです。

また、ルート上の連続するポイント間の距離を計算するときは、必ずhaversine distance equationsを使用してください。

出典

2012-01-18 22:27:20 andand

私にとって最善のことは、状況の非常に大きな部分の下で、迅速かつ正確です。この状況での許容レベルは、ルート内のポイント間の距離が大きい場合に大きくなる必要がありますか？ –

私はそうマッピングソリューションを使用して時間が原因ボリュームにおそらく受け入れられない、少なくとも4000の計算を行う必要があります。

実際、これはマッピングソリューションが有益な完全な例です。あなたの伝統的な「地図を見て距離を決定する」ではなく、「データベースがあなたのGPSポイントに最も近いルートを決定できるようにする」

別のデータベースを使用することに反対していると言えば、：

Spatial Database Engine機能、またはかなり多くの空間解析機能を持つオープンソースPostGIS（空間）拡張子を持つ
のPostgreSQLを持つSQL Server 2008の、そのMS SQL 2008

PostGIS ST_Distance関数またはMS SQL Server 2008 STDistance関数を見てください。これは、SQL2005とSQL2008の利点を説明する良いblog entryです。

gis.stackexchangeに投稿を読む（または詳細なマッピングを依頼する）ことも考えられます。そのグループ全体が空間分析に専念しています。あなたが何を求めてきましたが、興味深い質問です

出典

2012-01-19 22:26:12 RyanDalton

ありがとうございます。私は友人にも私にgis.stackexchangeを提案してもらいました。マッピングソリューションを使用することでスピードが懸念されます。これらの時間は最低でも4000時間です。しかし、あなたが正しいのはおそらく最も正確な解決策です。 –

答えて

関連する問題