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

Question

有人用过Boost多边形库的布尔函数吗？ 增强多边形库

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

我输入了 200000 个随机生成的多边形（有 5~8 个点）

但是 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))。