Delaunay 三角剖分内整数坐标的双线性插值
Bilinear interpolation on integer coordinates within a Delaunay triangulation
我有一个由大约 100 万个三角形组成的平面 Delaunay 三角剖分。每个顶点都标记有几个标量指标 [1]，我希望在同一个规则网格上看到每个指标的快速、简单的插值。作为参考，我的三角形并集涵盖了大约 1000 万个具有（整数）坐标的网格单元。 [2]
当我说简单时，我的意思是简单。双线性很好！我的理解是，这 (a) 基本上是 GPU 谋生的工作，以及 (b) 可能是无数家庭作业的主题。我本人是 public 健康方面的政府研究员，所以这不是我的家庭作业。 :-)
在我缓慢但正确的参考实现中，我可以在大约 10 分钟内计算出以下内容：
对于每个三角形 T:
- T的边界框内所有（整数）笛卡尔坐标的集合G；
- G 中每个 (x, y) 的重心坐标 (u, v, w)；
- 拒绝不是所有正数的 (u, v, w) — 即在 T 内；
- T中每个剩余坐标的加权和（uz_1 + vz_2 + w*z_3），其中z_1、z_2 和 z_3 对于给定的度量 [1]，是 T 的顶点处的标量值。
我真的需要第 1-3 步要快；第 4 步很简单，但这是我的最终目标。理想情况下，解决方案将采用以下任一形式：
- 一个经过适当许可（GPL 可以）的库，非常简单API；或
- 一个足够清楚的解释，很明显中级程序员如何用 Fortran、R、Python 或 C 编写代码。
此任务的经典表述是 "TIN to DEM" 地形建模作业。但现在似乎更需要反过来(?)
一些基本的清理，比如当一个点恰好落在由 2+ 个三角形共享的边或顶点上时删除重复项，也可以。
非常感谢您的时间和关注。下车后，我会根据建议清理格式并进行编辑！
脚注：
[1] 海拔、温度和湿度。
[2] 在 UTM 网格上间隔 20x20m 的意义上的整数。所以只需按 20 缩放即可。
虽然我没有看到任何可以解释您的描述缓慢的原因，但我将如何处理它。基本成分确实是 "triangle scanner".
首先对 Y 上的三个顶点进行排序。这需要进行三次比较，只有六种可能的配置。从顶部 Y 到中间 Y 然后从中间 Y 到底部 Y 在整数纵坐标上循环。对于每个纵坐标，与左侧和右侧的交点给你一个间隔。
在该区间内的整数横坐标上从左到右循环。双循环只会访问属于三角形的网格节点。
不使用重心坐标，可以建立平面的方程，即计算Z = a X + b Y + c的系数，并用这个公式进行插值。 （您甚至可以增量计算值，即 Z(X + 1) = Z(X) + a，但对于每个三角形的少量点，我不确定这是否值得。）
通过一个简单的约定很容易避免重复点：只生成落在三角形左侧的点，而不是落在右侧的点（这些点将由三角形生成到对。）
有些车必须练习处理特殊情况，例如整数纵坐标的水平边，但这是可以管理的。
总工作量将对三角形的数量、域的 Y 范围和覆盖的网格节点的数量敏感，计算每个这些因素的少量算术运算。对于一百万个三角形和一千万个网格单元，低于一秒的 运行 次并非不可能。
我有一个由大约 100 万个三角形组成的平面 Delaunay 三角剖分。每个顶点都标记有几个标量指标 [1]，我希望在同一个规则网格上看到每个指标的快速、简单的插值。作为参考，我的三角形并集涵盖了大约 1000 万个具有（整数）坐标的网格单元。 [2]
当我说简单时，我的意思是简单。双线性很好！我的理解是，这 (a) 基本上是 GPU 谋生的工作，以及 (b) 可能是无数家庭作业的主题。我本人是 public 健康方面的政府研究员，所以这不是我的家庭作业。 :-)
在我缓慢但正确的参考实现中，我可以在大约 10 分钟内计算出以下内容：
对于每个三角形 T:
- T的边界框内所有（整数）笛卡尔坐标的集合G；
- G 中每个 (x, y) 的重心坐标 (u, v, w)；
- 拒绝不是所有正数的 (u, v, w) — 即在 T 内；
- T中每个剩余坐标的加权和（uz_1 + vz_2 + w*z_3），其中z_1、z_2 和 z_3 对于给定的度量 [1]，是 T 的顶点处的标量值。
我真的需要第 1-3 步要快；第 4 步很简单，但这是我的最终目标。理想情况下，解决方案将采用以下任一形式：
- 一个经过适当许可（GPL 可以）的库，非常简单API；或
- 一个足够清楚的解释，很明显中级程序员如何用 Fortran、R、Python 或 C 编写代码。
此任务的经典表述是 "TIN to DEM" 地形建模作业。但现在似乎更需要反过来(?)
一些基本的清理，比如当一个点恰好落在由 2+ 个三角形共享的边或顶点上时删除重复项，也可以。
非常感谢您的时间和关注。下车后，我会根据建议清理格式并进行编辑！
脚注：
[1] 海拔、温度和湿度。 [2] 在 UTM 网格上间隔 20x20m 的意义上的整数。所以只需按 20 缩放即可。
虽然我没有看到任何可以解释您的描述缓慢的原因，但我将如何处理它。基本成分确实是 "triangle scanner".
首先对 Y 上的三个顶点进行排序。这需要进行三次比较，只有六种可能的配置。从顶部 Y 到中间 Y 然后从中间 Y 到底部 Y 在整数纵坐标上循环。对于每个纵坐标，与左侧和右侧的交点给你一个间隔。
在该区间内的整数横坐标上从左到右循环。双循环只会访问属于三角形的网格节点。
不使用重心坐标，可以建立平面的方程，即计算Z = a X + b Y + c的系数，并用这个公式进行插值。 （您甚至可以增量计算值，即 Z(X + 1) = Z(X) + a，但对于每个三角形的少量点，我不确定这是否值得。）
通过一个简单的约定很容易避免重复点：只生成落在三角形左侧的点，而不是落在右侧的点（这些点将由三角形生成到对。）
有些车必须练习处理特殊情况，例如整数纵坐标的水平边，但这是可以管理的。
总工作量将对三角形的数量、域的 Y 范围和覆盖的网格节点的数量敏感，计算每个这些因素的少量算术运算。对于一百万个三角形和一千万个网格单元，低于一秒的 运行 次并非不可能。