18

我有以下格式的二维高度图

06 36 39 42 43 55 ... 
37 40 43 43 45 46 ...
40 43 44 45 46 48 ...
44 44 46 47 48 50 ...
41 44 45 47 48 48 ...
...

而且我需要将其重新映射为基于 grin 的轮廓格式（因此它可以进一步映射到精灵中）

. . . . | . . 
. . . . \ . . 
. . . / / . . 
. . . | . . . 
. . . | . . . 
. / - / . . .

这里.的意思是平坦的区域，|笔直-的悬崖/和\悬崖角落（每个代表两种不同的可能性）。

我尝试了标准的行进广场方法，但​​发现仅对 3 个邻居进行抽样会导致很多问题，因为相邻案例超载。（注意下面额外的不合适的直悬崖）

. . . . | . \ 
. . . . \ \ .
. . . / / - .
. . . | - . .
. . . | . . .
. / - / . . .

我想要的是对有助于处理这类事情的算法/方法的一些参考。我知道带有某种深度优先搜索的轮廓行走是一种选择，但尚未尝试过，并且宁愿将其作为最后的手段。还有一些特征的表示问题，例如是否包括 1 个元素厚的悬崖脊或忽略它们。另一种选择是通过生成的轮廓并更改它们，以便它们平滑地组合在一起，但这看起来真的很hacky......

4

1 回答 1

1

创建一个插值/最佳拟合函数。您的模型应该是一个 2D 多项式（在x和中y），其度数“恰到好处”：不要太高以免过度拟合所有内容，但不要太低以免丢失细节。

您现在有了一个可以切片的数学函数，通过设置f(x,y) = height. 这个方程的解是等高线。您现在有两个选择，具体取决于您是否可以解析求解。

  • 假设您无法解析求解，您仍然可以轻松地找出曲线的近似值：
    • 首先将网格着色为白色 iff(x,y)>height和黑色 if f(x,y)<height。注意在大约 <1 格内有黑白过渡的所有“过渡”区域：这些是轮廓所在的正方形。
    • 随机选择一个过渡方块，并在大致 <1 的网格半径内搜索f(x,y)==height，以在轮廓上找到一个点。在那个点（不一定在网格上），我们计算梯度∇f(x,y) = (∂f/∂x, ∂f/∂y)（“上坡向量”）。我们在任一方向将其旋转 90 度(∂f/∂y, -∂f/∂x)：：这种方式沿轮廓指向。我们非常缓慢地（步长比网格小得多）跟踪轮廓。这将把我们带到一个轮廓周围。
    • 在此跟踪期间，每次通过网格框时，我们将其标记为 {|,-,/,}，具体取决于梯度的平均值所指向的方向。（我们还必须给邻居贴上标签，就.好像它们还没有贴上标签一样；见 [*]。）
    • 请注意，在那之后可能仍然有过渡网格框！例如，如果你有两个山丘，你将填充一个圆圈，但轮廓是两个圆圈。在另一个随机（未标记）“过渡”网格框上重复上述过程（这就是我们需要 [*] 的原因，否则我们可能会关注我们已经考虑过的点的邻居）。重复直到没有更多未标记的“过渡”网格框。
    • height为您希望绘制为轮廓的每个级别执行此操作，然后您就完成了。
  • 您可能能够像处理圆锥曲线一样进行分析求解，但这可能不太可能并且超出了此问题的范围。如果你可以解决曲线，你可以使用各种技术“网格化”它（例如参数化它，然后使用可能半格的步长沿着轮廓行走，注意最近的邻居）

（如果一个轮廓与另一个轮廓重叠，则轮廓高度之间的间距太小。如果您对给定轮廓不满意，则可能性集 {-,|,/,} 太小。）

于 2012-04-06T03:32:26.587 回答