在3D地形上,给定3D线,找到线和地形之间的交点
我有一个3D地形(x,y,z)网格,每个网格的每个坐标都是已知的.现在,我有一个单调增加/减少的线,其起点也是已知的.我想找到地形和线相遇的点.算法是做什么的？
我能想到的是将3D地形的坐标存储在nxn矩阵中.然后我会根据地形中的网格对线进行分段.然后我将从距离线最近的网格开始,然后尝试计算该平面是否与该线相交,如果是,则获取坐标并退出.如果不是,那么我将进入下一部分.
但我的算法是最好的还是最优的解决方案？或者是否有任何现有的库已经这样做了？
不是直接优化，只是一些提示：
如果您的网格很大，则可能值得根据地形构建八叉树，以便快速减少必须检查线路的网格节点的数量。这在巨大的网格（如 512*512 ndoes）中会更有效，因为只需要考虑光线穿过的叶节点。
此外，八叉树可用作通过检查哪些离开节点位于视锥体中来决定网格的哪些部分可见并因此必须绘制的方法。
但有一个问题：构建八叉树必须提前完成，需要一些时间，而且八叉树是静态的。它在构建之后就不容易修改，因为一个节点的修改可能会影响其他几个节点，而不一定是相邻的节点。
但是，如果您不打算在创建网格后对其进行修改，那么八叉树将会有所帮助。
更新
现在我了解了您计划如何存储网格，我相信空间分区将是找到相交线最近邻居的有效方法。
线性查找最近邻的运行时复杂度为 O(N)，而空间分区应用程序的平均运行时复杂度为 O(log N)。