C＃を使ってポリゴンの内側軸を見つける

Question

ポリゴンの中心線を見つける方法を理解しています。私のGoogle検索は、私が必要とするものが「内側軸」と呼ばれると信じさせました。このように：

alt text http://www.ndl.kiev.ua/downloads/center_line.png

私が読んだによると、私は必要なもののセグメントのための2Dボロノイ図構成アルゴリズムを用いて製造することができます。

私はCodePlexの上のボロノイアルゴリズムのC＃バージョン（FortuneVoronoi）を見つけたし、それに私のポリゴンを適用した後、私はこれで終わる：

alt text http://www.carbonatlas.com/geonotes/gaia_voronoi.png

グリーンは、元の多角形です。オレンジはボロノイの頂点であり、黒い線はボロノイの頂点です。

私はこれらの頂点に必要なものを見ることができますが、私が必要としないすべてのものをフィルタリングするために必要な次のステップが不明です。

ご提供いただけるお役に立てれば幸いです。

Answer 1

一つの簡単な解決策は次のようになります。

1. は、ポリゴンの頂点のドロネー三角形分割を作成します。
2. ポリゴン内部のボロノイ頂点を特定ボロノイは、2つの内部のボロノイ頂点を接続するエッジ
3. 出力（ http://en.wikipedia.org/wiki/Point_in_polygonを参照）。

膨大なデータがある場合、交差点は非常に高価になる可能性があります。

次に、questionのような同様のアプローチを実行できます。this solutionも同様に機能します。私がやる方法：

1. ポリゴン頂点のDelaunay三角形分割を構築します。
2. デラウネイエッジで覆われていないすべてのポリゴンエッジの中点を挿入します。すべてのポリゴンのエッジがDelaunayエッジで覆われるまで、これを再帰的に行います。
3. ポリゴンのエッジに対応するすべてのドローネエッジにマークを付けます。
4. ステップ3.-5を使用して内側軸を抽出します。 in this solution

PSです。まさにそれを計算すると、はるかにコストがかかるが、ティーザーとして...あなたが黒の入力サンプルポイントのためにこのような結果を得ることができ、両方のソリューションは、中心軸の一部近似を与えることに注意してください：

Answer 2

うわー。私はここで手足に出て、ポリゴンの内側と外側の両方についてアルゴリズムが混乱しているかもしれないことを示唆しています。元のポリゴンのエッジと頂点を定義するときは、「内側の」が常に「右手のルール」のようなものを使用して見つけられるように定義されていることを確認する必要があります。右下隅のポリゴンを見るだけで、ポリゴンの端が実際に交差しているように見えます。たぶんアルゴリズムは、そのセクションと他のものを「内側に」見ているかもしれません。左下に同じ。

これはアルゴリズムが内部の方向と外部の方向を判断できないように思われるという私の直感です。

私は、ポリゴンの外にあるすべてのVoroni「ノード」を除外することが簡単なアプローチだと考えていますが、それは見えません。ダイアグラムを詳しく見ると、各ノードには3つのエッジがあり、他のノードに接続しているように見えます。おそらく、3つのエッジのいずれかがポリゴンの外側のノードに接続されているノードを除外することができます。それは働くだろうか？コメントで示唆したよう

Answer 3

同様の構成はStraight skeletonであり、ポリゴン自体を縮小し、頂点が中心に近づくにつれてその頂点をトレースすることで構築できます。これは、構築するのが少し簡単かもしれませんが、内側の軸とまったく同じ曲線ではありません。