c++ - Boost多边形库 bool 函数计算时间

Question

有人用过Boost多边形库的 bool 函数吗？ Boost polygon library

它说算法的时间复杂度是O(nlogn)，n = #points

我输入了 200000 个随机生成的多边形(有 5~8 个 potins)

但是 OR 和 XOR 函数花费了大约半个小时(是的，只是调用它的函数)

虽然结果是正确的，但是耗时太惨了

有人遇到过这个问题吗？

Answer 1

尽管发布展示所描述行为的代码总是有帮助的，但我假设每个 i=1..n 多边形与之前的每个 1..(i-1) 都有一些(唯一的)交叉点多边形，这意味着由第一个 n-1 多边形异或得到的点数是 n 的二次方，因此您请求 n 次 O(#Points * log(#Points)) 的操作，其中 #Points 是O(n^2)，因此总复杂度为 O(n^2*log(n))。