通常的随机边缘跳跃方法应该有效。基本上，从网格的任何三角形开始，然后确定目标点位于哪条边的对边。也就是说，确定哪条边在延伸到一条线时将点与三角形的内部分开。当有两种可能性时，随机选择一种，并考虑与该共享边相邻的三角形，然后重复。随机化应该使该方法收敛于 Delaunay 三角剖分的概率 1，我想不出它不适用于任意三角剖分的原因。

编辑：我应该补充一点，边缘跳跃应该是$O(\log N)$对于单个点有一个合理的常数，所以它是$O(M \log N)$为了$M$点。但是，如果您按位置对点进行排序（例如首先使用希尔伯特曲线排序），您可以使用前一个查询的三角形初始化每个新查询，以进一步减少运行时间（我不是 CS 理论家，所以我可以' t告诉你大O会在那里）。

Edit2：发现这个 PDF描述了这样一个保证终止的“行走”方案，并回顾了更天真的方法。

使用四叉树的另一种替代方法是使用三角剖分层次结构。见奥利维尔德维尔斯。改进的增量随机 Delaunay 三角测量。在过程中。14 年。ACM 研讨会。计算。Geom.，第 106-115 页，1998。它最适用于 Delaunay 三角剖分，但也适用于非 Delaunay。

基本上无论你做什么来加速点定位都需要构建一个辅助数据结构。在四叉树或其他一些空间细分的情况下，您需要构建细分树。在跳边的情况下，需要构建三角形相邻拓扑结构。三角剖分层次结构还需要构建一个粗三角剖分树。

我不相信您的解决方案实际上是正确的。考虑您拥有这些节点的情况：

• 答：(-3, 1)
• B: (0, 2)
• C: (3, 1)
• D: (0, -5)

有三角形ABC和ACD。现在 B 是离原点最近的点，但原点在三角形 ACD 中，其中不包含 B。

其余的，这个答案提供了一个解决方案，在退化的情况下可能会像$O(N \cdot M)$，但通常会更快 - 特别是对于 Delaunay 三角剖分和在某种意义上接近的三角剖分。

我会考虑构建一个包含三角形本身的四叉树的选项。即，您有一个存储在每个节点中的四叉树（对应于一个边界框）：

• 分割框的坐标，或者四个子树的边界框；
• 指向子树的指针；
• 完全落在此矩形的边界框内但不完全落在四个子树中的任何一个内的三角形集。换句话说，与四叉树的两个细分线段中的任何一个相交的三角形。

当给定一个点 P 时，遍历从四叉树的根到包含 P 的最小框的路径上的所有节点。您需要检查在这些节点中遇到的所有三角形。对于“表现良好”的三角测量，应该只有类似$\sqrt{n}$需要在包含的节点级别检查的三角形$n$子树中的三角形，并且深度应限制为$\log n$. 对于“行为不端”的三角测量，您可能会得到$O(N\cdot M)$工作。

CGAL处理三角测量和点定位（以及更多）。特别是2D 三角测量模块可以做你想做的事。