patternMinor
Detecting if an edge is "inside" a polygon?
Viewed 0 times
polygondetectingedgeinside
Problem
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.
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.
Solution
If you already have a constrained triangulation, to test if it contains the line segment $(a,b)$, You can do the following:
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.
- Find the triangle $(p,q,r)$ that contains $a$. If it does not exist, return false
- If $(p,q,r)$ contains b, return $true$
- Find the edge $(s,t) \in \left\{(p,q), (q,r), (r,p)\right\}$ which intersects $(a,b)$
- If a neighboring triangle $(t,s,u)$ does not exist return $false$
- 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.
Context
StackExchange Computer Science Q#161563, answer score: 4
Revisions (0)
No revisions yet.