int32座標のための正確で並列な2Dデロネー三角形分割

Delaunay32 高速で並列な2Dデロネー三角形分割。正確な整数述語と直接的な浮動小数点入力を利用。Delaunay32は、ピクセル、ラスターサンプル、ボクセル投影、固定小数点ジオメトリ、その他の量子化された空間データなど、大規模な離散2D点集合の三角形分割を行うためのC++17ライブラリです。有限の浮動小数点ポイントも直接渡すことができ、ライブラリは内部でそれらを量子化しますが、出力インデックスは元の座標を参照し続けます。正確な整数述語と、Morton順序の分割統治アルゴリズム、コンパクトな2-dartトポロジ、オプションのマルチスレッディングを組み合わせています。その結果、決定論的で堅牢、特に大規模な点集合で高速な三角形分割器が実現しました。大規模な点集合では、Delaunay32はdelaunator-cppよりも10倍以上、Fade2Dよりも約4倍高速です。 ハイライト * 認定された座標範囲のための正確な方向およびインサークル述語 * 負の座標や大きなオフセットを含む符号付き32ビット整数入力 * シリアルおよび共有メモリ並列実行 * 重複ポイントの決定論的な処理 * 制約付きデロネー三角形分割（非交差整数セグメント用） * 三角形インデックスは、元の入力を参照し、三角形分割グリッド上で反時計回りに配置されます * オプションのハーフエッジ隣接性、凸包、重複代表マッピング * 精度制限と衝突ポリシーを備えた、自動、固定ステップ、または固定スケールの浮動小数点量子化 * ポイントサンプリング、Delaunay32ジオメトリJSON、ドメインクエリ、SVGエクスポートのためのオプションのdelaunay32::extrasコンパニオンターゲット * MITライセンスで、通常のライブラリ使用では依存関係なし ドキュメント * 使用ガイド：完全なAPI、型、正確性、量子化、スレッディング、およびエラー契約 * 変更履歴：リリースノートと破壊的なAPI変更 * 貢献ガイド：バグレポート、検証、およびプルリクエストの期待事項 * セキュリティポリシー：サポートされているバージョンとプライベートレポート 例 * 浮動小数点SVG例：量子化レポート付きのエンドツーエンド浮動小数点入力 * 制約付きSVG例：同じ固定ジオメトリの通常のおよび制約付き三角形分割 * ポリゴンSVG例：3つの穴を持つ凹型整数ドメインと、ドメインクリッピングによって省略されたポイント * ポリゴンロゴSVG例：JSONで定義された10個のポリゴングリフドメイン内の新しいブループリントポイント * 整数SVG例：生成されたまたはJSONの整数入力 いつ使用するか Delaunay32は、すでに離散的であるか、高解像度の均一な量子化に耐えられるデータ向けです。典型的な例としては、画像空間ジオメトリ、ラスターおよびハイトフィールドサンプル、投影されたボクセルデータ、固定小数点マップ、グラフィックス、および投影された空間データセットが含まれます。直接浮動小数点入力は、ほとんどのグラフィックス、マッピング、可視化、および一般的なメッシングアプリケーションで実用的であり、正確なエッジトポロジは必要ありません。triangulate_float()はソース座標を変更せずに、元の入力へのインデックスを返します。エッジの決定のみが内部で量子化された整数座標を使用します。結果のメッシュは、通常、ソース値から直接計算されたものに非常に近くなりますが、そのエッジが同一であることは保証されません。差は、ほぼ一致する、共線上の、または共円上のポイントで最も可能性が高くなります。元の浮動小数点座標の正確なデロネー・トポロジが必要な場合は、アダプティブ・エグザクト・トライアングレーターを使用してください。 パフォーマンス 以下の結果は、100万ポイントでのリリースビルドベンチマークをまとめたものです。Delaunay32の自動マルチスレッドモードは1.0倍のベースラインであり、低いほど良いです。4.0倍は、実装がおよそ4倍の時間がかかったことを意味します。各比較では、すべてのライブラリで同じ入力ポイントが使用されました。結果は、測定されたポイント分布全体、および制約付き三角形分割の場合はいくつかの代表的な制約レイアウトの平均値です。 |ワークロード|Delaunay32|Fade2D|delaunator-cpp| |---|---|---|---| |制約なしデロネー|1.0倍|約4.5倍|約11倍| |制約付きデロネー|1.0倍|約4.3倍|—| delaunator-cppは制約付き三角形分割をサポートしていないため、制約付き行には結果が表示されません。Fade2Dの結果は、Fade2D 2.17.3のバルク挿入APIを使用して測定されました。delaunator-cppは、オプションのベンチマークのためにのみサブモジュールとして含まれています。Delaunay32自体はそれに依存しません。これらの比率は意図的に概算であり、マシンおよびワークロードに依存します。リポジトリには、さまざまなポイント分布にわたる制約なしDelaunay32とdelaunator-cppを比較する詳細なベンチマークが含まれています。より詳細なパフォーマンス情報については、ご自身のマシンで実行してください。 クイックスタート リポジトリをクローンし、オプションのベンチマーク依存関係を初期化します。 git submodule update --init --recursive cmake -S . -B build -DCMAKE_BUILD_TYPE=Release cmake --build build -j ctest --test-dir build --output-on-failure ライブラリのみのビルドの場合、Delaunatorは不要です。 cmake -S . -B build \ -DCMAKE_BUILD_TYPE=Release \ -DDELAUNAY32_BUILD_BENCHMARKS=OFF \ -DDELAUNAY32_BUILD_TESTS=OFF \ -DDELAUNAY32_BUILD_EXAMPLES=OFF cmake --build build -j 別個にリンクされるextrasコンパニオンはデフォルトでビルドされます。厳密なコアのみのビルドの場合は、-DDELAUNAY32_BUILD_EXTRAS=OFFを追加してください。 インストール: cmake --install build Windows (MSVC) Visual StudioにC++によるデスクトップ開発ワークロード、Git、およびCMakeをインストールします。PowerShellから、次のようにマルチコンフィギュレーションVisual Studioジェネレーターを使用します。 git submodule update --init --recursive cmake -S . -B build cmake --build build --config Release --parallel ctest --test-dir build -C Release --output-on-failure cmake --install build --config Release 単一コンフィギュレーションのLinuxおよびmacOSビルドとは異なり、Visual Studioはビルド、テスト、インストールの際にコンフィギュレーションを選択します。したがって、ビルドされた実行可能ファイルはbuild\Release\の下にあります（例: build\Release\delaunay_benchmark.exe）。エクスポートされたCMakeターゲットは、三角形分割用のdelaunay32::delaunay32と、オプションのコンパニオンユーティリティ用のdelaunay32::extrasです。extrasターゲットはコアターゲットにリンクされ、コアターゲットはextrasにリンクされることはありません。 使用法 整数入力 #include <delaunay32/delaunay.hpp> #include <vector> int main() { std::vector<delaunay32::Point> points = { {0, 0}, {100, 0}, {100, 100}, {0, 100}, {48, 37}, }; // 1はシリアルパスを選択します。0はハードウェアスレッド数を選択します。 delaunay32::Triangulator triangulator(0); const std::vector<delaunay32::Triangle> triangles = triangulator.triangulate_int(points); for (const auto& triangle : triangles) { // i0, i1, i2 は元のポイントベクトルを反時計回りの順序でインデックス付けします。 } } 浮動小数点入力 有限の浮動小数点座標をFloatPoint値として直接渡します。手動での変換や量子化は不要です。 std::vector<delaunay32::FloatPoint> points = { {0.125F, 0.25F}, {5.5F, 0.1F}, {6.0F, 4.5F}, {-1.0F, 5.0F}, }; const std::vector<delaunay32::Triangle> triangles = triangulator.triangulate_float(points); // Triangleインデックスは変更されていないFloatPointベクトルを指します。 for (const auto& triangle : triangles) { const auto& a = points[triangle.i0]; const auto& b = points[triangle.i1]; const auto& c = points[triangle.i2]; // 元の浮動小数点座標を持つa, b, cを使用します。 } 量子化の詳細、隣接性、凸包、または代表マッピングが必要な場合は、triangulate_float_full(points)を使用します。その量子化フィールドは、グリッドステップ、測定された座標誤差、およびポイントの衝突を報告します。QuantizationOptionsは、別々のバッチ間で安定したマッピングを提供できます。 delaunay32::QuantizationOptions options; options.mode = delaunay32::QuantizationMode::FixedScale; options.origin_x = 0.0; options.origin_y = 0.0; options.scale = 1000.0; const auto triangles = triangulator.triangulate_float(points, options); 返される頂点は元の精度を保持します。接続性は内部整数グリッド上で計算されるため、エッジの選択は、特に幾何学的な退化に近い場合、元の浮動小数点値の正確なデロネー三角形分割とは異なる場合があります。 制約付き整数入力 同じ整数ポイントベクトルへのインデックスのペアとしてエッジを渡します。 std::vector<delaunay32::Constraint> constraints = { {0, 2}, {2, 4}, }; const std::vector<delaunay32::Triangle> triangles = triangulator.tr