我希望对基于Delaunay三角测量的不规则采样函数进行线性插值。假设我有一座小山，我获得了Delaunay三角测量：z(x,y)
我知道每个三角形顶点（样本）的高度。我想要任意点的高度。zz(x,y)
如何判断哪个三角形包含点？一旦我知道了这一点，我想在三角形的三个顶点之间插值是相当简单的。(x,y)
您知道现成的实现吗？也许还包括插值位？我敢肯定，在某个地方一定有一个开源的实现。我对Java（源代码或JAR）特别感兴趣，但任何VB或其他语言的味道也可能有用。
您可以通过通过三角测量向搜索点走来查找目标三角形。这假设您可以在恒定时间内访问相邻的三角形，如果三角测量存储在双连接边列表或类似结构中，则会出现这种情况。实现非常简单，因为您不需要任何其他数据结构。
新增详细信息：设 P 为搜索点。取任何三角形 T0 和 T0 中的点 P0。如果 P 在 T0 中，则操作完成。否则，请查找 T0 的边 E0，该边与线 P0-P 相交。转到边缘 E0 上 T 的 T1 的相邻三角形 T1，并在 T1 中取一个点 P1。现在重复，直到三角形 Tn 包含 P。
这不是一个容易回答的问题，它取决于您从查找中需要什么性能，以及您准备交易多少内存来获得该性能。
如果这是一个非常罕见的操作，或者您的三角形数量很少，那么您可以随时迭代所有三角形。测试包含点的三角形并不是很昂贵。您可能应该首先对此进行编码，看看它是否提供可接受的性能。
如果这是不可接受的，你可以尝试走过三角测量 - 基本上从一个三角形开始，然后找到下一个最接近你正在寻找的点。这确实假设您在一个简单的三角形列表中有一些额外的信息 - 特别是你可以找到使用给定顶点的三角形（或者从其相邻的三角形中找到一个三角形，这在复杂性上大致相等）。如果你没有计算出来，那么它几乎和找到一个点一样昂贵。
如果这还不够快，你需要设置某种R-Tree。这使您可以非常快速地从其位置找到三角形，但确实需要大量的预处理和树的大量内存。
您可能会发现，计算第二种和第三种方法的预处理的时间超过了通过详尽搜索查找三角形的时间，如果您不经常这样做的话。
