1

P を単純であるが必ずしも凸であるとは限らない多角形とし、q を P 内にあるとは限らない任意の点とします。

P のエッジの最大数と交差する q から始まる線分を見つける効率的なアルゴリズムを設計してください。

言い換えれば、点 q に立っている場合、弾丸が最も多くの壁を通過するには、どの方向に銃を向ければよいでしょうか?

P の頂点を通過する弾丸は、1 つの壁に対してのみクレジットを取得します。

O(n log n) アルゴリズムが可能です。n は頂点またはエッジの数です。これはポリゴンであるため、エッジの数は頂点の数にほぼ等しくなります。

これは this this questionと同じですが 、答えを理解できませんでした。より具体的には、答えにはqが含まれていないようでした。また、ポリゴン上の各ポイントが頭とaになるため、頭と尻のことも明確ではありませんでしたそれが理にかなっている場合、各ポイントは 2 つのエッジに接続されているためです。ありがとう

4

1 に答える 1

2

したがって、頂点の近くでポリゴンと交差しない最適な回答には、ポリゴンの頂点とほぼ交差する仲間の最適な回答があります。

つまり、10個の「壁」を通過する線があり、それが頂点の近くにない場合は、10個の壁を交差させたまま、頂点に向かってある方向に平行移動できます。

この推論により、頂点の近くを通過するソリューションを検索するだけで済みます。

したがって、頂点（nlogn）を並べ替えてから、1つ（3n）とほぼ交差する可能性のある各線分を検索します。線が1つの頂点から別の頂点に移動すると、2つの壁が追加または失われる（または同じままである）ため、各候補線の交差の完全なセットを再計算せずにこれを行うことができます。この増分変化を各ステップで一定時間追跡できます。

于 2012-06-14T06:57:32.200 に答える