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

Question

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

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

Answer 1

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

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

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