Polygon inside polygon inside polygon

Question

I have number of simple polygons which do not intersect each other but some polygons may be embedded into others.

For example:

+--------------------------------------------+
|                                            |
|   +----------------+          +--------+   |
|   |                |         /         |   |
|   |   +--------+   |        /          |   |
|   |   |        |   |       /  +----(2)-+   |
|   |   |        |   |      /   |            |
|   |   +----(3)-+   |     /    |   +---+    |
|   |                |    +-----+   |   |    |
|   +------------(2)-+              +(2)+    |
|                                            |
+----------------------------------------(1)-+

How to find out the "depth" of all the polygons? In other words, how to find out by how many polygons a polygon is encompassed by? The "depth" are the numbers in parentheses.

I could count how many times a point of a polygon is inside of all the other polygons but this has quadratic complexity. How to compute those depths faster?

Answer 1

Put your polygons into some kind of spatial lookup structure, for example an R-tree based on the minimum bounding rectangles for the polygons. Then you should be able to compute the containment relation that you're after in O(n log n). (Unless you're in a pathological case where many of the minimum bounding rectangles for your polygons overlap, which seems unlikely based on your description.)

Edited to add: of course, you don't rely on the R-tree to tell you if one polygon is inside another (it's based on minimum bounding rectangles so it can only give you an approximation). You use the R-tree to cheaply identify candidate inclusions which you then verify in the expensive way (checking that a point in one polygon is inside the other).