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 回答