I wrote an algorithm that iterates over the set of polygons with holes. The complexity of the algorithm n2. Algorithm checks intersection of each polygon with each of another polygons . Each object contains approximately from 100 to 1000 points. But I was terrified when processing of 50 objects tooks from 40 to 200 seconds. I also need to check to 100,000 objects. Is it real in CGAL?
Is there any speed up optimization techniques in CGAL?
For each polygon, first compute all the bounding boxes of the polygons. If you want to check intersections of polygons, the first thing to check is if the bounding boxes of the polygons do intersect. If they do not, then the polygons cannot intersect.
Then, to avoid the quadratic computation of all pair of potential intersection, I suggest you use the following CGAL package, to speed up the computation: Intersecting Sequences of dD Iso-oriented Boxes. That package provide a function that can fast report all pair of intersecting bounding boxes. Then, for each of those pair, you can then verify if the two polygon actually do intersect.