How to detect a hole in the meshed body?

Question

Do we have any specific algorithm/s to identify/locate holes in a meshed body, based on mesh type?

Answer 1

If we have a triangulation of a space $X$ we can compute its simplicial homology. The rank of the first homology group $H_1(X, \Bbb Z)$ gives the number of holes in the space.

Alternatively we could take coefficients in a field $\Bbb F$. Then $H_1(X, \Bbb F)$ is a vector space and the number of holes is simply its dimension.

There are plenty of specific algorithms doing that, see one for example here.

Answer 2

Don't know how much it helps, but elementary algebraic topology, more specifically Euler characteristic, tells us the number of holes. Assume that the mesh has $V$ vertices, $E$ edges, and $F$ faces (in your case they seem to be triangles, but that is irrelevant). Then the Euler characteristic is $$ \chi=V-E+F. $$ The number of holes is then basically $1-\chi$. The justification is not too difficult (see that WP-page). Listing the following examples:

• A mesh consisting of a single triangle has $V=3$, $E=3$ and $F=1$, yielding $\chi=1$ and zero holes.
• A mesh of a $3\times3$ square with a single square missing in the middle has $V=4\cdot4=16$, $E=4\cdot3+3\cdot4=24$ (twelve horizontal edges, twelve vertical) and $F=8$ ($9=3\cdot3$ altogether, but the center face is missing, so $F=8$). Here $\chi=V-E+F=0$ matching with a single hole.
• Generalizing the previous example. If we have an $m\times n$ rectanglular mesh consisting of squares, and $H$ isolated $1\times1$ holes, we have $(m+1)(n+1)$ vertices, $(m+1)n+(n+1)m$ edges, and $m\cdot n- H$ faces. Again yielding $\chi=1-H.$

---

Finding those holes amounts to finding the collection of edges with the property that the given edge appears as a border of only a single face (instead of the "normal" two). Those edges can then be split into $H+1$ cycles – one for the exterior perimeter and one around each hole. You may need to pay special attention to the possibility that two separate holes may touch at a single vertex. If that possibility is ruled out, then there is only one way to split the collection of 1-sided edges into cycles.

Answer 3

(Maybe a bit late to the party, saw the question just now)

Supposing the mesh is exactly as the one shown, (only made of triangle, and each side of that hole is adjacent to a triangle) you can use https://github.com/libigl/libigl/blob/master/include/igl/boundary_loop.h function to get all boundaries. It will return 2 boundaries: the external one made of the sides of the object, and the internal hole. Then you can get the most internal "hole" as its points are the farthest from the mesh bounding box (https://github.com/libigl/libigl/blob/master/include/igl/bounding_box.h)