Delaunay三角剖分内整数坐标上的双线性插值

我有一个由约1百万个三角形组成的平面Delaunay三角剖分。每个顶点都用几个标量度量标记[1]，我希望在同一个规则网格上看到每个度量的快速简单插值。作为参考，我的三角形的联合覆盖了约1000万个具有（整数）坐标的网格单元。 [2]Delaunay三角剖分内整数坐标上的双线性插值

当我说简单，我的意思是简单。 Bilinear很好！我的理解是，这是（a）基本上GPU是以什么为生，以及（b）可能是无数家庭作业的主题。我自己是公共卫生的政府研究员，所以对我来说这不是功课。 :-)

以我缓慢但正确的参考实现中，我可以计算在大约10分钟以下：

对于每个三角形T：

所有（整数）的集合G笛卡尔坐标在T的边界框内;
G中每个（x，y）的重心坐标（u，v，w）
拒绝（u，v，w）并非都是正数 - 也就是在T内部;
对于T中的每个剩余坐标，其中z_1，z_2和z_3对于给定度量[1]的加权总和（u z_1 + vz_2 + w * z_3），其顶点处的标量值为T.

我真的需要1-3步要快;第4步是微不足道的，但这是我的最终目标。理想情况下，解决方案采用以下任一种形式：

具有死亡简单API的适当许可（GPL为OK）库;或
这就足够清楚，很明显怎样的中级程序员可以使用Fortran，R，Python或C.它编写了一个解释

这个任务的一个经典配方是“TIN到DEM”地形模型工作。但似乎相反的是更普遍使用的这些天（？）

一些基本清理，就像当一个点正好落在由2+三角形共享边或顶点删除重复，是OK了。

非常感谢您的时间和关注。一旦我离开火车，我将清理格式并编辑每个建议！

脚注：

[1]海拔，温度和湿度。 [2]在UTM网格上相隔20x20m的整数。因此，仅仅通过20

来源

2016-05-12 dholstius

快速提问：输出需要多少精度？如果不是过多，您可以在GPU上使用OpenGL/OpenGL-ES吗？正如你所说，这正是GPU所做的事情（并且速度非常快）。 –

我只需要每个度量标准满量程的大约1％（可能是0.1％）的精度。因此，例如，如果度量“z”是温度，并且它们在整个域上范围从0到100C，那么我只需要z的插值到大约1.0或者大约0.1C的精度。许多三角形将是“平坦的“，顶点都非常接近相同的z。我试图生成三角测量，这样梯度就会相当平滑 - 也就是说，在我期望梯度变陡的地方，我生成了更细的网格。我可以通过三角形的大小绘制z的范围直方图...？ – dholstius

这看起来很有希望，除了我已经有了我想要使用的Delaunay三角剖分：http://rncarpio.github.io/delaunay_linterp/ – dholstius

规模虽然我没有看到任何可以解释你的描述缓慢，这里是我将如何处理它。基本成分的确是“三角扫描仪”。

开始通过Y.排序的三个顶点这需要三个比较和有只有六个可能的配置。循环遍历从顶部Y到中间Y，然后从中间Y到底部Y的整数坐标。对于每个坐标，与左侧和右侧的交点给出一个间隔。

在该间隔内从左向右环绕整数abscissas。双循环只会访问属于三角形的网格节点。

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

通过依靠简单约定很容易避免重复点：仅产生落在三角形的左侧点，而不是那些落在右侧

一些汽车必须行使处理特殊（这些将通过三角形向右生产。）例如整数纵坐标的水平边，但这是可控的。

总工作量将对三角形的数量，域的Y范围和覆盖的网格节点的数量敏感，对这些因素中的每一个计算一些算术运算。对于一百万个三角形和一千万个网格单元，运行时间在一秒以下不是不可能的。

来源

2016-05-12 20:19:12

谢谢。你能否详细说一下“建立平面方程”，给定顶点的三个值？ – dholstius

@dholstius：为'i = 1,2,3'解出易系统'Zi = a Xi + b Yi + c'。 –

啊，我明白了。再次感谢。 – dholstius

Delaunay三角剖分内整数坐标上的双线性插值

回答

相关问题