Find a set of points of a circle draped on a 3D height map
I have a height map of NxN values.
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.
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.
How to find this set of points?
Is this a known problem?
3d height map with circle draped http://www.keplero.com/upps/grid.jpg
-- edit
The assumption that Jan is using is right: the samples form a regular rectangular or square grid (in the XY 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.
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.
Just to clarify - You have a triangulated surface in 3d and, for a given starting vertex Vi in the mesh you would like to find the set of vertices U that are reachable via paths along the surface (ie geodesics) with length Li <= R .
One approach would be to transform this to a graph-based problem:
G(V,E) , where V is the set of vertices in the triangulated surface mesh and E is the set of edges in this mesh. The edge weight should be the Euclidean (3d) length of each edge. This graph is a discrete distance map - the distance "along the surface" between each adjacent vertex in the mesh. Vi , only expanding paths with length Li that satisfy the constraint Li <= R . The set of vertices visited U , will be those that can be reached by the shortest (geodesic) path with Li <= R . The accuracy of this approach should be related to the resolution of the surface mesh - as long as the surface curvature within each element is not too high the Euclidean edge length should be a good approximation to the actual geodesic distance, if not, the surface mesh should be refined in that area.
Hope this helps.
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.
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 .
For each of the points p in P , intersect the line segment Ap 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 now contains the perimeter that you're looking for. Adjust the sample fidelity (size of P ) according to your needs.
上一篇: 使用2D三边测量查找对象的位置
下一篇: 在3D高度图上找到一组装点的圆圈