Locating a point inside a union of simple polygons

I have a set of polygons (convex, concave – non-convex, not self-intersecting) in a plane. There may be intersections between polygons.

Polygon is defined by points (cartesian coordinate system).

There is 2 polygons: the first is { A, B, C, D } and the second is { E, F, G }.

Question

How can I detect bounding "face" by the given point?

• Solution for point 1 is { A, B, the intersection between |BD| and |EF|, F, the intersection between |FG| and |DC|, C, A }.

My idea

• I tried some alghoritmus for boolean operations on polygons, but I think that this is not the right approach.
• I can insert intersection points into original polygons and subdivided the original edge. After that, there is no intersection between polygon's edges.
• Can I use some graph theory algorithm or algorithm for space partitioning?
• Suppose my point was at the midpoint of the (imaginary) line connecting B and E (i.e outside the two polygons). what answer do you desire then ? – Suresh Venkat Apr 7 '14 at 21:22
• @SureshVenkat For this situation I desire that algorithm return something like null. – user3102393 Apr 7 '14 at 21:29
• I see. so you want to do point location inside the union of the polygons then ? – Suresh Venkat Apr 7 '14 at 22:03
• Please clarify what you mean by "concave" polygons. – Yoshio Okamoto Apr 7 '14 at 22:53
• @YoshioOkamoto I mean non-convex. By the en.wikipedia.org/wiki/Convex_and_concave_polygons. – user3102393 Apr 8 '14 at 5:48

You can consider every polygon one by one. You should update the answer after adding each polygon. For every polygon, first consider whether the polygon enclose the point. If yes, consider the every edge. Finding the edges going into the current minimum polygon (your current answer) and going outside. Then you can find all intersection and edges which generates your new answer. Iterate this procedure you can finally get the final answer

• first consider whether the polygon enclose the point What about the example with query point 1? The first polygon { A, B, C, D } encloses the query point 1. The second polygon doesn't enclose the query point 1, but some edges from the second polygon is boundery of face for query point 1. I like the idea of adding polygon one by one and finding the edges going into. – user3102393 Apr 9 '14 at 9:18

I didn't read the last few comments: this approach only makes sense for a fixed set of polygons and many different query points.

I haven't thought this through in detail, but something like the following might work:

1. Construct the trapezoidal decomposition of the arrangement of all line segments in the input (i.e ignoring which polygon each line segment comes from). There are standard algorithms for doing this.

2. Run a connected components algorithm over a graph induced by the resulting subdivision: each vertex is a cell of the subdivision and two vertices are connected by an edge if the corresponding cells intersect at an edge of the trapezoidal decomposition that is NOT part of the input. For each component, write down the canonical answer you desire.

3. Build a point location data structure over the subdivision.

When a query comes in, locate the subdivision cell using (3) and then output its descriptor using (2).

One solution is to build from the input polygons, a set of empty polygons (by 'empty' I mean there are no edges going through them) so that every 'face' of your shape has its own associated polygon. e.g. in your example we would create 4 polygons: the polygon containing (1), the polygon containing (2), the triangle with vertices G, intersection(EG, BD), intersection(FG, CD), and the triangle with vertices E, intersection(EF, BD), intersection(EG, BD).

If your input consists of many input polygons, an exponential number of these empty polygons will be generated. You can generate them by first finding all intersections between pairs of lines. Then for each vertex, for each outgoing edge of that vertex, if that (vertex, edge) pair is not yet seen, mark the (vertex, edge) pair as seen, walk from the vertex along the edge, and take the leftmost edge each time you encounter an intersection, and repeat for this (vertex, edge) pair. Stop when you reach the initial vertex again.

Now every point will be contained within at most one empty polygon. To determine which one, loop through all empty polygons and use a standard point-in-polygon test.

• an exponential number — No. If the polygons have $n$ edges in total, their arrangement will have at most $O(n^2)$ faces. – Jeffε Apr 8 '14 at 11:58