我有一个由大约 100 万个三角形组成的平面 Delaunay 三角剖分。每个顶点都标有几个标量指标 [1],我希望在同一个规则网格上看到每个指标的快速、简单插值。作为参考,我的三角形的并集覆盖了大约 1000 万个具有(整数)坐标的网格单元。[2]
当我说简单时,我的意思是简单。双线性就好了!我的理解是,这(a)基本上是 GPU 为生而做的,(b)可能是无数家庭作业的主题。我自己是公共卫生领域的政府研究员,所以这不是我的功课。:-)
在我缓慢但正确的参考实现中,我可以在大约 10 分钟内计算出以下内容:
对于每个三角形 T:
- T的边界框内所有(整数)笛卡尔坐标的集合G;
- G中每个(x,y)的重心坐标(u,v,w);
- 拒绝不全为正的(u, v, w)——即在T内部;
- T 中每个剩余坐标的加权和 (u z_1 + v z_2 + w*z_3),其中 z_1、z_2 和 z_3 对于给定度量 [1] 是 T 顶点处的标量值。
我真的需要步骤 1-3 快速;第 4 步是微不足道的,但这是我的最终目标。理想情况下,解决方案将采用以下任一形式:
- 一个经过适当许可(GPL 可以)的库,带有一个非常简单的 API;或者
- 一个足够清楚的解释,很明显中级程序员如何用 Fortran、R、Python 或 C 对其进行编码。
此任务的经典表述是“TIN 到 DEM”地形建模作业。但现在似乎更需要相反的情况(?)
一些基本的清理,比如当一个点恰好落在由 2 个以上三角形共享的边或顶点上时删除重复项,也是可以的。
非常感谢您的时间和关注。下火车后,我将根据建议清理格式和编辑!
脚注:
[1] 海拔、温度和湿度。[2] 整数,即它们在 UTM 网格上的间距为 20x20m。所以只需按 20 缩放。