Version (183 KB) by Gypaets
Mesh reconstruction and hole finding in a point cloud
Updated 29 Jun 2017

[triangulation, holes] = findTheHoles(XY,S,M,T)
% Definition
findTheHoles is a 2D mesh reconstruction tool which automatically
identifies holes in a points cloud.
% Usage
XY= Nx2 matrix with point coordinates.
Optional arguments:
S = Critical area ratio (real and positive number). Knots with a value
higher than the ratio of maximum to minimum neighbouring polygon
area are identified as hole-border points. Default value is 3.
M = Flag for manual editing. Default value is 0.
0: No manual editing.
1: Manual editing of hole-border points. After the first calculation
a figure with the point cloud is opened. Automatically recognized
points are marked with an 'x'. The user can add/remove
not/wrongly recognized border points selecting them with the
brush and clicking the appropiate button.
T = Triangulation (Nx3 matrix with polygon vertices). If not given the
delaunay triangulation of X,Y is used.
.Points: nx2 matrix with points' coordinates.
.ConnectivityList: nx3 matrix with the triangulation polygons.
holes: Cell array. Each cell element is an nx1 matrix with ordered
hole border point indices.

% Method
To identify the holes a triangulation of the points cloud is needed. If
none is given, the delaunay triangulation is used. Points where the
ratio between maximum and minimum neighbouring polygon area exceeds a
critical value are identified as hole-border points. Polygons for which
all vertices are identified as hole-border points are deleted.
The adjacency matrix of the resulting mesh is clustered to get the
% Issues
The clustering algorithm isn't fully developed yet and has issues with
interconnected holes among others.

% Examples
See file examples_findTheHoles.m

Cite As

Gypaets (2024). Gypaets/findTheHoles (, GitHub. Retrieved .

MATLAB Release Compatibility
Created with R2015b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Delaunay Triangulation in Help Center and MATLAB Answers
Tags Add Tags

Inspired: HoleDetection3D

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Versions that use the GitHub default branch cannot be downloaded

Version Published Release Notes

Repo update.
Added image to description

To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.