プログラミングコンテストで多角形の点を解くのに最適なアルゴリズムは何ですか?
2 に答える
1
ポイントから（任意の方向に）光線を放ち、ポイントがポリゴンの外側にある場合はポイントがポリゴンの外側にあり、そうでない場合はポイントがポリゴンの内側にある場合は、ポリゴンのエッジを横切った回数を確認します。
多くのクエリポイントに対してそれを行う必要がある場合は、ポリゴンを三角測量することができます（実際には、ポリゴンを含む凸面の内側と領域の両方を三角測量します）。これにより、O（log n）でレイシューティングを行うことができます
于 2012-04-17T12:25:51.090 に答える
-1
凸多角形がある場合は、これを使用できます：
于 2012-04-08T06:11:45.390 に答える