# How can I perform a triangle inside test in polygon meshes?

I have 3 vertices (V1, V2, V3) randomly selected on a regular triangle mesh. For these 3 vertices, I have computed the geodesic distance and the path (by using Dijkstra) among them and formed a triangle-like surface as in the above figure.

Now, I have the vertices that lie in each path and can compute geodesic distances from a given vertex.

What I want to do is to get the vertices or triangles that lies in triangle-like area. How can I do this?

• Assuming that barycentric approach does what I think it does it would be quite slow with large sets. Imagine a set of 9 million vertices with only 9 vertices in the desired set. Why iterate the entire set when v1, v2, and v3 give you all the information you need. The flood fill answer would be the fastest flexible solution. Although unflexible, if you can assume you have lines like you do now in the geometry then scanline would be the fastest approach. – Andrew Wilson Jul 19 '17 at 5:25
• You're absolutely right about performance issues. I'd like to use this approach in large meshes, so what I'm looking for is an efficient method. Actually I'm not familiar with neither flood filling nor scan fill algorithms, I'll take a look at them. Thanks. – mkocabas Jul 19 '17 at 5:52
• A flood fill with a graph would start at a node, visit every neighbor node if boundary condition is met and not visited, mark it as visited, and repeat (recursion). Alteration: mark every node on path as visited and start from a node inside the set. Then simply use the visitation check as the boundary condition. – Andrew Wilson Jul 19 '17 at 7:00
• Thanks for the detailed explanation. I find flood filling algo more reasonable, but I want to implement both flood fill and scan line, then compare the performances. – mkocabas Jul 19 '17 at 8:09

There is an alternative method that relies on flood filling. First arrange your edge data into a loop where the edges are forming a counterclockwise loop. Then start at an arbitrary point on the loop and pick edges joining that point. Use the outbound boundary edge and cross it with the other outbound edge, if it points in the direction of the face normal then it's an edge to be included, if not discard it. From this edge continue until you hit a boundary edge, at which point you terminate the fill. Continue at a yet to be visited boundary edge vertex.

• I'm not familiar with flood filling algorithm. Your explanation seems a little complicated to me. Could you please provide a decent reference to look at? Thanks. – mkocabas Jul 19 '17 at 5:47
• I got the solution by reading some. Thanks. – mkocabas Jul 19 '17 at 8:12

I've already commented on the use of flood fill and how it would be better as it's more flexible but another possible solution is scanline. (I say possible because it makes a lot of assumptions about your geometry but for the particular set shown and many similar ones it would work.)

For your example with 3 points: Find the intersection vertex from the segment v1,v2 and the line that v3 lies on. (The vertex to the upper left of v2) We'll call this vertex v4.

For every vertex pair a,b down v1,v4 and v1,v3
For every vertex from a to b
Mark as in the set
For every vertex pair a,b down v3,v2 and v4,v3
For every vertex from a to b
Mark as in the set


It's called scanline because (in the image above) you go down the red and green lines simultaneously and then red and blue lines simultaneously scanning the lines in as you go.

This solution would be very fast if there is an index pattern, which is often the case. Otherwise a calculation would be needed to determine which neighboring vertex lies on the line.

Funny thing is scanline, barycentric testing (in triangle bounding box), and flood fill are all ways of drawing triangles in 3d rendering.

I think you can calculate some surface-bound barycentric coordinates for each point on the surface, and then use them to check for inside or outside of the triangle.

I don't have an exact algorithm at hand but I found this following paper which does seem to handle exactly this kind of coordinates.

Barycentric Coordinates On Surfaces

• Thanks for the answer and reference paper. I will try to implement the method proposed. – mkocabas Jul 18 '17 at 12:55