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

Spatial queries for collections of triangles, tetrahedrons and general d-simplexes.
Updated 6 Jun 2020

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 (2024). 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
Find more on Delaunay Triangulation in Help Center and MATLAB Answers

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

Updates to underlying AABB-tree, etc.

Link to aabb-tree

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.