定位 Delaunay 三角曲面中包含任意点的三角形
我正在寻找基于 Delaunay 三角剖分的不规则采样函数 z(x,y) 的线性插值。假设我有一座山，我已经获得了 Delaunay 三角测量：
我知道海拔 z 在每个三角形顶点（样本）。我想要任意点 (x,y) 处的高度 z。
如何判断哪个三角形包含点
(x,y)？一旦我知道了这一点，我想在三角形的三个顶点之间进行插值就相当简单了。你知道有现成的实现吗？也许还包括插值位？我确信某个地方一定有一个开源实现。我对 Java（源代码或 JAR）特别感兴趣，但任何 VB 风格或其他语言也可能有用。
I'm looking to do a linear interpolation of a irregularly sampled function z(x,y) based on a Delaunay triangulation. Say I have a hill for which I have obtained a Delaunay triangulation:
I know the altitude z at each of the triangle vertices (samples). I want the altitude z at an arbitrary point (x,y).
How do I tell which triangle contains point
(x,y)? Once I know this, I guess it's fairly straightforward to interpolate between the triangle's three vertices.Do you know of a ready-made implementation of this? Perhaps with the interpolation bit included as well? I'm sure there must be an open source implementation of this somewhere out there. I'm especially interested in Java (source or JAR), but any flavour of VB or some other language could be useful as well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您可以通过沿着三角测量走向搜索点来找到目标三角形。这假设您可以在恒定时间内访问相邻三角形，如果三角剖分存储在双连接边列表或类似结构中，就是这种情况。实现很简单，因为您不需要任何额外的数据结构。
添加细节：设 P 为搜索点。取任意三角形 T0 和 T0 中的点 P0。如果 P 在 T0 中，您就完成了。否则找到 T0 与线 P0-P 相交的边 E0。转到边 E0 上的 T 的相邻三角形 T1，并在 T1 中取点 P1。现在重复直到三角形 Tn 包含 P。
You can find the target triangle by walking through the triangulation towards the searched point. This assumes that you can access neighboring triangles in constant time, which is the case if the triangulation is stored in doubly connected edge list or similar structures. The implementation is straightforward because you do not need any additional data structures.
Added details: Let P be the searched point. Take any triangle T0 and a point P0 in T0. If P is in T0 you are finished. Else find the edge E0 of T0 that is crossed by the line P0-P. Go to the neighbor triangle T1 of T over the edge E0 and take a point P1 in T1. Now repeat until the triangle Tn contains P.
这不是一个容易回答的问题，它取决于您的查找所需的性能，以及您准备交换多少内存来获得该性能。
如果这是一个非常罕见的操作，或者三角形的数量很少，那么您始终可以迭代所有三角形。测试包含一个点的三角形并不是很昂贵。您可能应该首先对此进行编码，看看它是否能提供可接受的性能。
如果不可接受，您可以尝试遍历三角测量 - 本质上是从一个三角形开始，然后找到距离您要查找的点最近的下一个三角形。这确实假设您对简单的三角形列表有一些额外的信息 - 特别是您可以找到使用给定顶点的三角形（或从其相邻三角形中找到一个三角形，这在复杂性上大致相当）。如果您没有计算此值，那么它几乎与找到一个点一样昂贵。
如果这还不够快，您需要设置某种 R-Tree 。这使您可以非常快速地从其位置找到三角形，但确实需要大量的预处理和树的大量内存。
如果您不经常这样做，您可能会发现计算第二种和第三种方法的预处理时间比通过穷举搜索找到三角形的时间要长。
This is not an easy question to answer, and it depends on what performance you require from your lookup, and how much memory you are prepared to trade to get that performance.
If this is a very rare operation, or your number of triangles is small, then you can always iterate through all the triangles. Testing for a triangle containing a point isn't very expensive. You should probably code this first and see if it gives acceptable performance.
If it isn't acceptable, your can try walking through the triangulation - essentially start with a triangle and then find the next one nearest the point you are looking for. This does assume that you have some extra information over a simple list of triangles - specifically that you can find the triangles that use a given vertex (or find a triangle from its neighbouring triangle, which is roughly equivalent in complexity). If you don't have this computed then it is nearly as expensive as finding a point.
If that isn't fast enough, you need to set up some kind of R-Tree. This allows you to find triangles from their locations very quickly, but does need a lot of pre-processing and a substantial amount of memory for the tree.
You may find that the time to compute the pre-processing for each of the second and third methods is more than the time to find the triangles by exhaustive search, if you don't do it often.
我的算法知识有点生疏了。您可能最好使用 Voronoi 图，而不是我之前的答案。
我无法帮助您了解具体情况，但希望这可以为您指明正确的方向。
我猜你也可以使用 R-tree 在其中链接到三角形。
在 google 上使用“java r-tree”快速搜索应该可以帮助您找到现有的库。
My algorithms knowledge is a bit rusty. Instead of my prior answer, you are probably better of using a Voronoi Diagram.
I can't help you with the specifics of this, but hopefully this can point you in the right direction.
I'm guessing you could also use an R-tree in which you link to your triangles.
A quick search on google with 'java r-tree' should help you out to find existing libraries.
您可以使用 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
You might use a Delaunay Hierarchy http://hal.inria.fr/inria-00166711
The idea is to take a subset of the points, triangulate it, and have links between vertices between the two layers. The "walk" is then performed in the small triangulation, then one jumps from one layer to the next one, then one continues the walk. This is implemented in the triangulations of 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/
查找 方法查找包含给定点的三角形，并且z< /code> 方法进行平面插值。不幸的是，它是一个编译的 JAR，所以我不知道算法是什么，但我感觉它“遍历三角测量”，如 @Jiri 和 @DJClayworth 所建议的。
同样不幸的是这个 JAR 中使用的非常规命名法。我最终可能会编写一个具有更好命名法的包装类。
I found a working implementation here: http://www.cs.bgu.ac.il/~benmoshe/DT/
The
findmethod finds the triangle that contains a given point, and thezmethod does the planar interpolation.Unfortunately it's a compiled JAR, so I don't know what the algorithm is, but I sense that it "walks through the triangulation" as suggested by @Jiri and @DJClayworth.
Also unfortunate is the rather unconventional nomenclature used in this JAR. I may end up writing a wrapper class with nicer nomenclature.
我对此很陌生，但如果您能够引用每个二维三角形，使用密钥是唯一数字的哈希图，您可以将该密钥编码为图像中的颜色。然后用纯色绘制三角形。
要找到三角形，您可以通过解码请求位置的颜色来检索密钥。
绘制三角形时会有成本，但查找应该很快。
我认为这个想法可以抽象为 3D 网格。
I am new to this but if you were able to reference each 2d triangle, using a hash map where the key is a unique number could you encode that key as say a color in an image. Then draw the triangles with that solid color.
To find the triangle you retrieve the key by decoding the color at the requested position.
There would be a cost when drawing the triangle but the lookup should be fast.
I think the idea could be abstracted to meshes in 3d.