4
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ It is more incorrect than "brute forcy". $\endgroup$
    – user16034
    Aug 12, 2023 at 9:02
  • 1
    $\begingroup$ @YvesDaoust How is it incorrect? Given that I am given a constrained triangulation, the edges in the triangulation are either fully inside or fully outside the polygon. Testing the midpoint is 100% correct. If any point is inside then the entire edge is inside. $\endgroup$
    – Makogan
    Aug 13, 2023 at 0:00
  • 1
    $\begingroup$ It is not clear from the question that the segments are either wholly in or wholly out. If this is the case, why taking the midpoint rather than one of the endpoints ? And what is the problem then, point-in-polygon is old as the world. $\endgroup$
    – user16034
    Aug 13, 2023 at 14:21
  • $\begingroup$ @YvesDaoust I explicitly said I am working on the segments of a constrained triangulation, if you look at any constrained triangulation that has a closed polygon as the constraint no edge will cross the polygon, by construction of the triangulation. You use the midpoint because the endpoints may lie right at the boundary, this would lead to potential numerical imprecision, the midpoint is guaranteed to lie in the interior so it will perform much better. $\endgroup$
    – Makogan
    Aug 13, 2023 at 18:21
  • $\begingroup$ Sorry to have disturbed. $\endgroup$
    – user16034
    Aug 13, 2023 at 19:31

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.