任意の点 P が与えられ、距離でソートされた近くの (メッシュ化されていない) ポイントを検索できると仮定すると、P を含むドロネー三角形を形成する 3 つの近くの点を効率的に決定できますか? もしそうなら、どのように？
1 に答える
1
共線点のない2Dにいると思います。私が提案するものは、3D でも機能します。すべてのポイントを含む Kd ツリーを構築します。次に、P の 2 つの最近傍を探します。外接円を作成します。
その円の中心を考えて、最も近いものを探します。最初に見つけた点 (三角形の点は無視) が円の半径よりも遠い場合、三角形ができています。そうしないと、空の円のプロパティに違反し、その場合、ポイントが三角形の外側にあることがわかります。これで、2 つの三角形を定義し、以前と同様に空の円のプロパティが検証されていることを確認できます (ただし、円内に点が見つかった場合は、点が三角形の内側にあるかどうかを確認する必要があると思います)。次に、外接円内にあるすべての四つの点と他のすべての点で Delaunay 三角形分割を行うようなものです。
実装には、たとえばOrthogonal_incremental_nearest_neighbor、Triangle_2クラスのhas_on_bounded_side関数、および circlecenter 関数を提供する CGAL を使用できます。
また、最初の 3 つの点で初期化されたDelaunay_triangulation_2クラスを直接使用して、三角形の面の空円プロパティを無効にする点を段階的に挿入することもできます。
于 2012-04-05T12:30:34.030 に答える