# Detect triangles within triangulation in 3D

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?

• If you are in 3D, can't you change the coordinates and the the plane of the figure to become the $x-y$ plane ? – G Cab Mar 26 '18 at 18:07
• @GCab yes i could do the change of basis vectors. But is there a way to detect the areas with out a sweepline? – Marko Taht Mar 26 '18 at 18:13
• In your third pic, one of the red regions is a quad, not a triangle. – John Hughes Mar 26 '18 at 19:52
• When you say "given the knowledge of the edges, ...", can you say in what form we "know" them? Are we given the three (or more) black polylines as an ordered list, where each edge shares a vertex with the previous edge, etc.? Are these lists oriented (i.e., is the outer black cycle oriented clockwise, while the inner hexagon is oriented counterclockwise, and the inner triangle is oriented...in some direction? And are we given a list of all mesh triangles as unordered triples of vertices? – John Hughes Mar 26 '18 at 19:55
• Triangles are given as separate structures that have 3 vertices and 3 edges. Edges re shared between triangles, so i can ask for neighbors of a triangle. – Marko Taht Mar 27 '18 at 6:23

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.

• This tests if the point is within the triangle. But how would you use it to determine if the triangle is within a polygon? – Marko Taht Mar 27 '18 at 6:28
• @MarkoTaht: I added a 2nd part to my answer. But it is possible that I did not catch clearly which is your problem. – G Cab Mar 27 '18 at 13:25
• I think i kinda understand where you are trying to go with this. But to clearify. My goal is to remove the colored triangles from the overall triangulation. – Marko Taht Mar 27 '18 at 17:10

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.

• uuh.. i like this. im gona try this. THe color i think can actually be determinedrather easily, if the triangle is connected to the outer perimeter(marked edge) but on the other side there is no triangle. That should mean that this triangle must remain. Using that i think this approach can work rather well :). If this works il mark this as an asnwer. – Marko Taht Mar 28 '18 at 7:08