将高度图映射到基于网格的轮廓格式

Question

我有以下格式的2D高度图

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的轮廓格式(因此它可以进一步映射到精灵)

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

这里.意思平坦区域,|和-直悬崖,/和\悬崖角(每一个代表2种不同的可能性).

我尝试了一种标准的行进方法,但发现只抽取3个邻居会导致相当多的问题,原因是相邻情况超载.(注意下面的额外不直的悬崖)

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

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

Answer 1

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

\n\n

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

\n\n

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

\n\n

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

\n