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

Question

有没有人用过Boost多边形库的布尔函数?Boost多边形库

表示算法的时间复杂度为O(nlogn)， n = #points

输入20万个随机生成的多边形(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))。