Z-Index mit Beschränkungen außerhalb der Grenzen

Question

Ich muss den Z-Index (Morton) eines Punktes auf einer Ebene von seinen 2 Koordinaten x, y berechnen.

Traditionell wird dies nur durch das Bit-Interleaving gelöst.

Allerdings habe ich Grenzen, und ich möchte, dass der Z-Index des Punktes nur die Mortonanzahl erhöht, wenn sie sich innerhalb des aktiven Bereichs befindet, und die Zählung überspringen, wenn sie draußen ist.

Um klar zu sein, die typische z Ordnung in einem 4x4-Quadrat ist:

| 0 1 4 5 | 
| 2 3 6 7 | 
| 8 9 12 13 | 
| 10 11 14 15 | 

Allerdings, wenn ich einen 3x3 aktiven Bereich haben, möchte ich den Index wie folgt berechnet werden:

| 0 1 4 x | 
| 2 3 5 x | 
| 6 7 8 x | 
| x x x x | 

Wie Sie sehen können, ist das 00-11 Quad voll, das 02-13 überspringt die Anzahl der 2 Punkte, die außerhalb des aktiven Bereichs liegen, gleich für 20-31 und für 22-33.

Wichtig: Ich möchte dies ohne Iteration tun.

Gibt es eine bekannte Lösung für dieses Problem?

Answer 1

konnte ich Antwort auf die Frage auf https://fgiesen.wordpress.com/2009/12/13/decoding-morton-codes/

zu behandeln rechteckige Bereiche bekommen, runden alle Dimensionen auf die nächste Potenz von 2 und linear Hauptachse packen.

Zum Beispiel endcoding Punktes (2,3) in 5x4 Rechteck wie folgt,

Aufrunden 5x4 zur nächsten Potenz von 2 Ergebnissen in 8x4 dh 3 und 2 Bits

Encoding Punkt 2,3 Zuerst verschachteln wir 2 Bits von 0b010, 0b11 erhalten wir 0b1110, und das dritte Bit von der x-Dimension wird das fünfte Bit des Ergebnisses.

Encoding 4,2, 0b100 wird 0b11 0b11010

Um z-Reihenfolge der 3x3-Bereich zu finden, die inverse Zuordnung für 4x4-Region unter Verwendung des oben Umkehrung der obigen Verfahren beim Generieren Karte keine Punkte überspringen, die fallen außerhalb 3x3 Region.

Mapping würde aussehen wie

(0,0) -> (0,0) 
(0,1) -> (1,0) 
(0,2) -> (0,1) 
(0,3) -> (1,1) 
(1,0) -> (2,0) 
(1,2) -> (2,1) 
(2,0) -> (0,2) 
(2,1) -> (1,2) 
(3,0) -> (2,2) 

Python-Code könnte nützlich sein, https://gist.github.com/kannaiah/4eb936b047a987b32555b2642a0979f7