查找叠加在 3D 高度图上的圆的一组点 [英] Find a set of points of a circle draped on a 3D height map

问题描述

我有一个 NxN 值的高度图.

I have a height map of NxN values.

我想找到给定一个点 A(红点)，它的 x 和 y 坐标是给定的(z 是从数据中知道的，所以 A 是表面的一个顶点)位于的一组点在以 A 为中心、半径为 R 的圆的圆周上，这是一个很好的近似圆形布料"(灰色)，覆盖在数据点描述的假想表面上.

I would like to find, given a point A (the red dot), whose x and y coordinates are given (and z is known from the data, so A is a vertex of the surface) a set of points that lie on the circumference of the circle with center in A and radius R that are a good approximation of a circular "cloth" (in grey) draped on the imaginary surface described by the data points.

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

The sampling, the reciprocal distances between the set of points that I am trying to find, doesn't need to be uniform, but still I would like to find at least all the points that are an intersection of the edges of the mesh with the circle at distance R from A.

如何找到这组点?

这是一个已知问题吗?

_{(来源:keplero.com)}

-- 编辑

Jan 使用的假设是正确的:样本形成与 [0,0] 对齐的规则矩形或方形网格(在 X-Y 平面中).但我想考虑 Z 方向的位移来计算距离.您可以将高度图视为地形，而我正在寻找的算法是提供给探索者的指令，该指令仅在给定纬度或经度的路径上行驶，标记距离 A 距离为 R 的点. 步行距离，即考虑到迄今为止所做的所有 Z 位移.探险家也在山谷里爬上爬下.

The assumption that Jan is using is right: the samples form a regular rectangular or square grid (in the X-Y plane) aligned with [0,0]. But I would like to take the displacement in the Z direction into account to compute the distance. you can see the height map as a terrain, and the algorithm I am looking for as the instructions to give to an explorer that, traveling just on paths of given latitude or longitude, mark the points that are at distance R from A. Walking distance, that is taking into account all the Z displacements done so far. The explorer climbs and go down in the valleys too.

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

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

The trivial algorithm for this would be something like this. We know that given R, the maximum displacement on the x and y axis corresponds to a completely flat surface. If there is no slope, the x,y points will all be in the bounding square Ax-R < x < Ax+r and Ay-R

At this point, it would start traveling to the close cells, since if the perimeter enters the edge of one cell of the grid, it also have to exit that cell.

推荐答案

我认为这将很难以精确的方式解决，因此我建议尝试模拟探索者将采取的路径的直接方法表面上.

I reckon this is going to be quite difficult to solve in an exact fashion, so I would suggest trying the straightforward approach of simulating the paths that your explorers would take on the surface.

给定你的起点A和移动距离d，计算XY平面上的点P的圆d 来自 A.

Given your starting point A and a travel distance d, calculate a circle of points P on the XY plane that are d from A.

对于 P 中的每个点 p，将线段 Ap 与您的网格相交，这样您就可以得到一系列探索者从一个方格穿越到下一个方格的点，按照探索者从 A 行进时发生的顺序.然后应该通过网格数据的插值为这些点提供 z 坐标.因此，您可以在此点序列中前进并跟踪到目前为止行进的距离.最终将达到目标距离 - 将 p 调整到这一点.

For each of the points p in P, intersect the line segment A-p with your grid so that you end up with a sequence of points where the explorer crosses from one grid square to the next, in the order that this would happen if the explorer were travelling from A. These points should then be given a z-coordinate by interpolation from your grid data. You can thus advance through this point sequence and keep track of the distance travelled so far. Eventually the target distance will be reached - adjust p to be at this point.

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

P now contains the perimeter that you're looking for. Adjust the sample fidelity (size of P) according to your needs.

这篇关于查找叠加在 3D 高度图上的圆的一组点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！