在两条折线之间有最小面积的网格

Question

我有两条折线分别为v和u，分别在3D中有n和m顶点。我想连接v[0]到u[0],v[n-1]到u[m-1]，并且内部顶点也可以以某种方式获得具有最小表面积的三角形网格条。

我最初的解决方案是通过随后添加最小对角线来获得接近最佳的初始网格，然后在每个四边形中切换对角线（如果它产生更小的区域直到不再可能）。

但恐怕我可以在当地最低，而不是全球的结束。实现最小网格的更好选择是什么？

Answer 1

这可以通过动态程序来解决。

让我们想象的问题作为一个表，其中列表示第一折线的顶点和所述行表示第二折线的顶点：

0 1 2 3 ... n-1 -> v 
0 
1 
2 
... 
m-1 

每个小区表示折线之间的边缘。您从(0, 0)开始，并希望通过采取(+1, 0)或(0, +1)步骤来找到到(n-1, m-1)的路径。你所做的每一步都有一个成本（三角形的面积），并且你想找到导致最小成本的路径。所以你可以迭代地（仅仅是动态编程的风格）计算到达任何单元所需的成本（通过比较两个可能的入局方向的结果成本）。记住你选择的方向，最后你会有一个完整的最低成本路径。整体运行时间将为O(n * m)。

如果您知道您的顶点或多或少地分布得很好，您可以将表格的计算限制为靠近对角线的几个条目。这可以使运行时间降至O(k * max(n, m))，其中k是围绕对角线的可变半径。但是，如果假设顶点分布不成立，您可能会错过最佳解决方案。

你也可以采用类似A *的策略，只在你认为它可以属于最小路径时（在一些启发式的帮助下）计算一个单元格。