Triangle within concave polygon.

Question

I have a situation something like this:

The polygon has been triangulated (Delaunay triangulation). All the vertices are on the black lines. I need to find all the triangles that make up the red area. Is there a way to do it? I know the vertices of the black lines and the edges of the black lines, but i dont have the order.

How can i find the triangles within the red area?

Answer 1

Assuming you care about a reasonably efficient algortithm, here goes:

Each triangle of the triangulation has one edge on one of the two arcs. And the two vertices of that edge are adjacent. So an algorithm looks like this:

for each arc (the outer and the inner)
  for each vertex v
     let w = the vertex after v
        if neighbors(v) and neighbors(w) are disjoint sets
           move to next vertex v
        else
           let q be the sole element of both neighbors(v) and neighbors(w)
           output (v, w, q)

You need to see why the intersection of the two "neighbors" sets can have at most one vertex --- I leave that to you --- and you need to find a way to detect intersections of two sets quickly; I suggest hashing.

BTW, "neighbors($v$)" means the set of vertices $u$ such that there's an edge from $u$ to $v$. In particular, $v$ is NOT in neighbors($v$).

The algorithm also assumes that you've got the two boundary cycles, which I've called "arcs", given as ordered lists of vertices. If not, you need to assemble those before you start.