（特定の三角測量に）多角形の輪郭を構成します

Question

どのようにして三角形だけで形成され、それが穴を持つことができ、外部輪郭が凹/凸型にすることができ、穴はまた、凹/凸することができ、2Dポリゴンの輪郭を構築して行くでしょう。

それはまさにの逆だと思わこの私はこっち読んでいるものから、三角測量の問題。 あなたはこの種の問題を処理するすべての記事を知っていますか？

オクトリ/四分木は、これに関連していますか？

Answer 1

私はあなたがこれらの三角形のエッジに沿って隣接していることを、「充填」三角形を構成する3点のセットの形式でデータを持っていること、および完全な形状の角であろうすべての頂点もの頂点であることを推測しますこの点を触れるすべての三角形。それからちょうど、倍増されていない、すなわち2つの隣接の三角形に属していないすべてのエッジを見つける必要があります。

Answer 2

私は、あなたが三角形のあなたのセットを表すために、トポロジカルなデータ構造を作成した後、境界上にある三角形の辺の上に順に反復するためにその構造を使用することによって、あなたの問題を解決することができると思います。

たとえば：あなたはhalfedgeデータ構造を作成することができます。 （正確に）あなたも、境界にhalfedgesを挿入すると仮定すると、境界輪郭を反復処理することは、境界上の1 halfedgeを見つけるのと同じくらい簡単ですし、あなたが戻ってあなたから始めhalfedgeに到達するまで、それを反復して、「次」ポインタです。

同様にhalfedgesに、あなたは翼端などのような他のトポロジカルな構造を使用することができますが、考え方は同じです。