問題タブ [point-in-polygon]

n辺の正多角形を作成するためのx、yポイントを計算する簡単なプログラムを作成する方法を見つけようとしています。ポリゴンを描画する既存の関数を使用しないコード例を教えてもらえますか? プロセスを理解したいのですが、これは次のようなものだと思います。

1. 半径と中心点から開始する角度をピックします
2. どういうわけか、中心からその距離で x、y 位置を計算します (どのように?)
3. 360 を辺の数で割り、その距離を移動して、最初の x、y ポイントから次の線を引きます
4. angle=360 をその数値で割るまで続けます。

私の仮定が正しいと仮定すると、主なことは、x、y ポイントを計算する方法を理解することです。

ビジュアル ベーシック (または古いスタイルの Microsoft/Atari/Commodore BASIC) または英語で人間が読める一連の手順での回答を優先します。数式で答えなければならない場合は、私が読めるようにコンピューター言語で答えてください。C や C++ でも理解できますが、数学表記の読み方がわかりません。私が使用している言語は、線画以外のグラフィックス プリミティブがほとんどない Visual Basic ライクな言語です。

特定の LatLng が Google マップのサークル内にあるかどうかを確認する必要があります (これらのいずれか: http://code.google.com/apis/maps/documentation/javascript/overlays.html#Circles )。どうすればこれを回避できますか？円を作成するための私のマークアップは次のとおりです。

半径だけを使用できますか？

グーグルマップ上の緯度/経度の値とポリゴンのポイントインポリゴンの迅速でかなり正確な方法を理解する必要があります。いくつかの調査の後-mysqlの幾何学的拡張に関するいくつかの投稿に出くわし、それも実装しました-

ただし、これは、多数のポイントで構成されるポリゴンでは機能しませんでした:(

さらに調査した後、レイキャスティングアルゴリズムと呼ばれる標準アルゴリズムに出くわしましたが、MySQLでそのクエリを開発する前に、誰かがすでにそれを経験しているか、実装方法を示す便利なリンクに出くわした場合は、チャンスをつかみたいと思いましたMySQL/SQLサーバーのアルゴリズム。

だから、それを短くする-質問は：

誰かがレイキャスティングアルゴリズムのMySQL/SQLサーバー実装を提供できますか？

追加の詳細：

• ポリゴンは、凹面、凸面、または複雑のいずれかです。
• 100％以上の精度で迅速な実行を目標としています。

ダーツ スコアリング プログラムを作成して (ダーツ ルームで自分自身を使用するため)、ユーザーがダーツ ボードの画像のさまざまな領域をクリックして、投げられたダーツを登録できるようにしたいと考えています。

このプログラムはサイズ変更可能であるため、ユーザーがプログラム ウィンドウのサイズを変更すると、ダーツ ボードの画像のサイズが変更されます。

ポリゴン (pointF-arrays) のリストを使用して各領域をマップし、計算を実行してマウス クリックがポリゴン領域内にあるかどうかを確認しますが、ピクチャ ボックスのサイズが変更されたときにこれらのポリゴンを正しくスケーリングするにはどうすればよいですか? 私のポリゴンは、特定のサイズで画像のダーツボード領域をマッピングするようにハードコーディングされています。

編集: Olivier Jacot-Descombes からの非常に素晴らしい回答の後、マウスポインターの x 値と y 値を元の画像サイズに一致する値に変換する GetScaledPoint 関数を使用してスケーリングを修正し、元のポリゴンのヒットを簡単に確認できるようにしました。 . 誰かが興味を持っている場合は、以下のコードのソリューションを編集しました。この例では、Picture1 は、sizemode=stretch および docking=fill に設定されたダーツ ボード (このようなhttp://quizmasters.biz/Pub%20Genius/Darts/Gfx/Dartboard_05.jpg ) の写真です。

私のメインビューには、サブビューとして実装されたいくつかの（おそらく多くの）多角形のアクティブエリアがあります。ユーザーがビューに触れたときに、彼女がそれらのアクティブな領域の1つに当たったかどうかを識別したいと思います。

すべての[可能性のある*]アクティブな領域のリストを反復処理し、ポイントがその中にあるかどうかをそれぞれに尋ねる、単純なアルゴリズムよりも優れたものはありますか？

hitTest:withEvent:ドキュメントに「このメソッドは、非表示になっている、ユーザーインタラクションを無効にしている、またはアルファレベルが0.01未満のビューオブジェクトを無視する」と記載されているため、（オーバーライドせずに）使用できません。そして、私のサブビューは確かに隠されています（ほとんどの場合）。

私はこれらのオプションを見ることができます：

• 私自身の本格的な四分木実装を実装します。これは時期尚早の最適化の悪臭であり、Appleのヒットテストの実装はすでに最適化されていると私は期待しているので、これは車輪の再発明です

• [possible *]領域を制限するには、最大および最小のx座標とy座標をそれぞれ維持し、最初にその長方形でヒットテストを行います。実際、私のサブビューframe はそれらの長方形です。私はAppleのヒットテストがそれらを使うことを期待している。

• hitTest:withEvent:サブビューのCocoaTouchをオーバーライドして、文書化された制限を削除します。うまくいけば、これが私のアプリに悪影響を与えることはありません（たとえば、サブビューでの誤ったタッチイベントを無視したり、メインビューに転送したりできます）。

• 素朴であり、素朴なアルゴリズムのパフォーマンスが低下するために、ユーザーが実際に使用するアクティブな領域をあまり多く追加しないことを信頼してください。

なにか提案を？

ポリゴンは常に単純ですが、必ずしも凸状である必要はないことに注意してください。また、私が使用する最も正確なヒットテストは、Quartzルーチンを使用したものです。CGPathContainsPoint

私はphpでポイントインポリゴンチェックを使用していますが、ポリゴンにないポイントが内部にあるため、大きなエラーが発生しています。

私の基本的な関数を以下に入力します (ここにあり、クラスから単純な関数に変更されています: http://www.assemblysys.com/dataServices/php_pointinpolygon.php )。私が考えることができる唯一のことは、どこかである種の丸め誤差ですか?

一例として、ポイントが単純な正方形である中央公園内にあるかどうかを判断しようとしていますが、公園の外のポイントから陽性を得ています。

洞察をありがとう、

-D

緯度/経度のポイントが、地球上のポイントを表す頂点によって定義されたポリゴン内に含まれているかどうかを把握しようとしています(緯度/経度も時計回りに)。これは、2D 緯度/経度空間にマッピングできるポリゴンの場合は簡単です。

これがますます困難になるのは、地球の半分をカバーする極から極へと移動する可能性のある円 (現在は 3D に戻る) です。緯度/経度への変換は正弦波のように見えます。ポリゴン テストの 2D ポイントは、このケースには適用されなくなりました。この問題を解決するアルゴリズムはありますか?

================== 以下のコメントの説明: =================== 多角形は (lon, lat) 度のペア、つまり (60, 90)、(60, 110)、(-30, 110)、(-30, 90)。

レイ キャスティング アルゴリズムを実装するコードがあり、それが機能します。ただし、地表の特定のポリゴンは、2D 空間の閉じたポリゴンに変換されません。

これは、コンピューター科学者にとっては少しトリッキーな質問です。100 x 100 のエントリ arr[i][j] の 2 次元配列/行列があるとします。i と j は 0 ～ 99 です。これは、各ドットがデータ値に対応する四角形のドットとして考えることができます。

ここで、4 点ポリゴンを定義し、4 点のインデックスを知っている場合: 4 点ポリゴンの内側にあるマトリックス内のエントリのみをループすることは可能ですか (巧妙なアルゴリズムはありますか)? つまり、ループ ラップの i と j のすべての値は、興味深い arr[i][j] の値に対応します (i と j は 4 ポイント ポリゴン内にあります)。

これは明らかですか？わかりにくいところはわかります。

敬具

Google から返された境界を保存しています。これらは、ne_lat、ne_lng、sw_lat、および sw_lng 座標の形式です。

私はいくつかの実装のためにmysql ploygons関数を探していました。ここにいくつかのサンプルエントリを含むサンプル関数があります:

GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))')

上のポリゴン関数でGoogleが返す境界の適切な置換を教えてもらえますか?

私は少し調査を行い、次のように結論付けました：

GeomFromText('Polygon((ne_lat ne_lng,ne_lat sw_lng,sw_lat sw_lng,sw_lat ne_lng,ne_lat ne_lng))')

ポリゴン関数に適切なエントリを作成しましたか??

前もって感謝します！