Partitioning a set of 2d polygons into intersection-connected subsets

Question

My question is given a set of 2d polygons how can I find the connected components of polygons according to a criteria based on intersection or proximity of them.

In other words I have a set of polygons. I want to group them into subsets where each polygon has at least one intersection with (one or more) other polygon(s) of the subset and no intersections with any other polygon in a different subset. So if I have S = {A, B, C, D} and A intersects C and C intersects D the resulting partitions are: P1 = {A, C, D} and P2 = {B}.

I don't have any problems with an good approximate solution if its fast and doesn't generate false negatives (i.e. no (potential) intersection is lost).

I don't need to actually calculate the intersections just determine if they intersect.

In my case the polygons are complex but if a known answer only works for concave or simple polygons I would still like to know about it!

I am actually not sure how to phrase this question which may account for my lack of findings of relevant papers.

Answer 1

What you want is to find the connected components of the intersection graph of the polygons, right? It would help to be more clear about what counts as an intersection: do the boundaries have to cross or does one polygon entirely inside another count as an intersection? And can the polygons have holes?

Regardless, a natural lower bound for running times for the problem is $\Omega(n^{4/3})$ where $n$ is the total number of segments in the input. Any faster and we could also improve the known time bounds for Hopcroft's problem of detecting an intersection between $n$ given points and $n$ given lines: expand each point into a small polygon (not so large that it intersects any line it didn't before) and test whether any of these expanded points belongs to a nontrivial connected component. This lower bound is mentioned briefly in my paper "Testing Bipartiteness of Geometric Intersection Graphs" which uses it to argue that bipartiteness of intersection graphs is strictly easier than connectivity; it in turn cites Jeff Erickson's paper "New lower bounds for Hopcroft’s problem", which proves an $\Omega(n^{4/3})$ lower bound in a reasonable but limited model of computation.

Answer 2

Make an undirected graph where each vertex corresponds to a polygon and link any pair of vertices if their corresponding polygons overlap. Then run whatever connected component labeling algorithm you like on the result.

Answer 3

To expand on Mikola's answer, you could modify a sweep-line algorithm like the Bentley-Ottman algorithm (http://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm) to detect the crossings, and maintain an auxiliary graph structure where each polygon is represented by a vertex. Mark each line segment with its polygon's representative graph vertex. Each time you detect a crossing between two line segments from different polygons, add an edge between the corresponding vertices of the auxiliary graph (if one does not already exist). In the end, the connected components of the auxiliary graph will give you exactly what you want.