FINDTRIA - Point-in-Simplex queries in d-dimensions.
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).
Citation pour cette source
Darren Engwirda (2024). FINDTRIA - Point-in-Simplex queries in d-dimensions. (https://github.com/dengwirda/find-tria), GitHub. Récupéré le .
Compatibilité avec les versions de MATLAB
Plateformes compatibles
Windows macOS LinuxCatégories
Tags
Remerciements
Inspiré par : AABBTREE - A d-dimensional bounding-box tree.
A inspiré : MESH2D: Delaunay-based unstructured mesh-generation
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!Découvrir Live Editor
Créez des scripts avec du code, des résultats et du texte formaté dans un même document exécutable.
aabb-tree
mesh-file
Les versions qui utilisent la branche GitHub par défaut ne peuvent pas être téléchargées
Version | Publié le | Notes de version | |
---|---|---|---|
1.4.0.0 | Updates to underlying AABB-tree, etc. |
|
|
1.3.0.0 | Link to aabb-tree |
|
|
1.0.0.0 |
|