在3D高度图上找到一组装点的圆圈
我有一个NxN值的高度图。
我想找到给定的A点（红点），其中给出了x和y坐标（并且从数据中知道z，因此A是曲面的顶点），位于圆周上的一组点以A和半径R为中心的圆形，这些圆形布料（灰色）很好地贴在数据点描述的假想表面上。
采样，我试图找到的一组点之间的相互距离不需要是均匀的，但是我仍然希望至少找到所有网格边缘与网格边界相交的点在距离A的距离R处旋转。
如何找到这一组点？
这是一个已知的问题吗？
三维高度贴图覆盖圆圈http://www.keplero.com/upps/grid.jpg
- 编辑
Jan使用的假设是正确的：样本形成一个规则的矩形或正方形网格（在XY平面中）与[0,0]对齐。 但我想考虑Z方向上的位移来计算距离。 您可以将高度图看作一个地形，并且我正在寻找的算法是给予一个探测器的算法，该探测器仅在具有经度或纬度的路径上行驶，标记距离A的距离为R的点。步行距离，这是考虑到迄今为止完成的所有Z位移。 探险家也在山谷中爬下来。
这个简单的算法就是这样的。 我们知道给定R，x和y轴上的最大位移对应于完全平坦的表面。 如果没有斜率，则x，y点将全部位于边界平方Ax-R <x <Ax + r和Ay-R
此时，它将开始行进到关闭单元格，因为如果周界进入网格的一个单元格的边缘，则它也必须退出该单元格。
为了澄清 - 您在三维中具有三角形曲面，并且对于网格中给定的起始顶点Vi ，您希望找到可通过长度为Li <= R的表面上的路径（即测地线）到达的一组顶点U 。
一种方法是将其转换为基于图形的问题：
G(V,E) ，其中V是三角网格表面网格中的顶点集合， E是该网格中边缘的集合。 边权重应该是每个边的欧几里德（3d）长度。 该图是离散距离图 - 网格中每个相邻顶点之间的“沿着曲面”的距离。 Vi运行Dijkstra算法的变体，只扩展长度为Li满足约束Li <= R路径。 顶点到达U的集合将是那些可以通过Li <= R的最短（测地线）路径到达的顶点。 这种方法的精度应该与表面网格的分辨率有关 - 只要每个单元内的表面曲率不太高，欧几里德边缘长度应该是对实际测地距离的良好近似，否则，表面网格应该在这方面进行完善。
希望这可以帮助。
我认为这将很难以确切的方式来解决，所以我建议尝试一下直接模拟你的探险家将在表面上采取的路径。
给定起点A和行程距离d ，计算XY平面上从A d的圆点P
对于每个点p在P ，相交线段Ap与你的网格，使你最终点的序列，其中的资源管理器从一个方格跨越到下的顺序，如果在资源管理器是会发生这种情况从A旅行。 这些点应该通过网格数据插值得到z坐标。 因此，您可以通过此点序列前进，并追踪到目前为止的行驶距离。 最终达到目标距离 - 将p调整到此时。
P现在包含您正在寻找的边界。 根据您的需要调整样本保真度（ P大小）。
上一篇: Find a set of points of a circle draped on a 3D height map