私は現在、サブ問題として 2D ポイント セットの変更を含むプロジェクトの研究を行っています。ポイント セット自体には、いくつかのポイントのクラスターが含まれます。これをどうにかして互いに分離し、クラスター ハル内のポイントを緩和する必要があります。あるいは、クラスターのハルポイントを取得し、それらをドメインとして使用し、それらの内部に (ほぼ) 等間隔にポイントを分散するだけで十分です。したがって、緩和はスキップされる可能性があります。最悪のシナリオとして、最大 10 万個の頂点を含むいくつかのポイント セットを処理する必要があるため、使用するアルゴリズムは高速である必要があります。私はこの問題の複雑さを知っています。そのため、車輪を再発明したくなく、可能であれば既存のコードを使用したいと考えています。これまでのところ、次のことがわかりました。
点集合緩和: Fortunes/Sullivans "Sweep Line" アルゴリズム: 最速のシングル スレッド ボロノイ ダイアグラム コンストラクターと言われています。ただし、コードを拡張するのは非常に難しいようで、デフォルトで抽出可能な情報には、少なくとも重心を計算して次の緩和反復を実行する必要があるボロノイ セル ハル データ (それらの頂点位置) が含まれていません。さらに、長方形以外のドメインは使用できません。
CVT: ボロノイ図を作成するための多目的ライブラリの束。ポイントの緩和と、ユーザーが指定した領域内のポイント セットもサポートしています。
CGAL: 基本的な MP サポートを備えた広範なフレームワークですが、明らかに統合された緩和方法はありません。各ポイント セットのサブクラスターの delaunay 三角形分割を作成し、これをボロノイ アダプターにフィードする必要があります。ボロノイ アダプターは、さらに緩和するためにボロノイ セル ハル データをクエリするイテレータを提供します。私がドキュメントを読んでいる限り、ドメインをサポートする必要があります（数千ページ:)
さらに、主に 3D で動作するように見える Voro++ などがあります。三角形。領域の制約を使用して、指定されたドメインからドローネ三角形分割を作成し、三角形の頂点を結果の点として使用できるようにします。
わかりました、現時点では、これをすべて非常にシンプルに保ちながら、CVTが私のニーズに合うべきだと私には思えます。しかし、よくわからないので、質問: できればドメインを使用して、ポイントセット緩和の実装を経験した人はいますか? どの既存のコードが望ましいでしょうか?
毛皮の提案に感謝します！t