计算 3D 网格表面上两点之间最短路径的算法 [英] Algorithm to calculate the shortest path between two points on the surface of a 3D mesh
问题描述
我正在寻找一种算法来计算以下内容:
I am looking for an algorithm to calculate the following:
我有:
一个 3D 三角形网格.三角形不一定位于一个平面内.两个相邻三角形的范数向量之间的夹角小于 90 度.
A 3D triangle mesh. The triangles do not necessarily lie in one plane. The angle between the norm vectors of two neighbouring triangles is less then 90 degrees.
两点.这两个点位于三角形网格的边缘或网格的三角形内.
Two points. The two points lie either on an edge of the triangle mesh or inside a triangle of the mesh.
我需要计算代表网格上两点之间最短路径的折线.
I need to calculate the polyline which represents the shortest path between the two points on the mesh.
最简单和/或最有效的策略是什么?
What is the simplest and/or most effective strategy to do this?
推荐答案
就目前而言，您的问题没有明确定义；根据用于将线段投影"到网格上的方向，可以有多种解决方案.
As it stands, your problem is not well defined; there can be many solutions depending on the direction used to "project" the line segment onto the mesh.
选择投影方向后，将网格展平到与投影方向垂直的平面上.此时，您的网格是二维边(线段)的集合；只需确定每条边与目标线段的交点(如果有).
Once you have chosen the direction of projection, flatten the mesh onto a plane perpendicular to the direction of projection. At this point, your mesh is a collection of 2d edges (line segments); just determine the intersection (if any) of each edge with your target line segment.
编辑:
更新后的问题现已明确定义.由于我对原始问题(以上)的回答已被标记为已接受，大概这意味着下面评论中给出的信息实际上是更新问题真正被接受"的信息.我总结一下:
The updated question is now well defined. Since my answer to the original question (above) has been marked as accepted, presumably that means the information given in the comments below are actually what was really being "accepted" for the update question. I'll summarize:
- 谷歌搜索3d 网格上的最短距离"会找到一些相关信息，例如 三角网格上的最短路径近似
- 另请参阅:https://stackoverflow.com/a/10389377/294949 -- danh
这篇关于计算 3D 网格表面上两点之间最短路径的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
