100 個のランダムなポイント (凸包を使用) が与えられた場合に、このポイントのクラウドを三角測量する単純な C++ アプリケーションを作成したいと思います。このテーマを検索しましたが、ドロネー三角形分割がオプションであることがわかりますが、これを実装する方法をまだ理解できません (たとえば、C++ で)。また、次のレベルでは、すべての Delaunay の「違法な」三角形を別の色でペイントして、Delaunay のアルゴリズムをよりよく示して理解できるようにしたいと考えています。
これらの点を三角測量する方法を理解してくれる人はいますか? 実装する必要がある小さなコード部分または一般的なアルゴリズムでしょうか?
I would strongly suggest not coding up any Delaunay Triangulation algorithm from scratch. If I were doing this to get an intuitive understanding of what the algorithm's output looks like, I'd take Johnathan Shewchuk's Triangle code and modify it to assign different colors, etc.
If, however, you are sufficiently motivated to implement this from scratch, then my suggestion would be to implement the 2D Delaunay Triangulation first, before you tackle the 3D version.
最初に一般的な三角測量が必要だと思いますが、それから Delaunay 法に準拠していないものをすべて修正しますか?
非常に悪い三角形分割アルゴリズム (角度ベクトルが悪い) は、次のようになります。
(i) 点群の凸包を取得する (ii) CH の任意の点 (最初の点を使用すると便利です) を CH の他のすべての点 (もちろん、次および前の点を除く) と接続します。すでにエッジを形成しています）。
(iiiA) 平面内の 1 つおきの点について、その点が三角形の中にある場合、その点をその三角形の 3 つの頂点と接続することによって、その点から 3 つの三角形を作成します。 (iiiB) 辺上にある場合 ( 100 ポイントの場合は少しありそうにありませんが、スキップできると思います)、それがある四角形の他の 2 つの頂点と接続します。
これで始められると思います。クラウドは完全に三角形化されますが、エッジの半分以上が Delaunay 違法になる可能性があります。次に、必要なエッジの修正 (反転) に進むことができます。
実装に問題がある場合は、サンプル コードを提供して、作業を開始できるようにします。ここでは、アルゴリズムの戻り値が三角形のセット/ベクトルであると便利であることを念頭に置いてください。そうすれば、それらを操作して個別に色を変更できます。
三角測量のアルゴリズムと C++ でのコーディングの両方について学びたい場合、C++ で三角測量をコーディングするプロジェクトを組み合わせることは魅力的に思えるかもしれませんが、初心者にとっては確かに難しすぎます。したがって、複合問題に取り組む前に、まず三角測量のアルゴリズムの側面とC++ の基本を別々に学ぶことをお勧めします。