点与高度图之间的距离

Question

给定一个三维点和一个高度图（一个高程数据的光栅图像），我如何快速确定高度图和该点之间的距离？

天真的方法是测量到高度图上每个点的距离，虽然可行但太慢了。

当然，有很多通用算法可以加速点云和点之间的最近邻搜索，例如k-d tree。

是否有一种算法更适合高度图的特定情况，无论是每个查询的性能还是在查询之前准备必要的数据结构的性能？

理想情况下，我正在寻找一种算法，它不需要将整个高度图数据构建成树。似乎应该有某种方法利用点已经按X和Y方向在高度图中排序的事实。

- HugoRune

---

你需要精确的距离吗，还是获取一个快速的上限或下限就足够了？ - j_random_hacker

你的高度图不能具有无限的高度分辨率。因此，靠近点的某些部分将比其他部分更接近，因为它们不能超过基准平面距离+-高度图限制。此外，您可以使用缩小的高度图来查找候选区域。 - JAre

@j_random_hacker 理想情况下，我希望得到精确的距离，甚至是最近的点本身。但是如果有更好的方法可以获得上限和下限，我认为我也可以使用它，只要上限和下限之间的范围是可调整的。 - HugoRune

你是否正在尝试找到离给定的三维点最近的高度图上的点？ - Steve H

Answer 1

以下两个方法都假设您的查询点P在高度图上方，即从高度图平面到P的法线与实际包含高度图的区域相交。如果不是这样，则建议测量到高度图4条边上最近点的距离，并取最小值。我没有思考下面的两个方法是否仍然可以在这种（常见）情况下给出精确答案，但它们可能可以被说服。

首先，在高度图平面上找到直接位于P下方的点Q（即通过P的高度图平面的法线与平面在Q处相交）。让高度为height(Q)的高度图表面上的点R在Q处。那么从P到高度图中任意一点的距离的上限U由P和R之间的距离给出，即distance(P,Q) - height(Q)。

在接下来的内容中，我将称高度图像素的“顶部边缘”下方的高度图平面上的点A的基础为A。例如，Q是R的基础。

当P靠近高度图表面时

在这种情况下，U将很小，并且您可以利用任何比R更接近P的高度图点不能使其基础距离Q处的高度图平面超过U。 （想象一个以P为中心，半径为U的球：它刚好触及R，而任何比R更接近P的点必须在其中。）因此，在寻找比R更接近的点时，您可以限制自己仅测试以Q为中心的（2U）x（2U）高度图“像素”的矩形。 （或者实际上只是以Q为中心的半径U圆盘的高度图像素 - 但由于更复杂的循环条件，这只能节省少量的比较，并且可能实际上更慢。） 注意：此算法不考虑每个高度图像素的四个“侧壁”。例如，假设高度图像素的大小为1x1单位，R的高度为5，P比R高3个单位，在R左侧有一个高度为100的高度图像素S，而所有其他高度图像素的高度都为0：那么从P到高度图的最小距离可以被认为是1，因为如果您从P开始直接向左移动1个单位，您将撞到支持S的东侧“墙壁”。但上述算法将报告距离为3，因为它仅考虑每个高度图像素的“顶部边缘”，而S的顶部边缘远在P之后。

当P远离时

在这种情况下，高度图点与P之间的角度起到的作用较小；一个点是否靠近P更多地取决于其高度而不是在高度图平面中其基础与Q之间的距离。因此，我建议将高度图点的一份副本按照高度从大到小排序。然后，您可以按照高度递减顺序计算列表中每个点A与P之间的距离，在高度(A) < height(Q)时停止，因为列表中的任何剩余点B，其高度必然更低，必须至少与R一样远离P，因为线段BP处于某些非零角度。

实际上，还有一种稍微更复杂的停止准则：在遍历点列表时的任何时候，您都可以中止此过程并切换到检查其高度图平面基于 Q 更接近的所有点。也就是说，假设您正在按高度递减顺序遍历高度图点列表，并来到一个基础与 Q 之间存在一些小距离 D 的点 A：那么最接近 P 的点要么是迄今为止找到的最接近点，要么是在高度图平面上的基底距离 Q 最多为 D 的最接近点。这可以使用搜索以 (2D)x(2D) 高度图像素网格找到，类似于“当 P 接近高度图表面时”发生的情况。这在 R 比较深的情况下很有用，否则需要按递减顺序检查几乎所有其他高度图点。当然，如果 R 在一个宽阔、深谷中，那么找到足够接近 A 将需要很长时间，然后每个或几乎每个点都将被测试。

- j_random_hacker