Boost polygon library Время вычисления булевой функции

Кто-нибудь использовал булеву функцию библиотеки полигонов Boost?
Увеличить библиотеку полигонов

Это говорит о том, что алгоритм O (nlogn) во временной сложности, n = # точек

Я ввел 200000 случайно сгенерированных полигонов (с 5 ~ 8 потинами)

но функция OR и XOR стоит около получаса (да, просто вызовите ее функцию)

хотя результат правильный, но отнимает много времени

кто-нибудь встречал эту проблему?

2

Решение

Хотя это всегда поможет опубликовать код, который демонстрирует описанное поведение, я предполагаю, что каждый из многоугольников i = 1..n имеет некоторые (уникальные) пересечения с каждым из предыдущих многоугольников 1 .. (i-1), что подразумевает, что число точек, которые получаются в результате выполнения XOR первых n-1 полигонов, является квадратичным по n, поэтому вы запрашиваете n раз операцию O (#Points * log (#Points)), где #Points равно O (n ^ 2), таким образом, общая сложность будет O (n ^ 2 * log (n)).

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]