ボロノイ図からの凸面船体

O（n）の点のボロノイ図から点集合の凸包を計算するアルゴリズムが必要です。ボロノイ図はバウンディングボックスに含まれ、二重に接続されたエッジリストとして保存されます。入力は、原点が境界ボックスにあるハーフエッジです。唯一の無限の細胞は、境界エッジを持って、タスクはdoesnのように、あなたが十分に大きいバウンディングボックスを持っている場合はボロノイ図からの凸面船体

は私が

出典

2010-11-23 wallacer

1つの無限端から次の無限端に向かって凸包をまっすぐに歩くことができないのはなぜですか？問題がどのように表現されているのかをもう少し詳しく語りたいので、難しさを理解することができます。 –

問題の難しい部分は、ボロノイ図の特定のエッジが実際に無限に続くかどうかをテストすることです。また、ボロノイ図とバウンディングボックスは二重に接続されたエッジリストとして格納されているため、もう一つの難しい部分はDCELを正しくトラバースする方法を考え出すことです。いずれにせよ、私は働いていた解決策を思いついた。多分私はいつかすぐにここに書きます。 – wallacer

... 2つの点は、彼らは無限に長いボロノイ辺を共有する場合に限っ凸包上で隣接していることを知っていますタフに見えます。それぞれの境界エッジを反復して前後に移動し、最初の非境界エッジを見つけますFとB。トラバース中に見つかった現在およびすべての境界エッジをusedとマークします。ボックスが存在しない場合は、エッジFとBは無限になります。したがって、「中心」が凸包（現在の面はC）の一部である顔（fFおよびfB）に接触し、クロスエッジC-to-Fは凸包の一部です。 fFの顔をとってFのツインフォワードから反復して、次の境界以外のエッジ、たとえばF1を見つけます。それが 'B'-twin（または境界エッジがusedだった場合）に等しい場合は、終了します。そうでなければ、次の隣人（ 'fF1'）を横切ります。

出典

2011-01-27 22:28:27 mbaitoff

十分な大きさのバウンディングボックスがない場合はどうなりますか？ –

@uvts_cvs：つまり、すべての点がバウンディングボックスに囲まれているわけではありません。それらを凸包に含めることができないので、それらの点を捨てる。残りの点は元のセットと同じ凸包を持っています。 – mbaitoff

-1

O（n）時間にボロノイ図の凸包を計算することは可能だと思います。

Voronoi図とCHにある頂点の場合、Voronoi Diagramのセルを反復し、Grahmスキャンアルゴリズムと同様に凸包を使い切ることができますが、その方法は異なります。

あり、ここで不足している唯一の理論は、あるM4帳、定理7.4スプリンガーによって計算幾何学によると、次の...

を見て：だけその場合ならば点qははVor（P）の頂点であります最大の空白C_p（q）は、その境界上に3つ以上のサイトを含む。これは、すべての反復をチェックする必要があるサイトはO（1）で完了したことを意味します。つまり、O（n）サイトを反復するだけです。

定理7.3によると、ステロンnのボロノイ図の頂点の数は、2n-5（線形次数）以下の無地のサイトを指します。

したがって、ボロノイ図のCHをO（n）時間で計算することができます。

出典

2014-07-13 18:57:35 TripleS

ボロノイ図からの凸面船体

答えて

関連する問題