algorithm - 点与高度图之间的距离

Question

给定一个三维点和一个heightmap（高程数据的光栅图像），如何快速确定高度图和点之间的距离？
这种简单的方法，测量到高度图上每个点的距离，有效，但耗时太长。
当然，有很多通用算法可以加快点云和点之间的近邻搜索，例如ak-d tree。
在每个查询的性能方面，或者在查询之前准备必要的数据结构的性能方面，是否有一种算法更适合于heightmap的特定情况？
理想情况下，我搜索的算法不需要从整个高度图数据中构造树似乎应该有某种方法来使用这样一个事实，即点已经在高度图中按x和y方向排序。

Answer 1

下面的两个想法都假设您的查询点p“直接位于”高度图之上——也就是说，从高度图平面到p的法线与实际包含高度图的区域相交。如果没有，我建议测量到高度图4条边上最近点的距离，取最小值。我还没想清楚下面的两个想法是否会在这个（常见的）案例中给出确切的答案，但他们可能会被说服。
首先，在正下方的高度图平面上找到q点（即从高度图平面到p的法向线在q处与平面相交）。设高度图面上的点，在q以上的高度（q）处为r，然后p到高度图中任何点的距离的上界u由p和r之间的距离给出，即距离（p，q）-高度（q）。
在下面的内容中，我将位于某个高地图像素的“顶边”下的高地图平面上的点称为a的底，例如q是r的底。
当P接近高度图面时
在这种情况下，U很小，你可以使用这样一个事实：任何靠近P比R的高度图点，其基部都不能在距离Q远的高度图平面上（想想一个半径U以P为中心的球：它只接触R，而任何靠近P比R的点都必须在它里面。）所以当寻找比R更近的点时您可以限制自己只测试以Q为中心的（2U）x（2U）矩形的heightmap“像素”（或者实际上只测试以Q为中心的heightmap像素的radius-U圆盘——但这只节省了一个适度的常量比较因子，而且由于更复杂的循环条件，实际速度可能会慢一些）
警告：这不考虑每个高度图像素的4“侧墙”。例如，假设高地图像素的大小是1x1个单位，R的高度是5，P的高度是R的3个单位，R的左侧有一个高地图像素S的高度是100，而所有其他高地图像素的高度都是0：那么从P到高地图的最小距离可以被认为是1因为如果你从P开始，直接向左移动1个单位，你会碰到支持S的东“墙”，但是上面的算法会报告距离是3，因为它只考虑每个高地图像素的“顶边”，而S的顶边远远落后于P。
当P在远处时
在这种情况下，任何一个高地图点和P之间的角度起的作用较小；一个点是否接近P更多地取决于它的高度，而不是它的底部和高地图平面中Q之间的距离。因此，我建议保留一份按高度降序排列的高度图点副本然后，您可以按高度递减顺序计算P与此列表中每个点A之间的距离，停止一次高度（A）<高度（Q），因为列表中的任何剩余点B（其必然具有更低的高度）必须至少与P的距离和R的距离一样远，因为直线BP处于某个非零角度。
事实上，一个稍微复杂一点的停止标准是可能的：在浏览点列表的任何时候，你都可以中止这个过程，切换到检查所有的点，这些点在高度图平面中的基部比最近考虑的点更接近于q。假设你正在按高度递减的顺序浏览高度图点的列表，找到一个点a，它的底距Q有很小的距离D：那么到P最近的点要么是你迄今为止找到的最近的点或其在高地图平面中的基部与q的距离最大d的最近点。这可以通过搜索以q为中心的高地图像素的（2d）x（2d）网格来找到，类似于“当p接近高地图表面”下的情况。这在r恰好很深的情况下是有用的，否则将需要按降序检查几乎所有其他高度图点。当然，如果r是在一个宽而深的山谷中，那么需要很长时间才能找到任何足够接近的a，然后对每个或几乎每个点进行测试。