我想对一个不规则采样的函数 z(x,y) 进行线性插值，并基于德劳内三角剖分。假设我有一座山丘，我已经获得了一个德劳内三角剖分：
我知道每个三角形顶点（样本）处的高度z。我想知道在任意点 (x,y) 处的高度 z。
如何确定包含点
(x,y)的三角形？一旦知道这一点，我想在三角形的三个顶点之间进行插值应该是相当简单的。你知道是否有现成的实现吗？可能包括插值部分？我相信肯定有某个开源实现这种方法。我特别感兴趣 Java（源代码或 JAR），但其他语言的版本也可能有用。
在 Delaunay 三角剖分表面中定位包含任意点的三角形
17
- Jean-François Corbett
6个回答
9
您可以通过“走过三角形”来找到目标三角形，具体操作请参考通过三角剖分跳转。这需要假设您可以在常数时间内访问相邻的三角形，如果三角剖分存储在双连通边列表或类似结构中，则情况是如此。实施起来很简单，因为您不需要任何额外的数据结构。
补充细节: 假设P是要查找的点。选择一个三角形T0和T0中的一个点P0。如果P在T0中，则查找结束。否则，找到被线段P0-P穿过的边E0，并进入沿这条边共享的其他三角形T1中，并选取T1中的一个点P1。现在重复以上步骤，直到三角形Tn包含P为止。
- Jiri Kriz
3
D(s,n) < D(s,c)，其中s为搜索点，n为新点，c为当前点，D为距离函数。 - nulvinge
3值得一提的是：“这个过程只能保证在Delaunay三角剖分中终止。对于任意三角剖分，它可能会进入一个无限循环”。然而，“通过在选择下一个相邻的单纯形时引入随机性，无限循环可以被打破，对于所有实际目的而言都是如此”。 - Steven Jeuris
@Steven：好评论。幸运的是，步行总是在Delanay三角剖分中终止，我们不需要担心任何随机性。 - Jiri Kriz
3
这不是一个容易回答的问题，它取决于您需要查找的性能以及您愿意为了获得该性能而交换的内存量。
如果这是一个非常罕见的操作，或者您的三角形数量很少，那么您可以始终遍历所有三角形。测试包含点的三角形并不是非常昂贵的。您应该首先编写此代码，并查看它是否提供可接受的性能。
如果不可接受，则可以尝试通过遍历三角剖分 - 从一个三角形开始，然后找到最靠近您要查找的点的下一个三角形。这确实假定您拥有一些额外的信息，超过了简单的三角形列表 - 具体来说，您可以找到使用给定顶点的三角形（或从其相邻三角形中找到三角形，与查找点的复杂度大致相当）。如果您没有计算这个信息，那么它几乎和查找点一样昂贵。
如果还不够快，您需要设置某种R-Tree。这允许您非常快速地根据位置查找三角形，但需要进行大量预处理并且需要大量内存用于树。
如果这是一个非常罕见的操作，或者您的三角形数量很少，那么您可以始终遍历所有三角形。测试包含点的三角形并不是非常昂贵的。您应该首先编写此代码，并查看它是否提供可接受的性能。
如果不可接受，则可以尝试通过遍历三角剖分 - 从一个三角形开始，然后找到最靠近您要查找的点的下一个三角形。这确实假定您拥有一些额外的信息，超过了简单的三角形列表 - 具体来说，您可以找到使用给定顶点的三角形（或从其相邻三角形中找到三角形，与查找点的复杂度大致相当）。如果您没有计算这个信息，那么它几乎和查找点一样昂贵。
如果还不够快，您需要设置某种R-Tree。这允许您非常快速地根据位置查找三角形，但需要进行大量预处理并且需要大量内存用于树。
如果你不经常使用的话，你可能会发现第二种和第三种方法的预处理时间比通过穷举搜索找到三角形的时间更长。
- DJClayworth
2
对于遍历而言，并不需要顶点的信息。唯一需要的信息是每条边对面的相邻三角形。这通常是可用的，例如如果三角剖分存储在DCEL中。 - Jiri Kriz
是的，从技术上讲你是正确的。但是关于相邻三角形的信息与顶点->三角形映射一样大且复杂，因此论点完全相同。 - DJClayworth
2
您可以使用Delaunay分层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
- Andreas Fabri
2
我的算法知识有点生疏。与其给出之前的答案，你最好使用Voronoi Diagram。
可以在 Voronoi 图上建立一个点定位数据结构，以回答最近邻查询，其中需要找到距离给定查询点最近的对象。最近邻查询具有众多应用场景。例如，可能想要找到最近的医院或数据库中最相似的对象。
我无法帮助您解决具体问题，但希望这能指引您走向正确的方向。
我猜您也可以使用R-tree，并将其链接到三角形上。
在谷歌上快速搜索“java r-tree”应该会帮助您找到现有的库。
- Steven Jeuris
1
1
我在这里找到了一个可行的实现：http://www.cs.bgu.ac.il/~benmoshe/DT/
find方法可以找到包含给定点的三角形，而z方法则进行平面插值。
不幸的是，它是一个已编译的JAR文件，所以我不知道算法是什么，但我感觉它会像@Jiri和@DJClayworth建议的那样“遍历三角剖分”。
同样不幸的是，这个JAR使用的命名方式相当不常规。我可能最终会编写一个具有更好命名方式的包装类。
- Jean-François Corbett
0
我对此很新，但如果您能够引用每个2D三角形，并使用哈希映射将键作为唯一数字编码为图像中的颜色，那么您可以用该实心颜色绘制三角形。
要找到三角形，您可以通过解码所请求位置处的颜色来检索键。
绘制三角形时会有成本，但查找应该很快。
我认为这个想法可以抽象到3D网格中。
- Dave
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接