0

我有一个由大约 100 万个三角形组成的平面 Delaunay 三角剖分。每个顶点都标有几个标量指标 [1],我希望在同一个规则网格上看到每个指标的快速、简单插值。作为参考,我的三角形的并集覆盖了大约 1000 万个具有(整数)坐标的网格单元。[2]

当我说简单时,我的意思是简单。双线性就好了!我的理解是,这(a)基本上是 GPU 为生而做的,(b)可能是无数家庭作业的主题。我自己是公共卫生领域的政府研究员,所以这不是我的功课。:-)

在我缓慢但正确的参考实现中,我可以在大约 10 分钟内计算出以下内容:

对于每个三角形 T:

  1. T的边界框内所有(整数)笛卡尔坐标的集合G;
  2. G中每个(x,y)的重心坐标(u,v,w);
  3. 拒绝不全为正的(u, v, w)——即在T内部;
  4. 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 缩放。

4

1 回答 1

1

虽然我没有看到任何可以解释您描述中缓慢的东西,但这是我将如何处理它。基本成分确实是“三角扫描仪”。

首先对 Y 上的三个顶点进行排序。这需要进行三个比较,并且只有六种可能的配置。在整数纵坐标上循环从顶部 Y 到中间 Y,然后从中间 Y 到底部 Y。对于每个纵坐标,与左侧和右侧的交点为您提供了一个间隔。

从左到右循环该区间内的整数横坐标。双循环只会访问属于三角形的网格节点。

您可以建立平面方程,即计算 的系数,而不是使用重心坐标,Z = a X + b Y + c并使用该公式进行插值。(您甚至可以增量计算值,即Z(X + 1) = Z(X) + a,但是对于每个三角形的少量点,我不确定这是否值得。)

依靠一个简单的约定很容易避免重复点:只产生落在三角形左侧的点,而不是落在右侧的点(这些将由右侧的三角形产生。)

在此处输入图像描述

某些汽车必须练习处理特殊情况,例如整数纵坐标处的水平边,但这是可以管理的。

总工作量将对三角形的数量、域的 Y 范围和覆盖的网格节点的数量敏感,并为每个因素计算少量算术运算。对于一百万个三角形和一千万个网格单元,运行时间低于一秒并非不可能。

于 2016-05-12T20:19:12.057 回答