Всегда ли код пересечения полигонов в CGAL использует библиотеку рациональных чисел GMP?

В настоящее время я работаю над определением, пересекаются ли два многоугольника друг с другом. Я нашел пример на веб-странице документации CGAL: http://doc.cgal.org/latest/Boolean_set_operations_2/Boolean_set_operations_2_2do_intersect_8cpp-example.html

Однако этот код использует библиотеку рациональных чисел GMP, поэтому он относительно медленный. В моей задаче мне нужно определить пересечение многоугольников тысячи раз. Поэтому мне интересно, есть ли альтернатива, которая использует только арифметику с плавающей запятой, чтобы она могла работать намного быстрее? Большое спасибо.


cgal computational-geometry gmp polygons
person Hanyu Ye    schedule 22.02.2017    source источник
comment
Я не знаю конкретно этот пакет, но большинство операций с участием Epeck ленивы, т.е. они сначала выполняются с интервалом в два раза, и обращаются к GMP только в тех немногих местах, где это необходимо. Это, безусловно, медленнее, чем что-то на основе Epik, но не так медленно, как выполнение всех вычислений напрямую с рациональными числами (Simple_cartesian‹Gmpq›).   -  person Marc Glisse    schedule 22.02.2017

Ответы (1)


arrow_upward
0
arrow_downward

CGAL заявляет: «CGAL сочетает арифметику с плавающей запятой с точной арифметикой, чтобы быть эффективным и надежным. CGAL имеет для этого встроенный числовой тип, но Gmp и Mpfr обеспечивают более быстрое решение, и мы рекомендуем использовать их». (1) По моему опыту, именно для этого и предназначен CGAL, точное вычисление.

Если вы используете CGAL, потому что он напрямую предоставляет функции пересечения полигонов, возможно, вам подойдет альтернативная библиотека. Вот некоторые из альтернативного потока.

Одна последняя мысль. Вы также можете ускорить свой код в CGAL. В вашем случае я бы предложил вычислить ограничивающую рамку для каждого многоугольника и сначала выполнить тесты пересечения с ними. Это уже устранит множество пар полигонов.

person gue    schedule 23.02.2017
comment
Хорошая идея! Большое спасибо. - person Hanyu Ye; 23.02.2017