java - サブ二次時間でポリゴンの中心軸を構築することは可能ですか?

Question

サブ二次時間で穴のある複雑な非凸多角形の中心軸を構築することは可能ですか? アルゴリズムの説明を教えてください。

または、Java にそのためのライブラリがあるのでしょうか。

Answer 1

http://en.wikipedia.org/wiki/Medial_axisはボロノイ図のリンクを示唆しており、IIRCボロノイ図はn log n時間で計算できます（Fortunesアルゴリズム）。

ただし、ボロノイ図からエッジ（およびおそらく部分的なエッジ）を選択するなど、後でやるべきことがまだいくつかあると思います。基本的に、ボロノイ図はポリゴン内の頂点に基づいており、エッジに関する情報、およびどの領域が塗りつぶされ、どの領域が穴であるかに関する情報が不足しています。したがって、その追加情報を考慮に入れるためにやるべきことが残っているに違いありません。

ただし、ボロノイ図ができたら、この余分な作業を線形時間で実行できることを願っています。ボロノイ図自体は、たとえば、ポリゴンのどのエッジがどのボロノイセルを通過するかを決定するために使用できるインデックス構造を提供します。

私はこれを適切に考えていませんが、ボロノイ図を元のポリゴンにクリップすることで、正しい結果が得られる可能性があるという考えがあります。