7

私は過去数か月にわたってPHP、PDO、SQLを習得し、PHP / SQLのベストプラクティスに従って、ユーザー登録/電子メールアクティベーション/およびログインログアウト機能を備えた基本的な動的Webサイトを構築しました。今、私は次のタスクで立ち往生しています...

正方形/ポリゴン（300万以上）の巨大なデータセットを作成しました。それぞれのサイズは緯度と経度の1分で、単一の座標セット（左上隅）を持つPHP配列に格納されています。正方形のような形状を外挿するには、各方向に0.016度（約1分）を追加して、他の3つの座標を生成します。

ここで、上記の配列の各ポリゴンが米国の土地の少なくとも一部にあることを確認する必要があります。つまり、完成したデータセットのグラフィック出力を生成して、サンフランシスコの海岸線を確認する場合です。 、彼らはこのようなものを見るでしょう。

これは、ポイントインポリゴンの問題に似ていますが、ポイントではなく別のポリゴンを処理し、他のポリゴンは国境であり、交差点だけを見ているわけではありません。次のことを確認したい：

  • ポリゴン/正方形はポリゴンと交差します。（海岸線/境界線を考えてください）。
  • ポリゴン/正方形はポリゴンの内側にあります。（米国本土を考えてください）。
  • ポリゴン/正方形には、ポリゴンの一部が含まれています。（小さな島を考えてください）。

これは私の大雑把に描かれた画像で示されています：

これは簡単ではありません！

これらの3つの条件のいずれかに一致する場合は、正方形を維持したいと思います。とにかく大きなポリゴンと相互作用しない場合（つまり、水上にある場合）、それを破棄します。

大きなポリゴンは米国のシェープファイル、または座標を取り除いて非常に複雑なポリゴンを作成できるKMLファイルになると思っていました。

次に、これらの一致する正方形と正方形IDをcsvファイルに渡して、各正方形の座標のセットを含むMySQLテーブルに統合することを考えました（実際、テーブルを処理するためのベストプラクティスすらわかりません） MySQLではそのサイズですが、必要に応じて説明します）。最終的な目標は、Javascriptを介してGoogle Maps APIを使用して地図を作成し、コーディングしているWebサイトの地図上にこれらの正方形を表示することです（明らかに、データベースに負担をかけないように、視点内に正方形のみを表示します） ）。私もそのような情報を最初にPHPを介して渡さなければならないと確信しています。しかし、実際にデータセットを作成するタスクと比較すると、これらはすべて比較的簡単に思えます。

これは明らかに手作業ではできないことなので、自動化する必要があります。私はPythonを少し知っているので、それは役に立ちますか？どこから始めるべきかについての他のヒントはありますか？私のためにコードのいくつかを書いてくれる人はいますか？

4

2 に答える 2

3

この他の質問は、あなたがやろうとしていることのかなりの部分に答えると思います

2つの凸多角形が交差しているかどうかを確認するにはどうすればよいですか？

もう1つの部分は、データベースを使用している場合、両方のセット（マップポリゴンのセットと生成した他のポリゴンのセット）からビューポイントの近くのすべてのポリゴンをロードしてから、この小さい方で上記のアルゴリズムを実行することです。ポリゴンのセット。マップにオーバーレイする必要があるセット内のすべてのポリゴンのリストを生成できます。

于 2013-03-01T00:21:48.420 に答える
3

これは、効率的で、実装が可能な限り簡単なソリューションです。私は単純とは言いませんが、可能な限り単純であることに注意してください。結局のところ、これは難しい問題です。

1）ShapefilesまたはKFLを使用してUSポリゴンデータを取得します。これにより、頂点のリストによってそれぞれ定義された一連のポリゴンシェイプ（ランドマス）が生成されます。

2）米国用の軸整列境界ボックス（AABB）長方形のセットを作成します。1つはアラスカと各アラスカ島、1つはハワイの島、1つは米国本土、もう1つは米国本土の沖合の小さな島です。米国本土（例：アラスカのボールドヘッド島、カリフォルニア沖のカタリナ）。各境界ボックスは、形状の最小および最大の緯度と経度である角を持つ長方形として定義されます。私の推測では、これらは数百個あると思います。たとえば、ハワイの大きな島の場合、緯度は北緯18度55分から北緯28度27分まで、経度は西経154度48分から西経178度22分までです。グローバルな緯度/経度のペアのほとんどは、これらの数百の境界ボックスのいずれにも含まれていないため、このステップで破棄されます。たとえば、10°20'W、30°40'のバウンディングボックス 10°20'Wは154°48'W未満であるため、N（アフリカのラスパルマス近くの大西洋のスポット）はハワイと重なりません。このビットはPythonで簡単にコーディングできます。

3）緯度/経度のペアが数百のAABB長方形のいずれかと重なっている場合は、AABB長方形内の単一のポリゴンに対してテストする必要があります。これを行うには、ミンコフスキー差（MD）を使用することを強くお勧めします。最初にこのWebサイトを徹底的に確認してください。

http://www.wildbunny.co.uk/blog/2011/04/20/collision-detection-for-dummies/

特に、ページの途中にある「ポリ対ポリ」のデモを見て、少し遊んでみてください。そうすると、2つの形状のMDを取得するときに、そのMDに原点が含まれている場合、2つの形状が重なっていることがわかります。したがって、次に行う必要があるのは、2つのポリゴンのミンコフスキー差を取得することです。これにより、新しいポリゴン（デモでは、B-A）が生成され、そのポリゴンに原点が含まれているかどうかを確認します。

4）MDを実装するためのアルゴリズムに関する多くの論文がオンラインにありますが、論文を読んでそれをコードに変換する能力があるかどうかはわかりません。2つのポリゴン（テストしている緯度/経度の長方形、および緯度/経度の長方形と重なったバウンディングボックスに含まれるポリゴン）のMDを取得するのは難しいベクトル計算であるため、あなたはあなたの経験を教えてくれましたレベルはまだ高くありません。すでにMDを実装しているライブラリを使用するか、さらに良いことに、衝突検出を実装しているライブラリを使用することをお勧めします。

例えば：

http://physics2d.com/content/gjk-algorithm

ここでは、Pythonに移植できる関連する擬似コードを確認できます。

if aO cross ac > 0 //if O is to the right of ac
    if aO dot ac > 0 //if O is ahead of the point a on the line ac
        simplex = [a, c]
        d =-((ac.unit() dot aO) * ac + a)
    else // O is behind a on the line ac
        simplex = [a]
        d = aO
else if ab cross aO > 0 //if O is to the left of ab
    if ab dot aO > 0 //if O is ahead of the point a on the line ab
        simplex = [a, b]
        d =-((ab.unit() dot aO) * ab + a)
    else // O is behind a on the line ab
        simplex = [a]
        d = aO
else // O if both to the right of ac and to the left of ab
    return true //we intersect!

これを自分で移植できない場合は、ここに含めた2つのリンクの作成者のいずれかに連絡することができます。どちらもFlashにMDアルゴリズムを実装しており、ソースコードのライセンスを取得できます。

5）最後に、衝突検出を処理したと仮定すると、緯度と経度のペアが米国の一部であるかどうかに関するブール値をデータベースに格納するだけで済みます。それが済んだら、Googleマップで好きなようにできることは間違いありません。

したがって、要約すると、ここでの唯一の難しい部分は、1）衝突検出GJKアルゴリズムを実装するか、または2）最初に緯度/経度のペアとそれに含まれる土地ポリゴンとの間のミンコフスキー差を計算するアルゴリズムを作成することです。 AABBを作成し、次にそのMDポリゴンに原点が含まれているかどうかを確認します。このアプローチを使用する場合、レイキャスティング（一般的なポリゴンの点ソリューション）は、2番目の部分でトリックを実行します。

これがあなたに正しい方向へのスタートを与えることを願っています！

于 2013-03-01T01:23:18.587 に答える