Matlab algorithm for point location in Delaunay triangulations (tsearchn)

8 次查看（过去 30 天）
Sergey Klevtsov
Sergey Klevtsov 2013-9-24
编辑： Keith Dalbey 2013-12-31
Does anyone know which algorithm Matlab uses for point location in a Delaunay triangulation (function 'tsearchn')? I haven't been able to google it. I wonder if it's just brute force, or some sophisticated method.
The interest is purely theoretical, I want to compare performance of different point location approaches in high-dimensional triangulations and need a baseline for comparison.
A paper reference would be very welcome, or at least a general idea of the algorithm and its complexity in terms of d (dimension) and n (number of points/simpleces). If this, however, cannot be disclosed, than so be it.

请先登录，再回答此问题。

回答（1 个）

Keith Dalbey
Keith Dalbey 2013-12-31
编辑：Keith Dalbey 2013-12-31
A few years back I talked to the guy who wrote qhull and he said the "optimally fast" way to identify the triangles that contained the points would be to modify the qhull algorithm to use two sets of points at the same time (and I'm paraphrasing from memory here), as it inserts planes into the first set, keep track of what sides of the planes that the second set of points were located in. So the complexity of the optimal approach should be the complexity of qhull. I had also asked this question (how their new tsearchn algorithm worked, when the time for a particular problem I was working on dropped from several minutes to a few seconds) of mathworks and the non-descriptive answer I got was that it was based on qhull and that the specifics of the algorithm were proprietary, but I'd guess their using the "optimal" qhull approach.

类别

在 Help Center 和 File Exchange 中查找有关 Spatial Search 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by