你有一个N维的标量成本函数，
\n\n\n\n\nf ( y 0 , y 1 , .., y N ) \xe2\x88\x8a \xe2\x84\x9d, y \xe2\x88\x8a \xe2\x84\x9d
\n
但仅在规则的矩形网格中采样，
\n\n\n\n\ny k = \xce\xa8 k + \xcf\x88 k x k，常数\xce\xa8 k \xe2\x88\x8a \xe2\x84\x9d 和\xcf\x88 k \xe2\x88\x8a \xe2\ x84\x9d，网格坐标x k \xe2\x88\x8a \xe2\x84\x95
\n
问题是找到等值面i ，
\n\n\n\n\nf ( y 0 , y 1 , ..., y N ) = C i
\n
直接的方法是循环遍历网格中的每个单元，并检查当前等值面是否与当前单元相交，如果是，则描述当前单元内等值面的部分。（行进立方体是描述等值面如何与每个网格单元相交的一种方法。）
\n\n这里的限制是使用基于邻域的搜索，而不是检查每个单元格。
\n\nOP 之前有一个专门针对 3D 情况的问题，我在其中发布了示例代码grid.h和grid.c的链接（在 Pastebin.com，因为它们太长而无法包含内联）。
\n\n该实现与 OP 的切片方法完全不同。我的方法是直接、简单地遍历与当前等值面相交的网格单元。它缓存网格样本，并使用单独的映射（char每个网格单元一个）来跟踪哪些网格单元已被缓存、遍历和/或推送到堆栈以便稍后遍历。这种方法很容易扩展到三个以上的维度。尽管代码是针对三个维度编写的，但该方法本身并不特定于三个维度；您需要做的就是调整数据结构以适应任何（合理的）维数。
等值面行走本身是微不足道的。您从等值面相交的任何网格单元开始，然后检查所有 2 N 个最近邻单元以查看等值面是否也与它们相交。在实践中，您使用要检查的网格单元位置堆栈和网格单元标志图来避免重新检查已检查的网格单元。
\n\n由于每个网格单元的网格点样本数量为 2 N，因此我的示例代码并不是最佳的：最终会评估许多附近的网格点，以查看相邻网格单元是否与等值面相交。（不是仅检查界定等值面的网格点，而是检查属于等值面周围任何网格单元的网格点。）随着N的增加，这项额外工作呈指数增长。
\n\n更好的方法是分别考虑 2 N个可能的 ( N -1) 面中的每一个，以避免检查等值面根本不相交的单元。
\n\n在N维规则矩形网格中，每个单元都是一个N维长方体，由顶点（角）处的 2 N个网格点定义。N个长方体单元具有N ( N -1)个二维面和2个N ( N -1)维面。
\n\n要检查每个 ( N -1) 面，您需要检查定义该 ( N -1) 面的 2 N -1 个网格点处的成本函数。如果这些点处的成本函数跨越等值面值，则等值面与 ( N -1) 面相交，并且等值面也与该方向上的下一个网格单元相交。
\n\n有两个 ( N -1) 个面垂直于每个轴。如果等值面与接近负无穷大的 ( N -1) 面相交，则等值面也与沿该轴朝负无穷大方向的下一个网格单元相交。类似地，如果等值面与接近正无穷大的 ( N -1) 面相交，那么它也会沿着该轴与正无穷大的下一个网格单元相交。因此，( N -1) 个面非常适合决定哪些相邻小区应该被检查或不被检查。这是正确的，因为 ( N -1) 面正是两个单元共享的网格点集。
\n\n我非常犹豫是否提供示例 C 代码，因为 3D 案例的相同方法的示例代码到目前为止似乎没有帮助任何人。我担心需要使用 2 维和 3 维示例图像进行更长的解释以进行说明，以易于理解的术语描述该方法；如果没有牢牢掌握逻辑，任何示例代码都看起来像官样文章。
\n| 归档时间： |
|
| 查看次数： |
230 次 |
| 最近记录： |