regex - 体素空间上的正则表达式

Question

有没有一种方法可以像用regexp在一维字符串中宽松地描述模式一样，在3d体素网格中宽松地描述对象（例如，通过模式匹配有限自动机）？

假设我要描述一个由高度为3且宽度为5的，由“ B”或“ C”型体素组成的，具有较低刻面的“ A”型体素的长方体，并将此描述与体素字段匹配以找到图案示例。我可以进行一些搜索以寻找确切的模型（类似于Boyer-Moore-in-3D），但是我需要为某些对象指定可变尺寸（例如上述长方体的可变长度）。

Answer 1

正则表达式是一种紧凑的方式，用于表达有限（但仍然是无限）语言集的语法。使用正则表达式，您无需告诉在哪里寻找下一个符号，因为众所周知您正在处理一个字符串并对其字符进行迭代以将其作为语言的符号...但是在3D中，您将需要告诉要走的路。

您可以将其视为3D Turing机器，这是一种Turing机器，它具有内部状态并且可以从3D“磁带”中读取符号，因为我们只是在验证是否忽略写入磁带。然后，该图灵机将沿着3D“ tape”（即3D体素网格）行走，并将体素读取为符号，在读取每个符号后，图灵机的内部状态将根据某些定律发生变化。一旦执行结束，机器的最终状态就会告诉您是否匹配。现在，Von Newman体系结构中的这些定律是将磁带中的数据解释为指令，但是我们想要一种哈佛体系结构，即将指令与数据分开。现在，您想要的是一种描述图灵机这些说明的方法。 [您可以将其视为徽标的乌龟，但使用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

这描述了Turing机器正在寻找的东西，并通过回溯算法来测试所有可能的匹配，它将按预期工作。

请注意，我不知道这些体素的可能值集。也就是说，我不知道字母。因此，我仅以A型，B型，C型和D型为例进行说明，其中之一可能是无体素的表示，而其他可能是颜色或您使用的任何颜色。根据需要可以有多种类型的体素。如果体素类型复杂，则必须在此处插入其描述。

我一直在考虑这种语言的实际使用，很快就会出现一个问题，就是旋转，我必须确定在X轴上的三个体素类型A被视为在Z轴上的三个体素类型A是相同的，更好的是允许用语言来描述。

现在，如果体素是节点，则描述路径非常相似。我已经完成了一种语言来描述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轴。

匹配3x3的体素集，在平面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”为移动方向，可能可以通过末尾的数字推断含义最后，但我不知道这是否明确。

最后，这将匹配平面X，Y中由A型体素制成的任何有效俄罗斯方块：

(A1[X|Y]){4}

如果我们假设世界只是二维的，并且我们允许忽略第一，那么它可以简化为：

(A.){4}

我对此感到满意。不过，对于复杂的结构，您应该考虑使用更复杂，更紧凑和更易读的符号。

这就是我将正则表达式推广到两个，三个或三个以上维度的理论。

编辑：

如果体素的类型很复杂或引起歧义，我建议用尖括号“ <”和“>”来编写它，例如，您可以使用原始体素数据的十六进制值：

(<0088FF>.){4}