問題タブ [medial-axis]

Delaunay三角形分割がそのステップである、内側軸抽出の実装を必要とするプログラムを書いています。外部内側軸は不要であるため、対応する外部三角形を削除する予定です。幸いなことに、多くの図が掲載されたページに出くわしました。また、内部および外部の Delaunay 三角形を決定する方法のヒント (「破線の周囲に基づく」) もありましたが、詳細な説明はなく、ヒントにすぎません。アルゴリズムを知っている人はいますか？

編集:最初の点が閉じた多角形の境界からサンプリングされることを忘れていました。私の意図は、各ドローネ三角形が多角形の内側にあるかどうかを判断することです。

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

_{（出典：kiev.ua）}

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

コードプレックス（FortuneVoronoi）でボロノイアルゴリズムのC＃バージョンを見つけました。ポリゴンを適用した後、次のようになります。

代替テキストhttp://www.carbonatlas.com/geonotes/gaia_voronoi.png

緑は元のポリゴンです。オレンジはボロノイ頂点で、黒い線はボロノイエッジです。

これらの頂点で必要なものの作成を確認できますが、不要なものをすべて除外するために必要な次のステップがわかりません。

私はあなたが提供できるどんな助けにも感謝します。

与えられた2つの曲線の内側軸を計算する方法を知っている人はいますか？

内側軸： http： //en.wikipedia.org/wiki/Medial_axis

これが私がそれを計算する必要がある形です：

内側の軸である濃い黒の線を自分で描きましたが、動的に計算できる必要があります。

これが私がこれまでに行ったことのアプレットとコードです：http： //www.prism.gatech.edu/~jstrauss6/3451/sample/

既知の変数は次のとおりです。-ptA、B、C、D-赤、緑、および黒の円の半径-pt QおよびR（画像のすぐ外側）、黒の円。

3D 多面体の正確な中心軸 (または選択した用語!) を計算するソフトウェアを見つけることに興味があります。出力は三角形の面、場合によってはエッジ、および頂点のリストであり、内側表面の接合部、シート、および継ぎ目を表すと思います。理想的には、凹面形状を含むすべての多面体を処理できるものが必要ですが (三角形の面では十分ではありません)、凸多面体を処理できるものを見つけることができれば幸いです。

まず、私が知っているソフトウェアについて教えてください。

私が変換している形状が複雑な表面であると仮定し、表面上に密集した点を分散させることによって、さまざまな「近似」方法が利用可能です。
これらの方法の 1 つは、http: //www.cs.ucdavis.edu/~amenta/powercrust.html によって提供される powercrust ソフトウェアです (凹型のケースを正しく処理するために、このソフトウェアに対してポイント ファイルをどのように定義する必要があるかはわかりませんが、承知しました）

別の近似法は、Tight Cocone (http://www.cse.ohio-state.edu/~tamaldey/cocone.html) に統合されています。これもまた、表面上に点を密に分布させ、ボロノイ図を使用して中心軸に収束させます。表面が正確に知られているという事実を利用する「CAD モデルの改善された中心軸」バージョンがあります。ただし、この改善されたモデルは、配布されたコードには組み込まれていません。

Gianni Schena (http://www.mathworks.com/matlabcentral/fileexchange/4917-skeleton-in-3d) による「3D のスケルトン」などの Matlab コードがあり、距離に基づくいくつかの単純な方法を使用します。変身。まだ概算です。

明らかに近似法は、表面に「スパイク」を与えて、特定のタイプの数値不安定性に悩まされる可能性があります。また、面と頂点の非常に大きなデータ構造を生成します。私が欲しいのは、非常に単純で小さなデータ構造を持つべき多面体 (立方体のような) の中心軸/表面の正確な表現です。

[2004 年、Culver、Keyser、および Manocha による多面体の内側軸の正確な計算] では、多面体の正確な内側軸を計算する方法が公開されました。しかし、誰かが実際にこの方法を実装したソフトウェアを見つけることができません。

何か知っている人、または 3D 内側表面ソフトウェアへの私の小さな進出に追加する何かを持っている人はいますか?

複雑な（ただし自己交差しない）ポリゴンを穴で三角形分割して、結果の三角形がすべてポリゴンの内側に配置され、そのポリゴンを完全に覆い、ドロネー三角形の規則に従うようにします。

もちろん、すべてのポイントに対してDelaunay三角形分割を作成することもできますが、ポリゴンの一部のエッジが結果の三角形分割に含まれないのではないかと心配しています。

それで、そのような三角測量は可能ですか？はいの場合、どうすればそれを行うことができますか？

念のため-ポリゴンの内側軸の近似を作成するために必要です（結果の三角形のすべての円周点を接続することで実行できることを願っています）。

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

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

これらの写真に示されているようなものを取得する必要があります。

中心軸変換に関連していると思いますが、垂直線または水平線のみが必要です。助言がありますか？

SVG にパス要素として格納されている 2D 形状があります。形状は、ベジエ曲線と線分で構成されています。

また、円弧長のパラメーター化を使用して生成している形状に沿って等間隔の点のセットもあります。

SVG またはこれらの点を使用して形状の中心軸を決定するにはどうすればよいですか?

私は Python を使用していますが、あらゆる種類の疑似コードまたはアルゴリズムのアドバイスをいただければ幸いです。

以下は、私が扱っている形状のタイプの例です。赤い点は、曲線に沿ってサンプリングされたポイントです。