HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

Exact, parallel 2D Delaunay triangulation for int32 coordinates (github.com)

59 pointsby oryx172919 コメント

要約

Delaunay32は、正確な整数述語と並列処理を組み合わせたC++17ライブラリで、大規模な2D点集合のデロネー三角形分割を高速かつ正確に行います。整数座標だけでなく、浮動小数点座標も直接扱え、既存のライブラリと比較して大幅な高速化を実現しています。画像処理やGISなど、離散的または高解像度で量子化可能なデータに適しています。

全文翻訳

Delaunay32

符号付き32ビット整数ポイントのための高速、並列2Dドロネー三角形分割。

[画像: 制約のある外側および穴の境界を持つポリゴン文字ドメイン内で三角形分割されたブルーノイズポイント]

Delaunay32は、正確な整数述語を中心に構築されたC++17ライブラリです。再利用可能なTriangulatorは、ポイント、制約、およびポリゴンドメインを設定済みの問題として受け取り、単一のtriangulate()呼び出しでトポロジーを構築してエクスポートします。

コアAPIはstd::int32_t座標のみを受け入れます。浮動小数点入力は、トライアングレーターに到達する前に、スタンドアロンのquantize()ユーティリティで明示的に変換されます。

ブラウザおよびJavaScript/TypeScriptでの使用については、Delaunay32 WebAssemblyパッケージとそのインタラクティブデモを参照してください。

パフォーマンス

Apple M1(8コア、16 GB RAM)で、100万個のユニークで制約のない整数ポイントに対する実行時間を測定しました(三角形のみの出力)。相対実行時間は、8スレッドのDelaunay32を基準に正規化されています。値が低いほど優れています:

実装スレッド数実行時間相対実行時間
Delaunay32845.4 ms1.0×
Delaunay321131.6 ms2.9×
Fade2D 2.17.3自動235.2 ms5.2×
Fade2D 2.17.31314.1 ms6.9×
delaunator-cpp (c1521f6)1542.0 ms11.9×
Triangle 1.61584.0 ms12.9×
CDT 1.4.51988.7 ms21.8×

特長

  • 受け入れられた整数入力の各々に対する正確な述語
  • シリアルまたは共有メモリ並列実行
  • 決定論的な同一点処理
  • スタンドアロン制約および穴のある分離ポリゴンドメイン
  • 制約とすべてのポリゴン境界に対する単一のバッチ処理トポロジー
  • 三角形のみ、または完全なトポロジーの結果と操作レポート
  • 明示的で設定可能な浮動小数点から整数への量子化
  • 各三角形に含まれる元の入力インデックス
  • サードパーティ製ソース依存関係なし

ビルド

デフォルトのトップレベルビルドには、ライブラリ、追加機能、テスト、ベンチマーク、および完全なサンプルスイートが含まれます:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
ctest --test-dir build --output-on-failure

ライブラリのみのビルドの場合:

cmake -S . -B build \
  -DDELAUNAY32_BUILD_BENCHMARKS=OFF \
  -DDELAUNAY32_BUILD_EXTRAS=OFF \
  -DDELAUNAY32_BUILD_EXAMPLES=OFF \
  -DDELAUNAY32_BUILD_TESTS=OFF
cmake --build build --parallel

コアCMakeターゲットをdelaunay32::delaunay32としてリンクします。オプションのJSON、サンプリング、SVGユーティリティはdelaunay32::extrasから利用可能です。

使用方法

#include <delaunay32/delaunay.hpp>

#include <vector>

int main() {
    const std::vector<delaunay32::Point> points = {
        {0, 0}, {100, 0}, {100, 100}, {0, 100}, {48, 37},
    };

    delaunay32::TriangulationOptions options;
    options.thread_count = 0; // ハードウェアスレッド数を選択。

    delaunay32::Triangulator triangulator;
    triangulator.set_options(options);
    triangulator.set_points(points);
    const delaunay32::TriangulationResult result =
        triangulator.triangulate();

    for (const delaunay32::Triangle& triangle : result.triangles) {
        const auto& a = points[triangle.i0];
        const auto& b = points[triangle.i1];
        const auto& c = points[triangle.i2];
        // a, b, c は反時計回りです。
    }
}

triangulate()は、例外が発生した場合でも、設定された問題を消費します。新しい問題を開始するにはset_points()を呼び出します。これにより、オプション、割り当て、およびワーカープロセスは保持されたまま、以前の制約とポリゴンドメインがクリアされます。

制約とポリゴンは実行前に設定されます:

triangulator.set_points(points);
triangulator.set_constraints(constraints);
triangulator.set_polygons(polygons);
const auto result = triangulator.triangulate();

隣接情報、完全な入力境界、および重複表現については、ResultDetail::Fullを選択してください。三角形の詳細はデフォルトです。

浮動小数点変換は意図的に分離されています:

#include <delaunay32/quantization.hpp>

const delaunay32::QuantizationResult converted =
    delaunay32::quantize(float_points);

triangulator.set_points(converted.points);
const auto result = triangulator.triangulate();

変換されたベクトルは、元の長さとインデックス順序を保持します。そのQuantizationReportは、マッピング、測定された誤差、および衝突を記録します。

その他

./build/delaunay_benchmark --quickを実行して、一様、クラスター化、対角線のポイント分布全体で短いローカルパフォーマンスを実行します。

追加機能が有効な場合、./build/delaunay_workload_benchmark --quickは、制約、完全な結果、SVG記録/シリアライゼーション、および境界/切断ポリゴンサンプリングもカバーします。より大きなフィクスチャと7回の測定実行には--quickを省略してください。CSV結果は中央ミリ秒を報告します。入力生成は除外され、出力破棄および(三角形分割の場合)set_points()が含まれます。

ライセンス

MIT。LICENSEを参照してください。サードパーティの依存関係ステータスはTHIRD_PARTY.mdに記録されています。