c++ - ポリゴン ライブラリのブール関数の計算時間を向上

Question

Boost ポリゴン ライブラリのブール関数を使用した人はいますか? ブースト ポリゴン ライブラリ

アルゴリズムの時間複雑度は O(nlogn)、n = #points であると書かれています

200000 個のランダムに生成されたポリゴンを入力します (5~8 個のポチンを使用)

ただし、OR および XOR 関数のコストは約 30 分です (はい、その関数を呼び出すだけです)。

結果は正しいですが、時間がかかるのはひどいです

誰かがこの問題に遭遇しましたか？

Answer 1

説明されている動作を示すコードを投稿することは常に役立ちますが、i = 1..n ポリゴンのそれぞれには、前の 1..(i-1) ポリゴンのそれぞれとの (固有の) 交差があると想定しています。最初の n-1 ポリゴンを XOR した結果のポイント数は n の 2 次であることを意味するため、O(#Points * log(#Points)) の演算を n 回要求していることになります。ここで、#Points は O(n ^2)、したがって、合計の複雑さは O(n^2*log(n)) になります。