体素空间上的正则表达式

Question

有没有一种方法可以松散地描述 3d 体素网格中的对象（例如，通过模式匹配有限自动机），就像我们可以使用正则表达式松散地描述一维字符串中的模式一样？

假设我想描述一个“A”型体素的长方体，其下表面由“B”或“C”型体素组成，高度为 3，宽度为 5，并将此描述与体素字段相匹配以查找模式示例。我可以搜索精确模型（有点像 3D 中的 Boyer-Moore），但我需要为某些对象指定可变尺寸（例如上述长方体的可变长度）。

Answer 1

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

您可以将其视为一台 3D 图灵机，即一台具有内部状态并且可以从 3D“磁带”读取符号的图灵机，因为我们只是验证，让我们忽略对磁带的写入。然后，该图灵机将在 3D“磁带”（又名 3D 体素网格）上行走，并将体素读取为符号，读取每个符号后，图灵机的内部状态将根据一定的规律发生变化。执行结束后，机器的最终状态会告诉您是否匹配。现在，冯·纽曼架构中的这些定律是将磁带中的数据解释为指令，但我们需要哈佛架构，即指令与数据分离。现在您想要的是一种描述图灵机指令的方法。 [您可以将其视为 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 型体素被认为与 Z 轴上的三个 A 型体素相同，更好的是允许用语言来描述它。

现在，如果体素是节点，则描述路径非常相似，我已经编写了一种语言来描述 2D 路径作为私有项目的一部分（将它们存储在数据库中，想想看......），这非常简单，它为每个方向保留一个字符并使用数字表示步数，例如：“2d5l1u”。对 3D 进行同样的操作并添加分组和匹配的方式即可。为了解决旋转问题，有必要扩展方向以允许析取来表达匹配的替代配置。在我想到的一些关于它如何工作的示例中，这将变得更加清晰（我没有在 EBNF 或类似的形式中使用过正式语法）：

在 X 轴上匹配 A 型三个体素的线：

(A1X){3}

这里我插入匹配“A”移动“1X”，用括号“(”和“)”进行分组，用大括号“{”和“}”进行量化。这展开如下：

A1XA1XA1X

最后一个“1X”不会影响结果，所以它也可能是：

A1XA1XA

它清楚地说：匹配 A 型体素，在 X 上移动 1 并匹配 A 型体素，在 X 上移动 1 X 并匹配 A 型体素。

在 X 轴或 Z 轴上匹配 A 型三个体素的线：

(A1X){3}|(A1Z){3}

替代方案：

(A1[X|Z]){3}

这里我使用括号“[”和“]”来创建一个“类”，它的位置告诉它是关于方向的，并且它只是包括可能的轴，不要混淆：

[(A1X)|(A1Z)]{3}

这将匹配三个 A 型体素，但它们可能不在同一轴上，它们只需连续并与其邻居共享 X 轴或 Z 轴。

在平面 X、Y 上匹配一组 3x3 体素类型 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}

Answer 2

我对 3D 或体素了解不多，但如果您可以使用标记将 3D 空间转换为一维表示，那么您可以在其上使用正则表达式。

简化示例：

对于具有蓝色面、红色面、绿色面和其他 3 个我们不关心的面的立方体：

<object>
    <cube>
        <faces>
            <face orientation="up" color="blue">
                <border neighborOrient="west">
                <border neighborOrient="south">
            <face orientation="west" color="red">
            <face orientation="south" color="green">
            ...
        </faces>
    </cube>
</object>

您的正则表达式可以在同一立方体中查找共享边框的面。正则表达式最适合文本，因此您的第一步应该是找到一种“扁平化”文本的方法。