プログラミングコンテストでポリゴンのポイントを解決する最良のアルゴリズムとは何ですか?プログラミングコンテストのポリゴンアルゴリズムにおけるポイント
-3
A
答えて
0
あなたは、この使用することができ、凸多角形がある場合:
1
の点から(任意の方向に)線を撮影し、その場合には、多角形の縁を越えた回数をチェックそれではポイントはポリゴンの外側にあり、さもなければポイントはポリゴンの内側にあります。
多くのクエリポイントで行う必要がある場合は、O(log n)でレイ撮影を行うことができるように、ポリゴンを三角形分割(実際にはポリゴンとポリゴンの間の領域の三角形分割)
関連する問題
- 1. プログラミングコンテストのアプローチ
- 2. java - codesprint2プログラミングコンテストの回答
- 3. マップ内のポイントにラベルを付ける
- 4. Scalaの関数定義における複数のパラメータ節のポイントは何ですか?
- 5. Prologにおけるツリーポストオーバトラバーサル
- 6. 「セマンティックウェブ」におけるオントロジー
- 7. Celery 3.0.1におけるフレーミングエラー
- 8. ドットネットにおけるコンカレントコンピューティング
- 9. Rails 2.2.2におけるダイナミックスキャフォールディング
- 10. Javaクラスタリングにおけるガベージコレクション
- 11. Prologにおけるツリープリオーダートラバーサル
- 12. PostGIS:他のポイントから特定の半径内のポイントを見つける
- 13. ポイントをシェイプに変換するのに助けが必要
- 14. 時間/空間の複雑さの低減。プログラミングコンテスト
- 15. インテグレーションテストにおけるBeanのオーバーライド
- 16. AIRアプリケーションのデプロイにおける問題
- 17. Javaにおける戻り値の値
- 18. NuGetとTFSのベストプラクティスTFSにおける
- 19. のC++における多型、親クラス
- 20. ASPの意味におけるサーバーサイドJS
- 21. iosデバイスのコンパイルにおけるSIPHONエラー
- 22. Pythonのデスクトップアプリケーション開発における
- 23. salesforce.com - レポートアクセスにおけるロールベースの階層
- 24. iPadアプリケーションにおけるメモリの問題
- 25. ソフトウェアデザインにおけるUMLの使用
- 26. オーチャードのプロジェクトにおける参照エラー
- 27. .NETにおけるBODMASの原則
- 28. SQLAlchemyにおける継承の問題
- 29. Javaにおけるvolatileキーワードの動作
- 30. 再帰におけるトラッキングの深さ
一般的なシェイプ(つまり三角形や四角形)のほとんどに最適化されたアルゴリズムがありますが、適切な線を選択する限り、任意のポリゴンで動作するウィキペディアで簡単なアプローチが概説されています。 wikipedia.org/wiki/Point_in_polygon – Blender
-1計算幾何学コンテストに参加したいのですが、コミュニティがあなたのためにそれを解決するよう求めています! – cmannett85
その結論にどうやって来たのですか?cmannett85 ?? !! – user1284064