How to find polygons overlap reign

Question

I have an algorithmic problem.

I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (x and y coordinates) and may contain up to N different vertices.

Assuming I have a set of N polygons, then for a new polygon k, how do I determine whether or not k overlaps with each one of the N polynomials in the set AND what is the overlapping reign percentage?

This is a purely algorithmic question but I plan on writing the algorithm in parallel using the CUDA platform, therefore any highly parallel solution would be preferred.

Answer 1

Building on top of polygon intersection, a naive process would just intersect each polygon with every other polygon and using the area of the polygons and the area of the intersection could compute what you call the overlapping reign percentage. This is easily parallel, and one could use a simple bounding box intersection to avoid computing the polygon intersect when the polygons's bounding boxes don't overlap.