問題タブ [point-in-polygon]

だから私はここに地図を持っています

Google Maps APIを使用して、特定の座標がそのポリゴン内にあるかどうかを検出するにはどうすればよいですか？それは可能ですか？

前もって感謝します。

これを実行する方法がわからないので、皆さんに聞いてみることにしました。

私は長方形のリストを持っています-実際にはatmは正方形だけですが、後で長方形に移行する必要があるかもしれないので、それらに固執してもう少し一般的にしてみましょう-2次元空間で。各長方形は2つのポイントで指定されます。長方形はオーバーラップする可能性があり、セットアップ時間についてはあまり気にしません。長方形は基本的に静的であり、セットアップに関するもの（ツリーの構築、並べ替え、追加のベクトルの事前計算など）を事前に計算する余地があるためです。何でも）。これが気になる場合は、JavaScriptで開発しています。

私の実際の質問に対して：ポイントが与えられた場合、そのポイントを含むすべての長方形のセットを取得するにはどうすればよいですか？

線形アプローチは十分に機能しません。そこで、O（n）よりも優れたパフォーマンスを発揮するものを探します。バウンディングボリューム階層などを読んでいますが、長方形が重なる可能性があるという事実を試したものは何でも（ポイントが複数の長方形内にある場合は、実際にすべてを取得したい）、常に邪魔になるようです。

何か提案はありますか？明らかな何かを見逃したことがありますか？BVHは、重複する可能性のある境界にも適用できますか？もしそうなら、どうすればそのようなおそらく重複するツリーを構築できますか？そうでない場合、他に何を使用できますか？境界線が内側にあるか、外側にあるか、または決定されていないかどうかは私には関係ありません。

誰かがリンクや、Some_Super_Cool_Structure_Perfectly_Suited_For_My_ProblemではなくBVHを使用するのがいかに愚かであるかについての怒りのような何かを思い付くことができれば、本当に感謝しています！

編集：わかりました、私はR-Treesで少し遊んでいました、そしてこれはまさに私が探していたものです。実際、私は現在、endy_cによって提案されているようにRTree実装http://stackulator.com/rtree/を使用しています。それは本当にうまく機能し、私の要件を完全に満たします。サポートしてくれてありがとう！

異なる色の領域をパスに変換することにより、ラスターグラフィックからSVGファイルに変換したマップがあります。

エッジの配列を指定して基本的なポリゴンのポイントチェックを行う方法は知っていますが、svg:path要素は複数のポリゴンとマスク（海などを考慮）を表し、d属性を解析してその情報を抽出するのはかなり手間がかかるようです。

そのチェックを簡素化できるJSライブラリはありますか？基本的に、ランダムなポイントを作成して、それらが陸（つまりポリゴンの内側）にあるのか水（つまり外側）にあるのかを確認したいと思います。

SVG要素はマウスイベントの処理を可能にするように見えるので、これはそれほど問題にはならないはずです（つまり、マウスポインターが要素の上にあるかどうかがわかれば、すでにポイントインを解決しています。ポリゴンの問題）。

編集：問題を少し複雑にしますが、svg:path要素は線ではなく曲線に基づいているように見えるので、d属性を解析してエッジの配列を作成することはオプションではないようです。

要素は属性を取ることができるのでfill、キャンバス上にSVGをレンダリングし、特定のポイントでピクセルのカラー値を見つけるというゲットーのアプローチは機能する可能性がありますが、それは本当に、本当にひどい方法のようです。

私は長い間検索してきましたが、答えはまったく見つかりませんでした。近いものはいくつかありますが、私の質問に正確に答えていると思われるものはありません! 一連の座標を取得し、それらからポリゴンを作成し、特定の場所がそのポリゴン内にあるかどうかを判断したいと思います。どんな助けでも大歓迎です！

mysql、ポリゴンの幾何学的データ型に関する典型的な質問があります。

緯度と経度の配列の形式でポリゴンデータがあります。例：

そして、緯度と経度の座標を持つポイント（頂点）があります。例：

今、この頂点 (ポイント) がポリゴンの内側にあるかどうかを調べたいと思います。どうすればphpでこれを行うことができますか?

多数のポイント (O(100 万) がポリゴンのコレクション (O(10)) の内側にあるか外側にあるかを判断する最も効率的な方法は何でしょうか?後者は必ずしも凸状ではありませんが、そうではありません穴があります. 現時点では、ポイントの位置をバウンディング ボックスと比較してポイントの数を削減し、残りのポイントでこの交差数法を使用します. しかし、おそらくより速い方法はありますか?

ポイントがポリゴン内にあるかどうかを判断することに関する投稿を見てきましたが、その答えは漠然としていたり​​、抽象的だったり、複雑すぎたりします。そこで、私が何をする必要があるかについて具体的な質問をしようと思います。

非直線 (場合によっては閉じた多角形) を表す点のセットがあります。長方形の「ビュー」領域があります。線分 (またはポリゴンの境界線) がビュー領域を通過するかどうかをできるだけ効率的に判断する必要があります。

各ポイントを単純にテストして、ビュー領域内にあるかどうかを確認することはできません。実際には領域内に点がなくても、セグメントが領域を通過する可能性があります (つまり、線が領域を横切って描かれます)。

これが私が決定したいものの例です（赤は関数が一連のポイントに対してtrueを返す必要があることを意味し、青は関数がfalseを返す必要があることを意味します。私はアーティストではないため、例では直線と長方形を使用しています）。

私が説明できるようにしたいもう 1 つの条件 (ただし、メソッド/関数は別のものである可能性があります) は、多角形の境界が四角形の領域を通過するかどうかだけでなく、領域が多角形によって完全に囲まれているかどうかを判断することです。ここでのニュアンスは、最初に説明した状況で、境界線の描画のみに関心がある場合、メソッドは false を返す必要があるということです。しかし、ここで説明した状況でポリゴン領域を塗りつぶす必要がある場合は、関数が true を返す必要があります。現在、「ドーナツ」形状のポリゴンのテストについて心配する必要はありません (神に感謝します!)。

ニュアンスを示す例を次に示します (赤い四角形には、画面上の領域を通過する単一の頂点または境界セグメントがありませんが、それでも画面上と見なす必要があります)。

「線分またはポリゴンの境界が画面を通過または横たわっていますか？」私は解決策を考え出すことができることを知っています (おそらく効率的なものではありませんが)。より冗長ですが、条件は私には明らかです。しかし、2 つ目は「画面上のポリゴン領域は?」です。問題は少し難しいです。誰かがこれを行うための良い提案をしてくれることを願っています。そして、1 つのソリューションが他のソリューションの上に簡単に実装できる場合は、まあまあです。

いつものように、助けや提案を事前にありがとう。

PS私は線の交点を決定する機能を持っていますが、画面上の領域は常にプレーン[0、0、幅、高さ]であるため、各セグメントを画面上の領域の両側と比較するためにそれを使用するのはやり過ぎのようです矩形。何か近道はないのでしょうか？

この形式で指定された長方形内に点があるかどうかを確認する最も速い方法は何ですか。長方形の反対側
の中心である2つの点と、それらの辺の高さである数値があります。これが明確であることを願っています。 長方形は（おそらく）軸と整列していません。このデータを前提として、四隅の計算、回転など、より高速なアルゴリズムがあるのではないかと思います。

私が考えたが、実装方法がわからない（数学に問題がある）アイデアは、点から2つの中心の間をトレースする線までの距離を見つけることでした。それが、辺の長さの半分未満の場合は、長方形と線上にある場合、それは長方形の中にあります。これをもっとよく説明する方法がわかりません。

たぶん、写真は説明に役立つでしょう：
A、B、C、およびサイドA/Bの長さが示されています。基本的に、CDが辺Aの半分未満でDがABにある場合、点は長方形の中にあると思いました。しかし、どうすればこれを行うことができますか？
別の考え： Dを見つけてAB上にあるかどうかを確認する代わりに、角度ABCとBACが鋭角であるかどうかを確認しますが、これを行う方法はまだわかりません。

ポイントがgwt-g2d形状内にあるかどうかを検出しようとしています。誰かがこれがどのように可能か知っていますか？

ポイントがコンテキスト内の任意のパス内にあるかどうかを判断できます。

2つの長方形（AとB）のコンテキストがあり、マウスがどの長方形にあるかを確認したい場合、どうすればよいですか？

長方形は単なる例であり、ポイントが複雑な形状であるかどうかも確認したいと思います。

私はjavaScript/jQueryで書かれたゲームに取り組んでいます。私のコードの一部は、タイルグリッド上にランダムなポリゴン（島）を描画します。ポイントがポリゴンの内側にあるかどうかを確認する必要があります。

Stack Overflowのいくつかの 場所で見つけたポイントインポリゴン交差スクリプトを使用しています（元のスクリプトはこちら）。これはFirefoxで正常に機能します。Chromeでは、スクリプトがポリゴン内にないと言っているポリゴン内のポイントがあります。

Firefoxの場合：

Chromeの場合（ランダムに生成されるため、島は異なります）：

ここのソース、特にpointPolygonIntersect関数を見てください： ポリゴンヒットテストのポイント

なぜこれが起こっているのか誰かが理解できますか？元のスクリプトはCであり、JavaScriptバージョンを使用しています-これが問題の原因である可能性がありますか？