<p>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?</p>

<p>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 "<a href="http://arxiv.org/abs/cs.CG/0307023" rel="nofollow">Testing Bipartiteness of Geometric Intersection Graphs</a>" which uses it to argue that bipartiteness of intersection graphs is strictly easier than connectivity; it in turn cites Jeff Erickson's paper "<a href="http://compgeom.cs.uiuc.edu/~jeffe/pubs/hopcroft.html" rel="nofollow">New lower bounds for Hopcroft’s problem</a>", which proves an $\Omega(n^{4/3})$ lower bound in a reasonable but limited model of computation.</p>

CC BY-SA 3.0
2014-01-17T14:53:19.667Z
By intersection I would include a polygon inside of a polygon as an intersection. So in essence if they share at least one point in their interior or there boundaries cross its an intersection.
Juan Besa
CC BY-SA 3.0
2014-01-17T14:57:48.580Z
What about convex polygons? I bad approximation would be to use the convex hull of each polygon and obtaining that intersection graph of them. I am sure it can be done using just the bounding boxes as an even coarser approximation.
Juan Besa
CC BY-SA 3.0
2014-01-17T17:05:31.543Z
This lower bound applies directly to convex polygons: each line is convex by itself, and each point (or each small expansion of the point) is also convex.
David Eppstein
CC BY-SA 3.0
2014-01-16T04:06:29.193Z
2014-01-16T04:06:29.193Z
David Eppstein
<p>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.</p>

CC BY-SA 3.0
2014-01-15T18:48:25.977Z
2014-01-15T18:48:25.977Z
Mikola
<p>To expand on Mikola's answer, you could modify a sweep-line algorithm like the Bentley-Ottman algorithm (<a href="http://en.wikipedia.org/wiki/Bentley" rel="nofollow">http://en.wikipedia.org/wiki/Bentley</a>–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.</p>

CC BY-SA 3.0
2014-01-17T15:00:11.623Z
The problem with this approach is contained in Mr. Eppsteins answer. If a polygon is completely contained inside another polygon then no actual intersection between boundaries occurs and you would not detect come intersections between polygons.
Juan Besa
CC BY-SA 3.0
2014-02-04T20:39:47.200Z
Ah, sorry Juan. I didn't read carefully enough! I was thinking only of boundary intersections, not interior intersections.
John
CC BY-SA 3.0
2014-01-16T17:35:13.543Z
2014-01-16T17:35:13.543Z
John
<p>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.</p>

<p>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}. </p>

<p>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).</p>

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

<p>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!   </p>

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

CC BY-SA 3.0
2014-01-14T21:12:55.043Z
In other words, you want to determine which polygons contribute to each component of the union.
Jeffε
CC BY-SA 3.0
2014-01-15T14:28:06.540Z
Yes that would be another way of putting it.
Juan Besa
CC BY-SA 3.0
2014-01-16T17:31:10.557Z
Are you looking for the complexity of the problem, or an actual algorithm to implement?
John
CC BY-SA 3.0
2014-01-22T13:05:26.277Z
I am looking for an algorithm to actually implement. Of course knowing if there is actually any possibility of an algorithm also helps!
Juan Besa
<polygon><computational-geometry>
Partitioning a set of 2d polygons into intersection-connected subsets
Juan Besa
# Partitioning a set of 2d polygons into intersection-connected subsets

(Asked by: username_0 on 2014-01-14)

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.

**Tags:** polygon, computational-geometry
> **Comments:**
> **username_1**: In other words, you want to determine which polygons contribute to each component of the union.  
> **username_0**: Yes that would be another way of putting it.  
> **username_2**: Are you looking for the complexity of the problem, or an actual algorithm to implement?  
> **username_0**: I am looking for an algorithm to actually implement. Of course knowing if there is actually any possibility of an algorithm also helps!  

---

## 3 answers

### Answer by username_3 on 2014-01-16. Score: 3 | Accepted answer

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](http://arxiv.org/abs/cs.CG/0307023)" 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](http://compgeom.cs.uiuc.edu/~jeffe/pubs/hopcroft.html)", which proves an $\Omega(n^{4/3})$ lower bound in a reasonable but limited model of computation.

> **Comments:**
> **username_0**: By intersection I would include a polygon inside of a polygon as an intersection. So in essence if they share at least one point in their interior or there boundaries cross its an intersection.  
> **username_0**: What about convex polygons? I bad approximation would be to use the convex hull of each polygon and obtaining that intersection graph of them. I am sure it can be done using just the bounding boxes as an even coarser approximation.  
> **username_3**: This lower bound applies directly to convex polygons: each line is convex by itself, and each point (or each small expansion of the point) is also convex.  

---

### Answer by username_4 on 2014-01-15. Score: 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 by username_2 on 2014-01-16. Score: 2

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.

> **Comments:**
> **username_0**: The problem with this approach is contained in Mr. Eppsteins answer. If a polygon is completely contained inside another polygon then no actual intersection between boundaries occurs and you would not detect come intersections between polygons.  
> **username_2**: Ah, sorry Juan. I didn't read carefully enough! I was thinking only of boundary intersections, not interior intersections.  

---

