Boost polygon library Время вычисления булевой функции
Кто-нибудь использовал булеву функцию библиотеки полигонов Boost?
Увеличить библиотеку полигонов
Это говорит о том, что алгоритм O (nlogn) во временной сложности, n = # точек
Я ввел 200000 случайно сгенерированных полигонов (с 5 ~ 8 потинами)
но функция OR и XOR стоит около получаса (да, просто вызовите ее функцию)
хотя результат правильный, но отнимает много времени
кто-нибудь встречал эту проблему?
Решение
Хотя это всегда поможет опубликовать код, который демонстрирует описанное поведение, я предполагаю, что каждый из многоугольников i = 1..n имеет некоторые (уникальные) пересечения с каждым из предыдущих многоугольников 1 .. (i-1), что подразумевает, что число точек, которые получаются в результате выполнения XOR первых n-1 полигонов, является квадратичным по n, поэтому вы запрашиваете n раз операцию O (#Points * log (#Points)), где #Points равно O (n ^ 2), таким образом, общая сложность будет O (n ^ 2 * log (n)).
Другие решения
Других решений пока нет …