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

Spatial queries for collections of triangles, tetrahedrons and general d-simplexes.

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 (http://github.com/dengwirda/find-tria).