4

複雑な多角形の凸包を見つけるための最悪の O(n log n) アルゴリズムと、単純な多角形の凸包を見つけるための最悪の O(n) アルゴリズムがあることは知っています。複雑な多角形の凸包を見つけるための最悪の O(n) アルゴリズムはありますか?

複雑な多角形は、線分が交差する可能性がある多角形です。複雑な多角形の凸包を見つけることは、点の順序付けられていないリストの凸包を見つけることと同じです。

4

4 に答える 4

2

ポイントセットが、比較ベースでないソートメカニズム（基数ソートなど）が比較ベースの方法よりも高速になるようなものである場合、グラハムスキャンアルゴリズム（http://www.math.ucsd.edu/ ~ronspubs/72_10_convex_hull.pdf ) を計算します。グラハム スキャンの時間の複雑さは、並べ替えステップによって支配されます。残りは線形です。

于 2013-10-11T13:56:35.120 に答える
2

私はかなり確信していません。任意の点集合の凸包は、並べ替えと同等であることを示すことができます。任意のポイント セットを注文し、ポイントを順番に接続して複雑なポリゴンにすることができます。これにより、任意のポイント セットに関する問題が軽減されます。

これは、凸包がソートと同等であるという証明へのリンクです。私はあまりにも怠惰で、自分で書くにはあまりにも悪いタイピストです.

于 2010-07-30T21:38:24.223 に答える
0

一般に、O(n) ソリューションはありません。O(n log n) よりも優れたピクセル化されたバージョンがあります。ただし、実際に使用するのは気が狂ってしまうほど、他の方法で足を引っ張っています。

最初のポリゴン (頂点 0、1、2 を使用) を画面空間にレンダリングしてから、個別の ID を使用して頂点自体を再レンダリングし、後で識別できるようにします。たとえば、フレーム バッファーを RGBA ffffffff にクリアし、凸包によってカバーされるスペースに fffffffe を使用できます。各頂点は、その ID を RGBA として使用してレンダリングされます。00000000、00000001など

16 ビットの例:

fffffffffffffff
fffffff0fffffff
ffffffeeeffffff
fffffeeeeefffff
ffffeeeeeeeffff
fffeeeeeeeeefff
ff2eeeeeeeee1ff
fffffffffffffff

新しいポイントのチェックは、現在のフレーム バッファでの単純なルックアップです。それが占有するピクセルがポリゴンまたは頂点 ID で「シェーディング」されている場合、新しい頂点は拒否されます。

新しい頂点が既存のポリゴンの外側にある場合、新しい頂点と凸包の内側のある点の間の最初のピクセルを見つけ (最初のポリゴンの真ん中にある何かがうまく機能します)、包の円周に沿って - 両方向に行進します。 - 新しい頂点から船体の反対側にいることに気付くまで。(これはユーザーへの演習として残します。効率の観点からすると、すべてうまくいかないソリューションがたくさんあります。) これらの 2 つのポイントで定義されたポリゴンと新しい頂点に、ポリゴン スペースの ID を入力します。注意してください。頂点 ID を消去せず、次のピクセルに進みます。

完了すると、ハル ID によって完全に囲まれていない頂点 ID を含むピクセルは、凸包頂点になります。

アルゴリズムの複雑さは頂点の数で O(n) ですが、欠点は明らかです。 ほぼすべての頂点がすぐに拒否されるように処理するばかげた、非常識な、驚異的な数のポイントがない限り、またエイリアス結果の制限を受け入れることができない限り、正気の誰もそれを使用しません。

友達は、友達にこのアルゴリズムを実装させません。

于 2010-07-30T23:03:29.107 に答える