<p>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</p>

CC BY-SA 3.0
2014-04-09T09:18:25.207Z
_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
CC BY-SA 3.0
2014-04-08T11:17:37.557Z
2014-04-08T11:17:37.557Z
THULeiZhixian
<p><em>I didn't read the last few comments: this approach only makes sense for a fixed set of polygons and many different query points.</em></p>

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

<ol>
<li><p>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. </p></li>
<li><p>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. </p></li>
<li><p>Build a point location data structure over the subdivision. </p></li>
</ol>

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

CC BY-SA 3.0
2014-04-08T17:55:52.147Z
2014-04-08T23:43:58.717Z
2014-04-08T23:43:58.717Z
Suresh Venkat
<p>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).</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-08T11:58:42.053Z
_an exponential number_ — No. If the polygons have $n$ edges in total, their arrangement will have at most $O(n^2)$ faces.
Jeffε
CC BY-SA 3.0
2014-04-08T11:37:06.687Z
2014-04-08T11:37:06.687Z
D G
<p>I have <strong>a set of polygons</strong> (convex, concave – non-convex, <strong>not</strong> self-intersecting) in a plane. There may be intersections between polygons.</p>

<p>Polygon is defined by points (cartesian coordinate system).</p>

<p>Please see the example image:</p>

<p><img src="https://i.sstatic.net/apypM.png" alt="enter image description here"></p>

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

<p><strong>Question</strong></p>

<p>How can I detect bounding "face" by the given point?</p>

<ul>
<li>Solution for point 1 is { A, B, the intersection between |BD| and |EF|, F, the intersection between |FG| and |DC|, C, A }.</li>
</ul>

<p><strong>My idea</strong></p>

<ul>
<li>I tried some alghoritmus for boolean operations on polygons, but I think that this is not the right approach.</li>
<li>I can insert intersection points into original polygons and subdivided the original edge. After that, there is no intersection between polygon's edges.</li>
<li>Can I use some graph theory algorithm or algorithm for space partitioning?</li>
</ul>

CC BY-SA 3.0
2014-04-07T21:22:18.730Z
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
CC BY-SA 3.0
2014-04-07T21:29:34.823Z
@SureshVenkat For this situation I desire that algorithm return something like null.
user3102393
CC BY-SA 3.0
2014-04-07T22:03:39.640Z
I see. so you want to do point location inside the union of the polygons then ?
Suresh Venkat
CC BY-SA 3.0
2014-04-07T22:53:20.350Z
Please clarify what you mean by "concave" polygons.
Yoshio Okamoto
CC BY-SA 3.0
2014-04-08T05:48:12.607Z
@YoshioOkamoto I mean non-convex. By the http://en.wikipedia.org/wiki/Convex_and_concave_polygons.
user3102393
CC BY-SA 3.0
2014-04-08T05:48:51.113Z
@SureshVenkat Yes.
user3102393
CC BY-SA 3.0
2014-04-08T11:56:29.050Z
Do you want to query the same set of polygons with several different points, or do you just want to consider one point and one set of polygons?
Jeffε
CC BY-SA 3.0
2014-04-08T12:47:36.657Z
@JɛﬀE One point and one set of polygons in most cases. The set of polygons is variable.
user3102393
CC BY-SA 3.0
2014-04-09T09:11:05.253Z
@JɛﬀE But query point may be in face between polygons. Like the example point 1.
user3102393
<computational-geometry>
Locating a point inside a union of simple polygons
user3102393
# Locating a point inside a union of simple polygons

(Asked by: username_0 on 2014-04-07)

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:

![enter image description here](https://i.sstatic.net/apypM.png)

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?

**Tags:** computational-geometry

> **Comments:**
> **username_1**: 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 ?  
> **username_0**: @SureshVenkat For this situation I desire that algorithm return something like null.  
> **username_1**: I see. so you want to do point location inside the union of the polygons then ?  
> **username_2**: Please clarify what you mean by "concave" polygons.  
> **username_0**: @YoshioOkamoto I mean non-convex. By the http://en.wikipedia.org/wiki/Convex_and_concave_polygons.  
> **username_0**: @SureshVenkat Yes.  
> **username_3**: Do you want to query the same set of polygons with several different points, or do you just want to consider one point and one set of polygons?  
> **username_0**: @JɛﬀE One point and one set of polygons in most cases. The set of polygons is variable.  
> **username_0**: @JɛﬀE But query point may be in face between polygons. Like the example point 1.  

---

## 3 answers

### Answer by username_4 on 2014-04-08. Score: 2

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

> **Comments:**
> **username_0**: _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.  

---

### Answer by username_1 on 2014-04-08. Score: 2

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


---

### Answer by username_5 on 2014-04-08. Score: 0

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.

> **Comments:**
> **username_3**: _an exponential number_ — No. If the polygons have $n$ edges in total, their arrangement will have at most $O(n^2)$ faces.  

---

