5

正規表現を使用して 1 次元の文字列のパターンを大まかに記述できるのと同じ方法で、3D ボクセル グリッドでオブジェクトを大まかに記述する方法はありますか (パターン マッチング有限オートマトンなどを介して)。

高さ 3、幅 5 の「B」または「C」タイプのボクセルで構成された下部ファセットを持つ「A」タイプのボクセルの立方体を記述し、この記述をボクセル フィールドに一致させてパターンの例を見つけたいとします。正確なモデル (Boyer-Moore-in-3D のようなもの) を検索することはできますが、一部のオブジェクトに対して可変寸法を指定する必要があります (前述の立方体の可変長など)。

4

2 に答える 2

5

正規表現は、限定された (そして無限の) 一連の言語の構文を表現するためのコンパクトな方法です。正規表現では、次の記号を探す場所を指定する必要はありません。これは、文字列を処理していて、その文字を言語の記号として反復処理していることがわかっているためです... しかし 3D では、進むべき道を告げる必要があります。

これは 3D チューリング マシンと考えることができます。これは内部状態を持ち、3D「テープ」からシンボルを読み取ることができるチューリング マシンです。テープへの書き込みを無視して確認しているだけなので。次に、このチューリング マシンは、3D ボクセル グリッドとも呼ばれる 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 を挙げましたが、そのうちの 1 つはボクセルのない表現であり、他のものは色や使用しているものである可能性があります。ボクセルのタイプは必要な数だけ存在できます。ボクセルのタイプが複雑な場合、その説明をそこに挿入する必要があります。

私はこの種の言語を実際に使用することを考えていましたが、非常にすぐに発生する問題の 1 つは回転です。それを言語で記述できるようにする方がよいでしょう。

ボクセルがノードである場合、パスを記述することは非常に似ています。プライベート プロジェクトの一部として 2D パスを記述する言語を作成しました (データベースに格納するために、図を参照してください...)。非常に単純です。 、すべての方向に文字を予約し、ステップに番号を使用します。たとえば、「2d5l1u」です。3D についても同じことを行い、グループ化して一致させる方法を追加します。ローテーションの問題を解決するには、方向を拡張して、選言が一致の代替構成を表現できるようにする必要があります。これは、私が考えたことがどのように機能するかのいくつかの例でより明確になります(私はEBNFまたは同様の形式の構文を使用していません):

X 軸上の 3 つのボクセル タイプ A のラインを一致させる:

(A1X){3}

ここでは、一致する「A」を動き「1X」に挿入し、括弧「(」と「)」をグループ化に使用し、中括弧「{」と「}」を使用して数量化します。これは次のように展開されます。

A1XA1XA1X

最後の「1X」は結果に影響しないため、次のようにすることもできます。

A1XA1XA

そして、それは明確に言っています: タイプ A ボクセルを一致させ、X の上に 1 を移動し、タイプ A ボクセルを一致させ、X の上に 1 を移動し、タイプ A ボクセルを一致させます。

X 軸または Z 軸上の 3 つのボクセル タイプ A のラインを一致させる:

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

別：

(A1[X|Z]){3}

ここでは、角かっこ「[」と「]」を使用して「クラス」を作成します。その場所は、方向に関するものであり、可能な軸のみが含まれていることを示しています。混同しないでください。

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

これはタイプ A の 3 つのボクセルに一致しますが、それらは同じ軸上にない可能性があります。それらは連続していて、X 軸または Z 軸のいずれかを隣接するものと共有する必要があるだけです。

平面 X、Y 上のボクセル タイプ a の 3x3 セットのマッチング:

(((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}

世界が 2 次元のみであり、1 を無視できると仮定すると、次のようになります。

(A.){4}

そして、私はそれに満足しています。それにもかかわらず、複雑な構造については、より複雑でコンパクトではなく、より読みやすい表記法を検討する必要があります。

これが、正規表現を 2 次元、3 次元、またはそれ以上の次元に一般化するための私の理論です。

編集：

ボクセルのタイプが複雑であるかあいまいな場合は、角かっこ「<」と「>」を使用して記述することを提案します。たとえば、生のボクセル データの 16 進値を使用できます。

(<0088FF>.){4}
于 2012-01-09T04:20:28.713 に答える
2

3D やボクセルについてはよくわかりませんが、マークアップを使用して 3D 空間を 1 次元表現に変換できれば、正規表現を使用できます。

簡単な例:

青い面、赤い面、緑の面、およびその他の 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>

正規表現は、境界を共有する同じキューブ内の面を探すことができます。正規表現はテキストで最もよく機能するため、最初のステップはテキストに「フラット化」する方法を見つけることです。

于 2011-12-22T20:03:36.537 に答える