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

Please see the example image:



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