<p>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.</p>

CC BY-SA 3.0
2017-07-19T05:47:27.480Z
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
CC BY-SA 3.0
2017-07-18T21:37:16.053Z
2017-07-19T22:05:00.340Z
2017-07-19T22:05:00.340Z
joojaa
<p>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.)</p>

<p>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. </p>

<pre><code>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
</code></pre>

<p><a href="https://i.sstatic.net/XsUCe.gif" rel="nofollow noreferrer"><img src="https://i.sstatic.net/XsUCe.gif" alt="enter image description here"></a></p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-07-19T07:25:04.967Z
2017-07-19T22:10:48.463Z
2017-07-19T22:10:48.463Z
Andrew Wilson
<p>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.</p>

<p>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.</p>

<p><a href="https://www.cct.lsu.edu/~swan2/Reference/DifferentialGeom/papers/BaryCoordonSurf_Rustamov2010SGP.pdf" rel="nofollow noreferrer" title="Barycentric Coordinates On Surfaces">Barycentric Coordinates On Surfaces</a></p>

CC BY-SA 3.0
2017-07-18T12:55:37.787Z
Thanks for the answer and reference paper. I will try to implement the method proposed.
mkocabas
CC BY-SA 3.0
2017-07-18T12:22:01.350Z
2017-07-18T12:22:01.350Z
Dragonseel
<p><a href="https://i.sstatic.net/49rn8.png" rel="noreferrer"><img src="https://i.sstatic.net/49rn8.png" alt="enter image description here"></a>
I have 3 vertices <code>(V1, V2, V3)</code> 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. </p>

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

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

CC BY-SA 3.0
2017-07-19T05:25:46.620Z
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
CC BY-SA 3.0
2017-07-19T05:52:26.147Z
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
CC BY-SA 3.0
2017-07-19T07:00:57.967Z
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
CC BY-SA 3.0
2017-07-19T08:09:43.763Z
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
<mesh><triangulation>
How can I perform a triangle inside test in polygon meshes?
mkocabas
# How can I perform a triangle inside test in polygon meshes?

(Asked by: username_0 on 2017-07-18)

[![enter image description here](https://i.sstatic.net/49rn8.png)](https://i.sstatic.net/49rn8.png)
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?

**Tags:** mesh, triangulation

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  

---

## 3 answers

### Answer by username_2 on 2017-07-18. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_1 on 2017-07-19. Score: 3

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

```

[![enter image description here](https://i.sstatic.net/XsUCe.gif)](https://i.sstatic.net/XsUCe.gif)

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.


---

### Answer by username_3 on 2017-07-18. Score: 2

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](https://www.cct.lsu.edu/~swan2/Reference/DifferentialGeom/papers/BaryCoordonSurf_Rustamov2010SGP.pdf "Barycentric Coordinates On Surfaces")

> **Comments:**
> **username_0**: Thanks for the answer and reference paper. I will try to implement the method proposed.  

---

