CGAL users discussion list

[Andreas Fabri <>]

Roger House wrote:
> I have an application in which I need to find the pairwise intersection 
> of hundreds, sometimes thousands, of polygons.  The obvious approach is 
> quadratic in the number of polygons, and I am hoping there are much more 
> efficient ways to do it.  Any information on algorithms for fast 
> pairwise intersection of polygons will be greatly appreciated.
>
> Roger House

Hi Roger,

What exactly do you want to compute: the intersection points,  the Boolean AND
of the area of pairs, just identifiers of pairs of polygons that do 
intersect,....

How are the polygons, or better how are the bounding boxes of them?
Do they traverse the entire domain,  are it nested spirals so that they
all have almost the same bounding box, or are it rather small bounding
boxes scattered over the domain.

A picture of a typical scenario might help us to help you.

best regards,

andreas