Espressione regolare su spazio voxel

Question

Esiste un modo per descrivere in modo approssimativo un oggetto (tramite la corrispondenza di modelli di automi finiti, ad esempio) nella griglia di voxel 3d allo stesso modo in cui possiamo descrivere in modo approssimativo i modelli nella stringa monodimensionale con espressione regolare?

Diciamo che voglio descrivere un cuboide di voxel di tipo "A" con facet inferiore composto da voxel di tipo "B" o "C" con altezza 3 e larghezza 5 e abbinare questa descrizione al campo voxel per trovare esempi di modello. Posso fare qualche ricerca per modelli esatti (tipo-di-come-Boyer-Moore-in-3D), ma ho bisogno di specificare dimensioni variabili per alcuni oggetti (come la lunghezza variabile per il cuboide sopra menzionato).

Answer 1

Non conosco molto del 3D o dei voxel, ma se riesci a trasformare il tuo spazio 3D in una rappresentazione unidimensionale utilizzando un markup, puoi usare una regex su di esso.

esempio semplificato:

Per un cubo con la faccia blu, viso rosso, faccia verde, e 3 altri non ci preoccupiamo:

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

tuo regex potrebbe cercare volti all'interno dello stesso cubo che condivide un confine. I regex funzionano meglio con il testo, quindi il tuo primo passo dovrebbe essere quello di trovare un modo per "appiattire" il testo.

Answer 2

Le espressioni regolari sono un modo compatto per esprimere la sintassi di un insieme di lingue limitato (e ancora infinito). Con le espressioni regolari non hai bisogno di dire dove cercare il prossimo simbolo, dal momento che è noto che stai lavorando su una stringa e iterando sui suoi personaggi portandoli come simboli della lingua ... ma in 3D tu farai bisogno di dire quale strada da percorrere

Potete pensarci come una macchina di Turing 3D, cioè una macchina di Turing che ha uno stato interno e può leggere simboli da un "nastro" 3D, dal momento che stiamo verificando solo ignorando la scrittura sul nastro. Quindi, questa macchina di Turing percorrerà il "nastro" 3D ovvero la griglia voxel 3D e leggerà i voxel come simboli, dopo aver letto ciascun simbolo, lo stato interno della macchina di Turing cambierà in base a determinate leggi. Una volta che l'esecuzione è finita, lo stato finale della macchina ti dice se è stata una partita o meno. Ora queste leggi in una Von Newman Architecture sono un'interpretazione dei dati del nastro come istruzione, ma noi vogliamo un'architettura di Harvard, cioè che le istruzioni siano separate dai dati. Ora quello che vuoi è un modo per descrivere quelle istruzioni per la macchina di Turing. [Puoi pensare a questo come alla tartaruga del Logo ma in 3D].

Seguendo lo spirito delle espressioni regolari preferiremmo un linguaggio che assomiglia alla struttura attuale. Se facciamo testo base che sarà un linguaggio descrittivo (perché un imperativo non è migliore di tuo Turing preferito completare uno), si dovrà dire per esempio (in inglese):

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 

Questo descrivono quello la macchina di Turing sta cercando, con un algoritmo di backtracking che test tutte le potenziali corrispondenze funzionerà come previsto.

Si noti che non conosco l'insieme di valori possibili dei voxel. Cioè, non conosco l'alfabeto. Quindi ho appena detto tipo A, tipo B, tipo C e tipo D come esempi, uno di quelli potrebbe essere la rappresentazione di nessun voxel, e gli altri potrebbero essere i colori o qualsiasi altra cosa tu stia usando. Ci possono essere tanti tipi di voxel secondo necessità. Se il tipo di voxel è complesso, la descrizione deve essere inserita lì.

Ho pensato a un uso pratico di questo tipo di linguaggio e un problema che si verifica molto rapidamente sono rotazioni, devo decidere che tre voxel di tipo A sull'asse X sono considerati uguali a tre voxel di tipo A sul Asse Z, meglio è permettere di descriverlo nella lingua.

Ora è molto simile descrivere un percorso se i voxel sono nodi, ho fatto un linguaggio per descrivere percorsi 2D come parte di un progetto privato (per memorizzarli in un database, andare in figura ...), è molto semplice, riserva un carattere per ogni direzione e usa un numero per i passi, ad esempio: "2d5l1u". Fare lo stesso per 3D e aggiungere un modo per raggruppare e abbinare farà. Per risolvere il problema di rotazione sarà necessario espandere la direzione per consentire alle disgiunzioni di esprimere configurazioni alternative per la partita. Questo sarà più chiaro su alcuni esempi di come potrebbe funzionare a cui ho pensato (non ho lavorato una sintassi formale in EBNF o simile):

Abbinare una linea di tre voxel di tipo A sull'asse X:

(A1X){3} 

Qui ho intercalare corrispondenti "a" con il movimento "1X", usare le parentesi "(" e ")" per il raggruppamento e le parentesi graffe "{" e "}" da quantificare. Questo si srotola a questo:

A1XA1XA1X 

L'ultima "1X" non influisce sul risultato, quindi potrebbe anche essere:

A1XA1XA 

E dice chiaramente: individua una di tipo A voxel, mossa 1 sulla X e abbina un voxel di tipo A, sposta 1 sulla X e abbina un voxel di tipo A.

corrispondenza di una linea di tre voxel tipo A nel corso degli assi X o l'asse Z:

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

Alternativa:

(A1[X|Z]){3} 

Qui uso parentesi "[" e "]" per rendere una "classe", la posizione di essa indica che riguarda la direzione e include solo l'asse possibile, non confondere con:

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

Questo corrisponderà a tre voxel di tipo A, ma potrebbero non essere sullo stesso asse, solo essere contigui e condividere l'asse X o l'asse Z con il vicino.

abbinabili una serie 3x3 di tipo voxel al di sopra del piano X, Y:

(((A1X){3})1Y){3} 

Questo corrisponde a una linea sull'asse X e le mosse 1 sopra l'asse Y per abbinare altro e così via. Implica che dopo aver raggruppato una ripetizione "([(A1X)] {16})" torniamo indietro al punto in cui la partita ha iniziato a eseguire la seguente mossa "1Y". Per srotolarlo sarebbe:

(A1XA1XA1X)1Y(A1XA1XA1X)1Y(A1XA1XA1X)1Y 

Guardate la parentesi rimanente, questi significa tornare indietro a dove è iniziata la partita. Quindi il programma controllerà cosa c'è all'interno del gruppo e quando sarà pronto tornerà dove si trovava prima di entrare nel gruppo e continuare ad eseguirlo.

corrispondenza di un paio di tipo voxel A separati da un voxel di tipo ignorato (su ogni asse): ""

A1(X|Y|Z).1(X|Y|Z)A1(X|Y|Z) 

Influenzato da espressioni regolari che usiamo il punto rappresentare qualsiasi tipo di voxel.

Non riesco ancora a decidere se è preferibile utilizzare valori negativi piuttosto che utilizzare altre lettere per altri assi, inoltre ritengo che il numero 1 possa essere facoltativo. Anche altre parti della sintassi delle espressioni regolari come "+", "*" e "?" deve essere seppur via più attentamente. Potrebbe essere utile applicare "{" e "}" per qualsiasi quantificazione fino a quando non sarà dimostrato che non c'è ambiguità.

Come si può avere notato che non sarà un problema per aggiungere un'altra direzione di movimento o interamente un altro asse, quindi questo porta molto bene a dire quattro dimensioni, come in:

(A1[X|Y|Z|W]){3} 

Può anche essere buono da usare il punto "." per rappresentare qualsiasi direzione:

(A1.){3} 

C'è un problema con assumere qualsiasi direzione quando non specificato e che è che questo linguaggio è definito per identificare ciò che è una direzione e distinguerli dai tipi voxel base alla posizione all'interno della espressione. Quindi "(A1B1) {3}" non verrà mappato a "(A1.B1.) {3}" perché prenderà "B" come direzione di spostamento, potrebbe essere possibile dedurre il significato dal numero finale a Alla fine, ma non so se sarà inequivocabile.

Infine questo corrisponderà qualsiasi pezzo tetris valido nel piano X, Y fatta di tipo voxel A:

(A1[X|Y]){4} 

Se assumiamo che il mondo è bidimensionale solo e che consentono di ignorare il numero uno, si riduce a questo:

(A.){4} 

E sono contento di quello. Tuttavia, dovresti considerare una notazione più complessa, meno compatta e più leggibile per strutture complesse.

E questa è la mia teoria per generalizzare le espressioni regolari a due, tre o più dimensioni.

EDIT:

Se il tipo di voxel è complesso o provoca ambiguità propongo di scrivere con staffe angolari "<" e ">", così ad esempio è possibile utilizzare il valore esadecimale del greggio voxel data:

(<0088FF>.){4}