假设我想要描述具有下部小平面的“A”型体素的长方体,其由具有高度3和宽度5的“B”或“C”型体素组成,并且将该描述与体素场匹配以找到图案的示例.我可以搜索精确模型(类似Boyer-Moore-in-3D),但我需要为某些对象指定可变尺寸(如上述长方体的可变长度).
解决方法
您可以将其视为3D图灵机,即具有内部状态并可以从3D“磁带”读取符号的图灵机,因为我们只是验证让我们忽略写入磁带.然后,这个图灵机将3D“磁带”也称为3D体素网格并读取体素作为符号,在读取每个符号后,图灵机的内部状态将根据某些定律改变.一旦执行结束,机器的最终状态就会告诉您它是否匹配.现在,Von Newman架构中的这些定律是对磁带数据作为指令的解释,但我们需要哈佛架构,即指令与数据分离.现在你想要的是一种描述图灵机的指令的方法. [你可以把它想象成logo的龟,但是在3D中].
遵循正则表达式的精神,我们更喜欢一种类似于实际结构的语言.如果我们以文本为基础,它将是一种描述性语言(因为命令式语言并不比你最喜欢的图灵完整语言更好),它将不得不说(例如)(英语)：
There is a voxel type A and then moving (x1,y1,z1) from that there is a voxel of type B or C and then moving (x2,y2,z3) from that there is a voxel type D
这描述了图灵机正在寻找什么,使用回溯算法测试它将按预期工作的所有潜在匹配.
请注意,我不知道体素的可能值集.也就是说,我不知道字母表.所以我只是说类型A,类型B,类型C和类型D作为例子,其中一个可能是没有体素的表示,其他可能是颜色或你正在使用的任何东西.根据需要可以存在多种类型的体素.如果体素的类型很复杂,则必须在那里插入它的描述.
我一直在考虑实际使用这种语言,并且很快出现的一个问题是旋转,我必须确定在X轴上的三个体素类型A被认为是相同的三个体素A型在Z轴上,更好的是允许用语言来描述.
现在它非常类似于描述一个路径,如果体素是节点,我已经用一种语言来描述2D路径作为私有项目的一部分(将它们存储在数据库中,去图……),它非常简单,它为每个方向保留一个字符,并使用一个数字作为步骤,例如：“2d5l1u”.对3D做同样的事情并添加分组和匹配的方法就行了.为了解决旋转问题,有必要扩展方向以允许分离来表示匹配的替代配置.关于它如何工作我会想到的一些例子(我没有在EBNF或类似的工作中使用正式语法),这将变得更加清晰：
匹配X轴上的三个体素A的线：
(A1X){3}
在这里我插入匹配的“A”与移动“1X”,使用括号“(”和“)”进行分组,使用大括号“{”和“}”进行量化.这展开了：
A1XA1XA1X
最后一个“1X”不会影响结果,所以它也可能是：
A1XA1XA
它清楚地说：匹配A型体素,在X上移动1并匹配A型体素,在X上移动1并匹配A型体素.
在X轴或Z轴上匹配三个类型A的体素线：
(A1X){3}|(A1Z){3}
替代方案：
(A1[X|Z]){3}
在这里,我使用括号“[”和“]”来制作一个’类’,它的位置告诉它是关于方向的,它只包括可能的轴,不要混淆：
[(A1X)|(A1Z)]{3}
这将匹配三个类型A的体素,但它们可能不在同一轴上,它们只能是连续的并且与它相邻共享X轴或Z轴.
匹配一组3×3体素,在平面X,Y上键入a：
(((A1X){3})1Y){3}
这匹配X轴上的线和Y轴上的移动1以匹配另一个,依此类推.这意味着在对重复“([(A1X)] {16})”进行分组后,我们回溯到匹配开始执行以下移动“1Y”的位置.展开它将是：
(A1XA1XA1X)1Y(A1XA1XA1X)1Y(A1XA1XA1X)1Y
查看剩余的括号,这些意味着回溯到匹配开始的位置.因此程序将检查组内部的内容以及何时完成它将返回到进入组之前的状态并继续执行.
匹配一对类型A的体素,由忽略类型的体素(在任何轴上)分隔：
A1(X|Y|Z).1(X|Y|Z)A1(X|Y|Z)
受正则表达式的影响,我们使用点“.”代表任何类型的体素.
我仍然不确定使用负值是否比使用其他字母用于其他轴更好,我还认为数字1可以是可选的.正则表达式语法的其他部分,如“”,“*”和“？”我必须更谨慎.在证明没有歧义之前,对任何量化强制执行“{”和“}”可能是好的.
您可能已经注意到添加另一个移动方向或完全是另一个轴不会有问题,所以这个端口很好地说四个维度,如：
(A1[X|Y|Z|W]){3}
使用点“.”也可能是好的.代表任何方向：
(A1.){3}
在未指定时假设任何方向存在问题,并且该语言被定义为识别什么是方向并且基于表达式内部的位置将它们与体素类型区分开.所以“(A1B1){3}”不会映射到“(A1.B1.){3}”,因为它将“B”作为移动方向,有可能通过尾随数字来推断其含义.结束,但我不知道它是否会毫不含糊.
最后,这将匹配由A型体素制成的平面X,Y中的任何有效俄罗斯方块：
(A1[X|Y]){4}
如果我们假设世界只是二维并且我们允许忽略第一个,那么它会减少到：
(A.){4}
我很高兴.然而,对于复杂的结构,您应该考虑更复杂,更紧凑和更易读的符号.
这就是我将正则表达式推广到两个,三个或更多维度的理论.
编辑：
如果体素的类型很复杂或引起歧义,我建议用尖括号“<”来写它.和“>”,例如,您可以使用原始体素数据的十六进制值：
(<0088FF>.){4}
