我正在寻找z(x,y)基于 Delaunay 三角剖分对不规则采样函数进行线性插值。假设我有一个山丘，我已经获得了 Delaunay 三角测量：
我知道z每个三角形顶点（样本）的高度。z我想要任意点的高度(x,y)。
如何判断哪个三角形包含点(x,y)？一旦我知道了这一点，我想在三角形的三个顶点之间进行插值是相当简单的。
你知道这个的现成实现吗？也许还包括插值位？我敢肯定那里一定有一个开源实现。我对 Java（源代码或 JAR）特别感兴趣，但任何风格的 VB 或其他语言也可能有用。
您可以通过三角剖分走向搜索点来找到目标三角形。这假设您可以在恒定时间内访问相邻的三角形，如果三角剖分存储在双向连接的边列表或类似结构中，情况就是如此。实现很简单，因为您不需要任何额外的数据结构。
增加细节：设 P 为搜索点。取任意三角形 T0 和 T0 中的一个点 P0。如果P在T0，你就完成了。否则找到与线 P0-P 相交的 T0 的边 E0。转到边 E0 上 T 的相邻三角形 T1，并在 T1 中取点 P1。现在重复直到三角形 Tn 包含 P。
这不是一个容易回答的问题，它取决于您从查找中需要什么性能，以及您准备交易多少内存来获得该性能。
如果这是一个非常罕见的操作，或者您的三角形数量很少，那么您总是可以遍历所有三角形。测试包含一个点的三角形并不是很昂贵。您可能应该先编写代码，看看它是否提供了可接受的性能。
如果它不可接受，您可以尝试通过三角测量- 基本上从一个三角形开始，然后找到下一个最接近您正在寻找的点的点。这确实假设您对简单的三角形列表有一些额外的信息 - 特别是您可以找到使用给定顶点的三角形（或从其相邻三角形中找到一个三角形，这在复杂性上大致相当）。如果你没有计算这个，那么它几乎和找到一个点一样昂贵。
如果这还不够快，您需要设置某种R-Tree。这使您可以非常快速地从它们的位置找到三角形，但确实需要大量的预处理和大量的树内存。
如果您不经常这样做，您可能会发现计算第二种和第三种方法的预处理的时间比通过穷举搜索找到三角形的时间要多。
我的算法知识有点生疏。而不是我之前的答案，您可能最好使用Voronoi Diagram。
可以在 Voronoi 图的顶部构建点位置数据结构，以回答最近邻查询，其中人们想要找到最接近给定查询点的对象。最近邻查询有许多应用。例如，人们可能想要找到最近的医院，或者数据库中最相似的对象。
我无法为您提供详细信息，但希望这可以为您指明正确的方向。
我猜你也可以使用链接到三角形的R-tree。
使用“java r-tree”在谷歌上快速搜索应该可以帮助您找到现有的库。
您可以使用 Delaunay Hierarchy http://hal.inria.fr/inria-00166711 这个想法是获取点的子集，对其进行三角剖分，并在两层之间的顶点之间建立链接。然后在小三角剖分中执行“行走”，然后一个人从一层跳到下一层，然后一个人继续行走。这是在 CGAL 的三角测量中实现的：http ://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Section_37.10
我在这里找到了一个可行的实现：http ://www.cs.bgu.ac.il/~benmoshe/DT/
该find方法找到包含给定点的三角形，该z方法执行平面插值。
不幸的是，它是一个编译的 JAR，所以我不知道算法是什么，但我感觉到它“通过三角测量”，正如 @Jiri 和 @DJClayworth 所建议的那样。
同样不幸的是这个 JAR 中使用的非常规的命名法。我最终可能会编写一个具有更好命名法的包装类。