java - 在 float[][] 中搜索 3D 图案

Question

我有一个浮点值数组，可以将其解释为灰度图像或 3D 表面(高度图)。 例如，它可能是一个 10x10 数组，如下所示:

0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 4 0 9 0 0 0 0 0
0 0 0 0 0 0 0 0 3 0
0 8 0 0 0 0 0 0 0 0
0 0 0 6 0 2 8 7 0 0
0 0 0 0 0 3 5 5 0 0
0 0 0 0 0 6 2 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

我正在寻找一个Java库(或有效的算法)来检测与引用模式类似的一个(或多个)模式的存在和位置，例如我想获取位置(5,5)作为无论我在寻找什么结果:

2 8 7
3 5 5
6 2 1

或:

3 8 6
3 6 5
5 2 3

有什么想法吗？

Answer 1

我不知道有什么 Java 库，但我认为编程不会太难。这个问题可以看作是子串问题的衍生问题，只不过你没有线性串。下面是一些可能非常接近的 Java 伪代码。

for(int x = 0; x < heightmap.width(); ++x)
    for(int y = 0; y < heightmap.height(); ++y)
        if(find_pattern(x, y))
            // YAY! pattern starts at (x, y)

// start at (x, y) and find an exact match
boolean find_pattern(int x, int y)
{
      for(int xx = 0; xx < pattern.width(); ++x)
          for(int yy = 0; yy < pattern.width(); ++x)
              if(heightmap[x + xx][y + yy] != pattern[xx][yy])
                  return false;
      return true; 
}

这将找到完全匹配的内容。如果你想要一些东西，比如加或减 2，那么你需要在 find_pattern() 中添加一些额外的逻辑，而不是 != 比较。

可能还有一些其他运行得更好的算法。这可能是最简单的编程。从复杂度来看，其运行时间为 O(n^2 * m^2):给定 n 是高度图的宽度和高度，m 是图案的宽度和高度。

注意:这不进行边界检查!

如果您实现边界检查，它将减少所需的比较次数，因为显然上述模式不能从高度图最右边的两列开始。有趣的是，当你进行边界检查时，复杂度会变为 O(n^2)，因为比率 n:m 变为 1:1 或 0:1