快速二维模式匹配

Question

考虑一个二维网格(平面中通常的网格).出于我的目的,模式或布置是将数字1和2分配给网格点的某个连接子集.例如,以下显示了三个单独的安排:

.......1.....1....
.222...2.....12...
.111...2.....2....
.222...22...12211.
.......1....11.1..

如果小图案可以旋转或反射,使得它的所有数字都小于较大图案中的数字,我说小图案匹配大图案.例如,考虑这种模式:

......
.1212.
....2.
......

它与上面最左边的排列不匹配,因为它无法旋转或反射以适合3x3的方格.它与中间排列相匹配,因为它可以旋转和反射以适合下方.然而,它不匹配最右边的布置,因为它被旋转或反射以适合最右边的布置,小图案中的数字大于大布置.(如果我的任何一个例子都不清楚或者您需要更多信息,请在评论区域提出请求.事先澄清一下:图案无法拉伸,也无法旋转,因此它与网格相对这意味着总共有四个旋转和四个反射,每个都可以被翻译.)

我想知道以下问题:

1. 如何快速测试小图案是否与大型布置相匹配？

2. 假设我有很多小模式.我能否以某种方式对它们进行预处理,以便快速判断它们中是否至少有一个符合排列？

我认为如果一个解决方案解决了更普遍的问题(比如任意数字 - 不仅仅是1和2 - 或允许断开连接的形状),它会很酷,但我真的只关心上面的情况.谢谢.

Answer 1

2D卷积.
(复杂度为n*Log(n),其中n为元素数)并且可能适用于较大的矩阵.

使两个矩阵匹配和不匹配相同的大小.

分别测试每个数字.示例 - cheking数k在serchung矩阵(更大)中设置数> = k on 0其他值on 1
在patteren矩阵中设置值<= k on 1 other set on 0

其中卷积的结果为0的是匹配和匹配

检查每次旋转和反射(总共8次)

这意味着一般的复杂性是k n log(n),其中k是数字的数量(在你的情况下是2)和n个更大矩阵的元素数量)