0

I am currently working on determining whether two polygons intersect with each other. I have found an example in CGAL's documentation webpage: http://doc.cgal.org/latest/Boolean_set_operations_2/Boolean_set_operations_2_2do_intersect_8cpp-example.html

However, this code employs GMP's rational number library hence it is relatively slow. In my problem, I need to determine intersection of polygons for thousands of times. Therefore, I wonder whether there is an alternative which only use the floating-point arithmetic so that it can run much faster? Thanks a lot.

Hanyu Ye
  • 21
  • 2
  • 1
    I don't know this package in particular, but most operations involving Epeck are lazy, i.e. they are first done with intervals of double, and only turn to GMP in the few places where that is needed. It is certainly slower than something Epick-based, but not as slow as doing all computations directly with rationals (Simple_cartesian). – Marc Glisse Feb 22 '17 at 18:56

1 Answers1

0

CGAL states: "CGAL combines floating point arithmetic with exact arithmetic, in order to be efficient and reliable. CGAL has a built-in number type for that, but Gmp and Mpfr provide a faster solution, and we recommend to use them." (1) Also in my experience that is what CGAL is for, exact computation.

If you use CGAL because it supplies the polygon intersection features directly, maybe an alternative library would be a possibility. Here are some from an alternative thread.

One final thought. You can also speed up your code within CGAL. In your case I would suggest computing the bounding box for every polygon and first do a intersection tests with those. It will already eliminate a lot of polygon pairs.

Community
  • 1
  • 1
gue
  • 1,868
  • 1
  • 16
  • 21