我有一个nxn值的高度图。
我想找到，给定一个点a（红点），它的x和y坐标是已知的（z是从数据中得知的，所以A是曲面的顶点）位于圆周上的一组点，中心位于半径A和半径R上，这是一个很好的近似圆的“布”（灰色），覆盖在由数据点描述的假想表面上。
采样，即我试图找到的一组点之间的倒数距离，不需要是均匀的，但我仍然希望找到至少所有的点，这些点是网格边缘与距离a距离r处的圆的交点。
如何找到这组点？
这是一个已知的问题吗？
（来源：keplero.com）
--编辑
jan使用的假设是正确的：样本形成一个与[0,0]对齐的规则矩形或正方形网格（在x-y平面上）。但我想考虑z方向的位移来计算距离。你可以把高度图看作是一个地形，我正在寻找的算法是给一个探险家的指令，这个探险家在给定纬度或经度的路径上行驶，标记距离a.Walking distance R处的点，这要考虑到目前为止所做的所有Z位移探险家也爬到山谷里去。
这个简单的算法是这样的。我们知道，给定R，X和Y轴上的最大位移对应于一个完全平坦的表面。如果没有坡度，则x，y点都在边界正方形Ax-R在这一点上，它将开始移动到封闭的细胞，因为如果周界进入网格的一个细胞的边缘，它也必须退出该细胞。
最佳答案
只是为了澄清-你有一个三维三角曲面，对于网格中给定的起始顶点Vi，你希望找到一组顶点U，这些顶点可以通过曲面上的路径（即测地线）到达，长度Li <= R。
一种方法是将其转换为基于图形的问题：
形成加权无向图，其中G(V,E)是三角化曲面网格中的顶点集，而V是该网格中的边集。边缘权重应该是每个边缘的欧几里德（3d）长度这个图是一个离散的距离映射-网格中每个相邻顶点之间的“沿曲面”距离。
从起始顶点运行Dijkstra's算法的变体，仅扩展满足约束E的长度Vi的路径。访问的顶点集Li，将是那些可以通过Li <= R的最短（测地线）路径到达的顶点集。
这种方法的精度应该与表面网格的分辨率有关——只要每个单元内的表面曲率不太高，欧几里得边缘长度应该是近似实际测地线距离的一个很好的近似值，如果不是，表面网格应该在该区域中细化。
希望这有帮助。
关于algorithm - 查找在3D高度图上叠加的圆的一组点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13561580/