問題タブ [geospatial]

緯度/経度のペアで表されるポイントの大規模なセットを使用しています (ポイントは必ずしも一意であるとは限りません。セット内に同じ場所にある複数のポイントが存在する可能性があります)。ポイントはデータベースに保存されます。

私がしなければならないことは、検索を効率的に実行して、任意の点から指定された半径 (たとえば 25 マイル) 内にある点の数を取得する方法を見つけることです。カウントは 100% 正確である必要はありません。さらに重要なことは、それが高速で、正しいカウントにかなり近くなければならないということです。SQL でこれを行うには、WHERE 句で三角関数を使用したクエリを使用して、基準点までの距離でポイントをフィルタリングします。残念ながら、このクエリは非常に高価であり、場所が非常に分散しているため、キャッシュはあまり役に立ちません。

私は最終的に、この種の操作を効率的に処理できるある種のインメモリ構造を構築することを目指しています-速度と引き換えに、データの正確さとライブネスの一部をトレードオフします（おそらく1日に1回だけ再構築します） . 私は kd ツリーについていくつかの調査を行ってきましたが、これが緯度/経度データ (2 次元平面の x、y データとは対照的に) にどの程度適用できるかについてはまだ明確ではありません。

誰かが私が検討すべきアイデアや解決策を持っている場合は、本当に感謝します-事前に感謝します.

Geometry タイプ フィールド (または Geography) を持つテーブルがある場合は、Reduce()関数を呼び出して形状の頂点数を減らすことができます。非常にうまく機能します。ただし、いくつかのポリゴンが隣接している (境界の一部を共有している) 場合、縮小されたポリゴンは必ずしも隣接しているとは限りません。

例

SQL バッチ:

これにより、2 セットのポリゴンが返されます。最初の縮小されていないセット:

次に、削減されたセット：

これらの形状ははるかに単純で、大まかな形状は正しいですが、私が望むのは境界部分を共有することです。したがって、ある意味で、それらをまとめて削減する必要があります。

最初に（エッジからエッジまで）ポリラインに分割し、次にラインを削減してから、再度ポリゴンに再構築する必要があると思います。ただし、T-SQLでこれを行う方法がわかりません。

何か案は？

編集: alphadaogg の回答を受け入れました。現在の両方の回答は、私にとって完全に説得力のあるものではありませんでしたが、alphadogg は確かに最大限の努力をしてくれました。それで、賞金は彼に行きます。

満足のいく方法が見つかったら、後で自己回答でフォローアップします。

フォローアップ: SqlServer Geo チームのプログラム マネージャーである Isaac Kunen に電子メールを送りました。彼の有益な応答は以下のとおりです。

あなたの問題はまったく珍しいものではありませんが、私たちが直接サポートするものではありません: これは、フィギュアのトポロジーの知識を必要とする操作であり、このようなものは組み込まれていません. 基本的に、あなたは望んでいません近隣ごとに個別のポリゴンを保存します。むしろ、境界の一部を表す曲線を保存し、これらの境界を複数のポリゴンに再利用する必要があります。ジェネラライズすると、共有境界がジェネラライズされ、依存するすべてのポリゴンが影響を受けます。

これを自分で作成することもできます---スレッドのポスターがヒントを引用しているように---しかし、そうするのは本当の努力かもしれません.

使用しているサードパーティ ソフトウェアはわかりませんが、これは別のオプションです。本格的な GIS が必要ない場合は、Safe Software ( http://www.safe.com ) の FME などのパッケージを使用できます。FME は汎用トポロジーを実行しませんが、探していることを実行するのに十分な機能を備えていると思います。http://www.safe.com/products/desktop/under-the-hood.php#3bを参照して ください。

これが役立つことを願っています。

乾杯、

-アイザック

私はインターネットを見回していましたが、この特定の問題に最適なアルゴリズムを見つけることができませんでした:

この画像で示されているように、顧客は各ポイントとともに一連のポイントと重量データを持っています。

加重ポイント http://chakrit.net/files/stackoverflow/so_heightmap_points.png

そのうち、これらのポイントとその重み値から「高さマップ」または一種の地形データを生成できる GIS プログラムがありますが、1,000 ポイント近くのデータがあり、これらは時間の経過とともに変化するため、これらの高さマップを自動生成する独自のツールを作成します。

これまでのところ、最も近いデータ ポイントまでの距離から各ピクセルの重みを計算し、Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)重みと距離係数をデータ ポイントの色に適用して、その特定のピクセルのグラデーション カラーを生成しようとしました。

ハイトマップの結果 http://chakrit.net/files/stackoverflow/so_heightmap_result.png

データ ポイントの特定の構成にはまだ問題があり、多くのデータ ポイントがある場合、アルゴリズムによって多角形の画像が生成されることがあります。理想的な結果は、多角形ではなく、省略記号のように見えるはずです。

これは、私が望む結果を示す勾配上昇に関するウィキペディアの記事の画像の例です。

山 http://chakrit.net/files/stackoverflow/so_gradient_descent.png

勾配上昇アルゴリズムには興味がありません。私が興味を持っていること; 重み付きのデータポイントが提供された場合、最初にその画像の元の関数を計算するアルゴリズムです。

トポロジカル数学の授業は受けていませんが、微積分はできます。何かが足りないのではないかと思います。Google の検索ボックスに何を入力すればよいかわかりません。

いくつかの指針が必要です。

ありがとう！

地理空間関数に適したライブラリは何ですか? 私は次のようなことを意味します

• 地球上の 2 点間の距離
• 特定の点から指定された半径の円の座標
• 等

さまざまなデータベースが地理位置情報を表すさまざまな方法へのインターフェースがある場合のボーナス。

私は地理初心者なので (この質問で明らかにならなかった場合に備えて)、他の地理位置情報/地理空間リソースへのポインタを歓迎します。

C++ と Python を優先しますが、すべてのポインターを歓迎します。

ポリゴン自体の内部に存在する Oracle Spatial でポリゴンの重心を見つける必要があります。sdo_geom.sdo_centroid メソッドは使用できません。これは、形状が馬蹄形に似ている場合に形状の外側のポイントを返すためです。

sdo_geom.sdo_pointonsurface メソッドを見つけましたが、ポリゴンのちょうど端にあるポイントを返します。これは数学的には機能しますが、すべてのポリゴンが他のポリゴンと境界を共有し、データにわずかな重複がある場合があるため、この環境では安全ではありません。このオーバーラップには、計算されたポイントを含めることはできません。

カスタムコードを書かずにこの点を見つける別の方法はありますか? このためのカスタム コードを作成することに反対しているわけではありませんが、事前に作成されたものが既に存在する場合はそれを使用したいと考えています。

ありがとう！

オープン レイヤーを使用して、ベース マップにオーバーレイするヒート マップ スタイルのタイルをいくつか作成したいと考えています。基本的に、いくつかのバウンディング ボックスをグリッドに分割し、そのグリッドの正方形内にサンプルのポイントがいくつあるかに基づいて、異なる色を使用してグリッドの各正方形を表示したいと考えています。

関連するテクノロジは、C#、OpenLayers、SQL Server 2008、および GeoServer です。

私の質問は基本的に一般的なアプローチの 1 つです。ノミの先端をどこに置くべきかよくわかりません。

私の最終的な目標は、任意のバウンディング ボックスを取得し、そのバウンディング ボックス内に収まる x マイルごとのグリッドを計算し、個々のポイントのコレクションを反復処理して、それらを 1 つのグリッド スクエアまたは別のグリッド スクエアに割り当てることができるようにすることです。グリッド スクエアごとのポイント密度を計算し、密度に応じてグリッドに色を付けてから、Open Layers を使用して CloudMade ベース マップに重ねることができます。

全体またはその一部について、どんな助けでも大歓迎です。

緯度と経度の2つのWGS84座標があります。これらのポイントはかなり接近しており、たとえば1メートルしか離れていません。

これらの点の間の線の方位角、つまり北への角度を計算する簡単な方法はありますか？

素朴なアプローチは、デカルト座標系を想定し（これらの点が非常に接近しているため）、次のように使用することです。

sin（a）= abs（L2-L1）/ sqrt（sqr（L2-L1）+ sqr（B2-B1））

a =方位角L1、L2 =経度B1、B2=緯度

座標が赤道から離れるにつれて誤差は大きくなります。これは、2つの経度間の距離が、2つの緯度間の距離（一定のまま）よりもますます小さくなるためです。

非常に複雑な数式をいくつか見つけましたが、それらは非常に接近しているポイントには行き過ぎであり、非常に高い精度は必要ないためです（小数点以下2桁で十分ですが、1つでも問題ありません。 GPSが返すもののように、とにかく精度を低下させる他の要因です）。

たぶん、緯度に応じておおよその縦方向の補正係数を決定し、次のようなものを使用することができます。

sin（a）= abs（L2 * f-L1 * f）/ sqrt（sqr（L2 * f-L1 * f）+ sqr（B2-B1））

ここで、fは補正係数です。

ヒントはありますか？

（これにはライブラリを使用したくありません。特に、ランタイムライセンスが必要なライブラリは使用しません。MPLされたDelphiソースがあれば素晴らしいでしょう。）

私のチームは、さまざまなデータベース プラットフォームが提供する地理空間機能を調査しています。

すべての実装はデータベース固有のものですか?それとも ANSI SQL 標準、または提供されている、または将来提供される予定の同様のタイプの標準がありますか?

実装されたコードを可能な限りデータベースにとらわれないようにしたいのでお願いします (私たちのプロジェクトは ANSI SQL 標準で書かれています)。

将来、この機能を標準化する計画はありますか?

私の会社は、さまざまなデータベース プロバイダーと、地理空間クエリを実装して多数のレコードの緯度/経度から距離を取得する方法を検討しています。

潜在的なデータベース プラットフォームとして PostgreSQL を調査します。

• PostGRE は地理空間クエリを実装していると聞きました。これは正しいです？
• 実装に関する情報を提供する適切なリファレンスはありますか?