How to detect if an edge is inside a closed curve in a constrained triangulation?

Question

Assume one has a constrained Delaunay triangulation like in here:'

https://www.researchgate.net/figure/Results-of-three-steps-constrained-Delaunay-triangulation-in-a-simple-vague-region-a_fig8_225854833

I know exactly how to process a and get c.

But if you have a shape like C, how can you detect whether an edge/face is inside one of the close contours so that you can delete it?

Answer 1

Assuming your constrained curves are manifold and oriented: For each constrained edge, iterate through all edges sharing that edge's start vertex, starting from the next edge CCW of that edge, in CCW order. Delete all edges until you hit another constrained edge.

Answer 2

In other words, you want to understand whether this outline is a cave or not? In this case, you can use one of the filling rules: even-odd or non-zero.

1. If your paths don't intersect each other, then even-odd is your choice because it's a little easier to implement.

2. But if the paths can overlap each other, it is better to use a non-zero and make a winding rule for the main and caves. This case is the most complex, and before triangulation you will have to apply some poly-bool operation to your shape.

Let's take a better look at 1 case.

For each path, you can take the leftmost point (x, y) and count how many edges are under it. You must ignore vertical edges and edges which is ended with same x. If the score is odd, this path is a cave, otherwise it is the main path. Some technic like beam scanning can be used to improve performance.

If you paths implement winding rules. It also super easy to understand is it a cave or not. For example main will go in clock wise direction and caves in counter clock-wise direction. If so all leftmost corner for all caves will be in counter clock-wise direction you can check it with cross product of this edges/vectors. Other solution with implemented winding rule is calculate area of this path and look at it sign.

Filling rule can be found here: https://ishape-rust.github.io/iShape-js/overlay/filling_rules.html