geometry - ボロノイ図から点集合の凸包を抽出する方法

Question

O(n) のポイントのボロノイ図からポイント セットの凸包を計算するためのアルゴリズムが必要です。ボロノイ図はバウンディング ボックスに含まれ、二重接続エッジ リストとして格納されます。入力は、境界ボックス上に原点があるハーフ エッジです。

無限に長いボロノイ エッジを共有する場合、2 つの点が凸包上で隣接していることはわかっています。

Answer 1

無限のセルのみが境界エッジを持つように十分な大きさのバウンディング ボックスがある場合、この作業は難しくないように見えます。境界エッジを反復処理し、それらのそれぞれについて、それを前後にトラバースして、最初の非境界エッジFおよびを見つけますB。トラバース中に見つかった現在およびすべての境界エッジを としてマークしusedます。エッジがFありB、ボックスが存在しない場合は無限になります。したがって、それらは「中心」が凸包の一部である面 (fFおよび)に接触し (現在の面は)、クロスエッジは凸包の一部です。顔を見て、 の双子から前方に反復して、次の非境界エッジを見つけます。それが 'B'-twin に等しい場合 (または境界エッジがfBCC-to-FfFFF1used）、 終わったよ。そうでない場合は、次のネイバー ('fF1') をトラバースします。