Please see the example image:

![enter image description here](https://i.stack.imgur.com/ARkZj.png)

There are a set of polygons (convex, non-convex, **but not** self-intersecting) in a plane. **Polygon is defined** by vertices – points (*x* and *y* coordinates, cartesian coordinate system).

*Example set of polygons:*

* The first polygon is A, B, C.
* The second polygon is D, E, F, G, H, I, J.
* The third polygon is K, L, M, N.
* The fourth polygon is O, P, Q.

Polygons divide a plane into regions. Some parts of polygons **may be overlapping** (like the first and the second polygon, the second polygon and the third polygon). This overlapping parts is seperate regions too. Some polygons **may be inside** others (like the fourth polygon inside the second polygon).

*Example regions after subdivision: blue, pink, green, orange, brown and purple.*

I imagine for simplicity that the plane is a rectangle with constant *x*, *y* coordinates.

**The Goal**

Detect the region (blue, pink, green, etc.) by the query point.

I am looking for algorithm and data structure for a plane subdivision with these assumptions.