A plane subdivision into non-overlapping regions by a set of polygons

Question

Please see the example image:

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.

Answer 1

First transform your set of polygons into a set of non-overlapping polygons by iteratively looking for pairwise intersections and replacing the pair of intersecting polygons with their intersection and the original polygons minus the intersection. This might be easier and faster if you first split each polygon into a set of convex polygons (the convex polygons can simply "inherit" the "color" of the original concave polygon).

You can then put the polygons into a quad-tree or a similar data structure which allows you to quickly select candidate polygons for membership tests for a given query point.

You will need to define what is happening on edges shared between multiple polygons.

Answer 2

I can recommend a trapezoidal decomposition http://en.wikipedia.org/wiki/Point_location#Trapezoidal_decomposition for efficient point queries in a planar subdivision.

In your case, the subdivision is defined indirectly so there is an extra step. You can try three approaches:

1) use a general polygon intersection algorithm that you will call incrementally,

2) form the trapezoidal decompositions of the polygons and perform fusions of these trapezoidal maps,

3) modify an existing trapezoidal decomposition algorithm so that it accepts as input a subdivision formed of overlapping polygons.

You will need to use some 2D Computational Geometry library... and courage.

ALTERNATIVE:

If your precision requirements are not too high, use a bitmap and fill every polygon, changing the color when pixels already painted are met.