Detect triangles within triangulation in 3D

Question

I have a triangulated polygon(lies approximately on a single plane). I know the vertices and the edges(polygon edges not the triangulation edges), but i dont know the exact order of them(but it probably can be found).

Inside the polygon additional smaller polygons will be added and re-triangulated. I need a way to detect the colored triangles.

I made an error here, the red areas are segmented into quads, but they are supposed to be segmented into triangles.

I know that one solution would be to do a sweepline across the triangulation and then use the edges to see if its inside or outside. But is there any easier methods? Since the polygons are in 3D space its hard to do a sweepline.

This is the polygonal area that is know to me. And the colored area needs to be found.

So given the knowledge of the edges(in no particular order), vertices and vertices that make up the inner added polygonal shapes, like in the last image, is there a way to detect what triangles are within the added polygons?

Answer 1

In $n-$D a point $P$ is internal to a segment $AB$ iff $$ P = t\,A + s\,B\quad \left| {\;\left\{ \matrix{ \;0 \le t,s \le 1 \hfill \cr \;t + s = 1 \hfill \cr} \right.} \right. $$

in $n-$D a point $P$ is internal to a triangle $ABC$ iff $$ P = t\,A + s\,B + r\,C\quad \left| {\;\left\{ \matrix{ \;0 \le t,s,r \le 1 \hfill \cr \;t + s + r = 1 \hfill \cr} \right.} \right. $$ i.e. if it is the weighted average of the vertices of the triangle, with the weights non-negative and summing to $1$.

IIn $2-$D we can write the above in matrix notation as $$ P = \left( {\matrix{ x \cr y \cr } } \right) = \left( {\matrix{ {x_{\,a} } & {x_{\,b} } & {x_{\,c} } \cr {y_{\,a} } & {y_{\,b} } & {y_{\,c} } \cr } } \right)\left( {\matrix{ t \cr s \cr r \cr } } \right) $$ and using the fact that $r+s+t=1$ we can rewrite the above using a square matrix $$ \left( {\matrix{ x \cr y \cr 1 \cr } } \right) = \left( {\matrix{ {x_{\,a} } & {x_{\,b} } & {x_{\,c} } \cr {y_{\,a} } & {y_{\,b} } & {y_{\,c} } \cr 1 & 1 & 1 \cr } } \right)\left( {\matrix{ t \cr s \cr r \cr } } \right)\quad \Rightarrow \quad \left( {\matrix{ t \cr s \cr r \cr } } \right) = \left( {\matrix{ {x_{\,a} } & {x_{\,b} } & {x_{\,c} } \cr {y_{\,a} } & {y_{\,b} } & {y_{\,c} } \cr 1 & 1 & 1 \cr } } \right)^{\, - \,1} \left( {\matrix{ x \cr y \cr 1 \cr } } \right) $$

We recognize in the above that it implies the use of homogeneous coordinates, and that the determinant of the matrix equals the area of the triangle, and therefore it is non-null and the matrix is invertible, unless the triangle is degenerated.

We are employing a Barycentric system.

So, to check if a point is internal to $\triangle {ABC}$, we multiply its homogeneous coordinates by the inverted matrix as above and verify that the resulting vector of parameters have non-negative components.

Concerning the arrangement of the points that you have into a polygon, let's consider first three points $A, B, C$ out of which we construct a triangle as per above. Then let's take a fourth point $P$.

With the above method we can determine if $P$ is external or internal to $\triangle {ABC}$. If it is external, one or two of its barycentric coordinates are negative.

When only one of them is negative, $s$ in the example shown in the drawing, then we know that $P$ is opposite to $B$ wrt $AC$ and we can (supposedly) add the triangle $\triangle {PAC}$.

But, if two coordinates are negative, then we have a double choice as for the triangle to add. Suppose e.g. that also $t$ be negative and $P=(10,3)$ in the $x-y$ reference. Then the possible additional triangles would be $\triangle {PBC}$ and $\triangle {PAC}$, and it is as well possible that $\triangle {ABC}$ be actually excluded.

Then, when $P$ is internal to $\triangle {ABC}$, the choice is triple.

In case of multiple choices, we cannot decide unless we have additional information.
If I understood properly, you have the list of the edgeswhich are part or not of the polygon to build. Then the choices become obvious, except for the case of a triangular hole in the polygon.
In this last case I do not know what additional information you have, that might help to decide whether the triangle is internal to the polygon or is to be excluded.

Answer 2

Here's a strategy using just a little bit of graph theory.

TL;DR: from the dual graph of the triangulation, delete all edges corresponding to the "(boundary) edges of the inner polygonal shapes"; then compute connected components.

Details:

Step 1: Build a graph structure, $G$, with one vertex for each triangle of your triangulation, and an edge between $v_1$ and $v_2$ exactly when the corresponding triangles share an edge. Thus if the vertex $v_1$ corresponds to triangle $(1, 4, 5)$ and $v_2$ corresponds to triangle $(4, 7, 5)$, then we include an edge between $v_1$ and $v_2$ in the graph $G$.

(Intuitively: put a dot in the middle of each triangle in your triangulation; draw an edge between corresponding dots if the triangles share an edge.)

Step 2: when the edge between two triangles is one of your boldface black edges (a divider between red and white, one of the things you described as "edges, vertices, and vertices that make up the inner polygonal shapes", or more intuitively, "the edges that you drew in your last picture"), mark the corresponding edge in $G$. Each edge of $G$ is now either marked or unmarked.

Step 3: starting at any node of G, perform a depth-first traversal, attaching a boolean label to each vertex you encounter.

a. Label the first vertex "t" (for "true").

b. As you traverse edges, if the edge you traverse is unmarked, use the same label for the newly-encountered vertex as for the one from which you're traversing; if the edge you traverse is marked, and the starting vertex has label $b$, then label the new vertex with "not $b$".

When you're done, all the vertices with one boolean label will correspond to triangles in the original mesh with one color; all those with the other label will correspond to triangles in the original mesh with the other color.

Which one is which? Who knows!? If your input mesh consisted of a single triangle, there's no way to know whether it should be white or red, from the data you've given us. So I leave that final determination -- the color of one particular triangle -- to you.

Just to make that last claim clear, I'm going to start with your last example, and make step by step edits that don't alter the nature of the problem in any essential way, and arrive at a situation where the solution is self-evidently ambiguous:

The upper left is a region with two interior regions, very similar to your final example; I simplify by removing one of them; I simplify again by removing an inner region from the other. Then (upper right) I move some of the vertices on the bottom edge, and insert a bottom vertex. Then I continue simply moving vertices until several line up, and delete those. I arrive at a mesh consisting of two triangles, with the edge between them being one where we change from white to red. But the same input could correspond to the opposite coloring, where the bottom triangle is red and the upper is white, by symmetry. That's why my algorithm can't tell you which is which: your data doesn't contain that information. But I can tell you all the triangles in the same color group.