FINDTRIA - Point-in-Simplex queries in d-dimensions.

version (296 KB) by Darren Engwirda
Spatial queries for collections of triangles, tetrahedrons and general d-simplexes.


Updated 6 Jun 2020

From GitHub

View License on GitHub

FINDTRIA computes "point-in-" queries for collections of simplexes (triangles, tetrahedrons, etc) in d-dimensional space. Unlike MATLAB's existing point-location facilities, FINDTRIA supports general collections of simplexes, including non-Delaunay, non-convex, and even overlapping configurations, and can compute multiple intersections per query point.
FINDTRIA is based on an efficient d-dimensional AABB-tree, which is used to speed-up the computation of spatial queries.

FINDTRIA is relatively efficient. It's typically many orders of magnitude faster than brute-force searches, and is often faster than MATLAB's inbuilt routine TSEARCHN, especially when the number of query points is large. MATLAB's inbuilt POINTLOCATION routine is usually faster than FINDTRIA when the underlying triangulation is Delaunay, but is often slower -- sometimes by a large factor -- for non-Delaunay triangulations. It is also restricted to two- and three-dimensional problems.

FINDTRIA was not specifically designed to outperform MATLAB's existing point-location routines (though it sometimes does a good job), it's main purpose is to facilitate efficient queries on non-Delaunay triangulations in arbitrary dimensions -- capabilities that are currently unsupported by existing inbuilt routines.

See TRIADEMO to get started with a set of example problems:

triademo(1); % point-location for a 2-dimensional non-Delaunay triangulation.
triademo(2); % point-location for a 3-dimensional non-Delaunay triangulation.
triademo(3); % compare FINDTRIA and TSEARCHN for higher-dimensional problems.

Additional information and references are available via the Github repository (

Cite As

Darren Engwirda (2022). FINDTRIA - Point-in-Simplex queries in d-dimensions. (, GitHub. Retrieved .

MATLAB Release Compatibility
Created with R14
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!
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.