Detecting if an edge is "inside" a polygon?

Question

I have computed a constrained triangulation of a set of points. The constraint happens to be a closed polygon.

The objective is to detect all edges which are inside the polygon, that is, an edge where both endpoints are points in the polygon and for which all interior points are inside the area of the polygon.

A hacky way to do it is to compute the winding number for the midpoint of the edge and test if it is inside the polygon. But this is very brute forcy. I am wondering if there is a better way.

Answer 1

To find all the edges inside a polygonal constraint inside of a larger constrained triangulation, You can do the following:

1. Find a single triangle inside the polygonal constraint
2. Use flood fill to find all triangles inside the polygonal constraint
3. Put all edges of these triangles into a set
4. Remove the polygonal constraint edges from the set

Finding the First Triangle

To find the first triangle inside of the polygonal constraint, You could simply take one edge of the polygon $(a,b)$ and find the triangle $(a,b,c)$, provided the polygonal constraint has the same orientation as the triangles.

Answer 2

If you already have a constrained triangulation, to test if it contains the line segment $(a,b)$, You can do the following:

1. Find the triangle $(p,q,r)$ that contains $a$. If it does not exist, return false
2. If $(p,q,r)$ contains b, return $true$
3. Find the edge $(s,t) \in \left\{(p,q), (q,r), (r,p)\right\}$ which intersects $(a,b)$
4. If a neighboring triangle $(t,s,u)$ does not exist return $false$
5. Set $(p,q,r) \leftarrow (t,s,u)$ and go to 2.

Step 4. basically tests if an edge exits a border.

Finding The Triangle

In order to find the triangle that contains $a$ You could build some BVH with all the triangles and in $\mathcal{O}(n*\log(n))$ and find a triangle in $\mathcal{O}(\log(n))$. But that may not be as fast in practice as in theory.

Another way is to start at some triangle and then walk along the mesh towards $a$ using the A* algorithm. If You sort the tested edges according to some space-filling curve order, and You always start with the triangle You've last looked at, You may even find the next triangle in amortized $O(1)$ time in practice.