3

我有一个 NxN 值的高度图。

我想找到，给定一个点 A（红点），它的 x 和 y 坐标是给定的（并且 z 从数据中已知，所以 A 是表面的一个顶点）一组位于圆周上的点圆心在 A 和半径 R 的圆是一个很好的近似圆形“布”（灰色）覆盖在数据点描述的假想表面上。

采样，我试图找到的点集之间的倒数距离，不需要是统一的，但我仍然想至少找到所有与网格边缘相交的点距离 A 为 R 的圆。

如何找到这组点？

这是一个已知问题吗？

带圆圈的 3d 高度图
（来源：keplero.com）

- 编辑

Jan 使用的假设是正确的：样本形成与 [0,0] 对齐的规则矩形或正方形网格（在 XY 平面中）。但我想考虑 Z 方向的位移来计算距离。您可以将高度图视为地形，并将我正在寻找的算法视为向探险者提供的指令，该指令仅在给定纬度或经度的路径上行驶，标记距离 A 为 R 的点。步行距离，这是考虑到到目前为止所做的所有 Z 位移。探险者也在山谷中攀爬和下降。

对此的简单算法将是这样的。我们知道给定 R，x 和 y 轴上的最大位移对应于完全平坦的表面。如果没有斜率，x,y 点都在边界正方形 Ax-R < x < Ax+r 和 Ay-R

此时，它将开始移动到靠近的单元格，因为如果周界进入网格的一个单元格的边缘，它也必须退出该单元格。

4

2 回答 2

1

我认为这将很难以精确的方式解决，所以我建议尝试直接的方法来模拟你的探险者将在表面上采取的路径。

给定您的起点A和行进距离d，计算PXY 平面上d从A.

对于 中的每个点p，P将线段A-p与您的网格相交，以便最终得到探险者从一个网格正方形穿过到下一个网格正方形的一系列点，如果探险者从 出发，就会发生这种情况A。然后应该通过从您的网格数据中插值来为这些点提供 z 坐标。因此，您可以通过此点序列前进并跟踪到目前为止的行进距离。最终将达到目标距离 - 调整p到这一点。

P 现在包含您要查找的周长。P根据您的需要调整样本保真度（大小）。

于 2012-11-30T13:01:14.740 回答
0

只是为了澄清-您在 3d 中有一个三角形表面，对于Vi网格中的给定起始顶点，您希望找到U可通过长度为 的表面（即测地线）的路径到达的顶点集Li <= R。

一种方法是将其转换为基于图形的问题：

  1. 形成加权无向图G(V,E)，其中V是三角曲面网格中的顶点集，E是该网格中的边集。边权重应该是每条边的欧几里得（3d）长度。该图是离散距离图 - 网格中每个相邻顶点之间“沿表面”的距离。
  2. 从起始顶点运行Dijkstra算法的变体Vi，仅扩展长度Li满足约束的路径Li <= R。访问的顶点集U将是那些可以通过最短（测地线）路径到达的顶点Li <= R。

这种方法的精度应该与表面网格的分辨率有关——只要每个单元内的表面曲率不太高，欧几里得边长应该是实际测地距离的良好近似值，如果不是，表面网格应该在这方面进行改进。

希望这可以帮助。

于 2012-11-26T21:24:36.080 回答