在Delaunay-triangulated表面中找到包含任意点的三角形
Jea*_*ett 16 java algorithm interpolation vba triangulation
我正在寻找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.
- 值得一提的是:_"这个程序只能在Delaunay三角剖分中终止.对于任意三角剖分,它可以进入有限循环"_ .... _"但是,对于所有实际目的,通过引入有限循环可以被打破选择哪个邻近的单一访问时的随机性"_ (3认同)
| 归档时间： |
|
| 查看次数： |
3707 次 |
| 最近记录： |