問題タブ [point-in-polygon]

プログラミングコンテストで多角形の点を解くのに最適なアルゴリズムは何ですか?

ポイントがポリゴン内にあるかどうかを確認したいと思います。もちろん、私はグーグルで検索して、この質問が以前に回答されているかどうかを調べ、次のアルゴリズムを見つけました: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html ポリゴンが部分的に開いていない限り、これは正常に機能します。 . 例えば：

AE は正常に検出されますが、B ポリゴンの開いた部分も閉じていると見なされます。このサンプル コードを実行すると、私の言いたいことがわかるでしょう。

x2/y2 ポリゴンは、部分的に開いたブロックに接続された閉じたブロックで構成されます。pnpoly 関数は、開いたブロックの "内" の点を多角形内にあると見なします。

私の質問は次のとおりです。どうすればこの問題を解決できますか? それとも私は何かを見落としていますか？

前もって感謝します。

ジオフェンスを作成し、デバイスがフェンスに出入りしているかどうかを確認できるアルゴリズムを探しています。多角形アルゴリズム (レイ キャスティングと巻き数) の点を見てきましたが、円や不規則な形状にも適用できるアルゴリズムはありますか? 重要な制約は時間効率です。

ありがとうございました。

CPU時間の25％をむさぼり食う方法があります。このメソッドを 1 秒あたり約 27,000 回呼び出します。(ええ、頻繁に更新されているため、多くの呼び出しがあります)。2 つのポリゴンが重なっているかどうかを検出するより高速な方法を誰かが知っているかどうか疑問に思っています。基本的に、画面上で動いているオブジェクトと画面上で静止しているオブジェクトをチェックする必要があります。私は PathGeometry を使用しており、以下の 2 つの呼び出しは、プログラムが使用する CPU 時間の 25% を使用しています。私が渡している PointCollection オブジェクトには、ポリゴンの 4 つのコーナーを表す 4 つのポイントが含まれています。それらは長方形の領域を作成しない場合がありますが、すべての点が接続されています。形は台形になると思います。

これらのメソッドは短く、実装が非常に簡単でしたが、以下のコードよりも速く実行できる場合は、より複雑なソリューションを選択したいと思うかもしれません. 何か案は？

私は問題を抱えています。皆さんが私を解決するのを手伝ってくれることを願っています.

DbGeometry ポイント (または DbGeography、両方を使用できます) を取得しました。これが DbGeometry ポリゴン (または DbGeography) 内にあるかどうかを確認したいと思います。

私は現時点でこれをやっています：

したがって、ゾーン (db の EF エンティティ) を反復処理し、このポイントがこの境界内にあるかどうかを確認します。

問題は結果が返されないことですが、境界とその境界内にあるポイントを手動で作成したため、そのポイントがその境界内にあることがわかります。

私がやっていることが間違っているかどうか、これを行う別の方法があるかどうか、誰か教えてもらえますか?

とても感謝しています。

マヌエル

ポリゴン内にマーカーを配置する方法 (このポリゴンは既にマップ上にあります)? 私の考えは、たとえば円を多角形に内接する方法を見つけて、この円の中心を見つけることです (問題ではありません) が、円を内接する方法を見つけることができません。

LatLngBounds のメソッド getCenter() は期待どおりに機能しません。これは、多角形の数学中心が視覚的にこの多角形の外にある可能性があるためです。

多角形のMySQL クエリでポイントを作成する必要があります。

私はすでに次の 2 つの優れたソリューションを見つけました。

http://forums.mysql.com/read.php?23,286574,286574

レイキャスティングアルゴリズムのMySQL実装?

ただし、これらの関数は、1 つのポイントがポリゴン内にあるかどうかしか確認できません。PiP 部分がクエリの一部のみである必要があるクエリがあり、ポリゴン内の x ポイントをチェックします。

このようなもの：

$points = list/array/whatever of points in language of favour

アップデート

次のようなMBR関数で試しました：

G2 は G1 の中にあるべきではありませんが、MBRはそうであると言っています。

私はこれを行うための最善の方法を見つけようとしています。地図がPolygon描かれています。Google MapsAPIV2がポリゴン上でタッチ検出機能を備えているようには見えないためです。タッチポイントがポリゴンの内側にあるかどうかを検出できるかどうか疑問に思いました。もしそうなら、私の主な目標は地図上に状態の輪郭を描くことであり、ユーザーがその状態をタップすると、カスタムビュー内に詳細が表示されます。今MapOnClickのところ、地図のをキャプチャすることはできますが、ユーザーが内部をタップすると、のセットがPolygon必要になります。私は初心者なので、十分に明確でない場合はお詫び申し上げます。polygon.getID()Toast

わかりました、これは私がこれまでに半作業をしているものです

}

私が抱えている問題は、タッチが別のポリゴンに到達するまで、各ポリゴンの左側に当てはまるということです。この問題を引き起こすアルゴリズムの何が問題になっていますか？どんな助けでもいただければ幸いです。

複雑なポリゴンと単純なポリゴンの扱い、ポイントがポリゴンの内側/外側かどうかの判断などについて学び始めています（例： http： //geomalgorithms.com/a09-_intersect-3.htmlおよび関連ページ）。Bentley-Ottmannアルゴリズム、回転数、エッジ交差などの実装を提供するRパッケージを見つけたいと思っていました。

または、CGALライブラリまたは同様のツールセットへのRインターフェイスはありますか？Rcppはこれを行うための最良の（または唯一の）方法ですか？

私は過去数か月にわたって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を少し知っているので、それは役に立ちますか？どこから始めるべきかについての他のヒントはありますか？私のためにコードのいくつかを書いてくれる人はいますか？