Curva da ordem Z.
Content
Valores de coordenadas
A figura abaixo mostra os valores z para o caso bidimensional com coordenadas inteiras 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (mostrado tanto em decimal quanto binário). A intercalação dos valores de coordenadas binárias (começando à direita com o x-bit (em azul) e alternando para a esquerda com o bit y (em vermelho)) produz os valores z binários (inclinados em 45 °, como mostrado). Conectar os valores z em sua ordem numérica produz a curva em forma de Z recursivamente. Os valores z bidimensionais também são chamados de quadky.
Os valores z das coordenadas X são descritos como números binários da sequência Moser-DE Bruijn, tendo bits diferentes de zero apenas em suas posições uniformes:
x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101}A soma e a diferença de dois valores X são calculadas usando operações bitwise:
x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101x[i−j] = ((x[i] & 0b01010101) − x[j]) & 0b01010101 if i ≥ jEssa propriedade pode ser usada para compensar um valor z, por exemplo, em duas dimensões, as coordenadas na parte superior (diminuindo y), inferior (aumento de y), esquerda (diminuindo x) e direita (aumentando x) do valor z atual z são:
top = (((z & 0b10101010) − 1) & 0b10101010) | (z & 0b01010101)bottom = (((z | 0b01010101) + 1) & 0b10101010) | (z & 0b01010101)left = (((z & 0b01010101) − 1) & 0b01010101) | (z & 0b10101010)right = (((z | 0b10101010) + 1) & 0b01010101) | (z & 0b10101010)E em geral para adicionar dois valores z bidimensionais W e Z:
sum = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)Construindo com eficiência quadtrees e octrees
A ordem z pode ser usada para construir com eficiência um quadtree (2d) ou octree (3D) para um conjunto de pontos. A idéia básica é classificar o conjunto de entrada de acordo com a ordem z. Uma vez classificados, os pontos podem ser armazenados em uma árvore de pesquisa binária e usados diretamente, que é chamada de quadtree linear, ou podem ser usados para criar um quadtree baseado em ponteiro.
Os pontos de entrada geralmente são dimensionados em cada dimensão para serem números inteiros positivos, como uma representação de ponto fixo sobre o intervalo de unidades [0, 1] ou correspondente ao tamanho da palavra da máquina. Ambas as representações são equivalentes e permitem que a mais alta ordem seja encontrada em tempo constante. Cada quadrado no quadtree tem um comprimento lateral que é uma potência de duas e coordenadas de canto que são múltiplos do comprimento lateral. Dados dois pontos, o quadrado derivado para os dois pontos é o menor quadrado que cobre os dois pontos. A intercalação de bits dos componentes X e Y de cada ponto é chamada de embaralhamento de x e y e pode ser estendida a dimensões mais altas.
Os pontos podem ser classificados de acordo com o shuffle sem intercalação explicitamente os bits. Para fazer isso, para cada dimensão, o bit mais significativo das coordenadas exclusivas ou das coordenadas dos dois pontos para essa dimensão é examinado. A dimensão para a qual a parte mais significativa é maior é usada para comparar os dois pontos para determinar sua ordem de embaralhamento.
O exclusivo ou operação mascara os bits de ordem superior para os quais as duas coordenadas são idênticas. Como o Shuffle intercala bits de ordem superior a ordem mais baixa, identificar a coordenada com a maior bit mais significativa, identifica o primeiro bit na ordem do shuffle que difere e que a coordenada pode ser usada para comparar os dois pontos. Isso é mostrado no seguinte código Python:
Uma maneira de determinar se o bit mais significativo é menor é comparar o piso do logaritmo base-2 de cada ponto. Acontece que a operação a seguir é equivalente e requer apenas operações exclusivas ou exclusivas:
Também é possível comparar números de ponto flutuante usando a mesma técnica. A função LESS_MSB é modificada para comparar primeiro os expoentes. Somente quando são iguais é a função LEST_MSB padrão usada nos Mantissas.
Depois que os pontos estão em ordem classificada, duas propriedades facilitam a construção de um quadtree: o primeiro é que os pontos contidos em um quadrado do quadtree formam um intervalo contíguo na ordem classificada. A segunda é que, se mais de um filho de um quadrado contiver um ponto de entrada, o quadrado é o quadrado derivado para dois pontos adjacentes na ordem classificada.
Para cada par de pontos adjacentes, o quadrado derivado é calculado e seu comprimento lateral determinado. Para cada quadrado derivado, o intervalo contendo é delimitado pelo primeiro quadrado maior à direita e à esquerda em ordem classificada. Cada um desses intervalos corresponde a um quadrado na quadtree. O resultado disso é um quadtree comprimido, onde apenas nós contendo pontos de entrada ou dois ou mais crianças estão presentes. Um quadtree não compactado pode ser construído restaurando os nós ausentes, se desejar.
Em vez de criar um quadtree baseado em ponteiro, os pontos podem ser mantidos em ordem classificada em uma estrutura de dados, como uma árvore de pesquisa binária. Isso permite que pontos sejam adicionados e excluídos no tempo O (log n). Dois quadtrores podem ser mesclados mesclando os dois conjuntos de pontos classificados e removendo duplicatas. A localização do ponto pode ser feita pesquisando os pontos anteriores e seguindo o ponto de consulta na ordem classificada. Se o quadtree for comprimido, o nó antecessor encontrado pode ser uma folha arbitrária dentro do nó de interesse compactado. Nesse caso, é necessário encontrar o antecessor do ancestral menos comum do ponto de consulta e da folha encontrada.
Use com estruturas de dados unidimensionais para pesquisa de faixa
Embora seja necessária bem preservação da localidade, para pesquisas eficientes de intervalo, um algoritmo é necessário para o cálculo, a partir de um ponto encontrado na estrutura de dados, o próximo valor z que está no intervalo de pesquisa multidimensional:
Neste exemplo, o intervalo que está sendo consultado (x = 2, ..., 3, y = 2, ..., 6) é indicado pelo retângulo pontilhado. Seu maior valor z (max) é 45. Neste exemplo, o valor f = 19 é encontrado ao pesquisar uma estrutura de dados no aumento da direção do valor z, para que tenhamos que pesquisar no intervalo entre F e Max (área hachurada ). Para acelerar a pesquisa, calcularia o próximo valor z que está no intervalo de pesquisa, chamado bigmin (36 no exemplo) e apenas pesquisou no intervalo entre Bigmin e Max (valores em negrito), pulando a maior parte do chocante área. A pesquisa em direção decrescente é análoga com o Litmax, que é o maior valor Z na faixa de consulta menor que o F. O problema do BIGMIN foi declarado primeiro e sua solução mostrada no TROPF e Herzog. Esta solução também é usada em UB-Trees ("GetNextz-Address"). Como a abordagem não depende da estrutura de dados unidimensional escolhida, ainda há uma escolha livre de estruturar os dados, métodos tão conhecidos, como árvores equilibradas, podem ser usadas para lidar com dados dinâmicos (em contraste, por exemplo, para as árvores R onde Considerações especiais são necessárias). Da mesma forma, essa independência facilita a incorporação do método nos bancos de dados existentes.
A aplicação do método hierarquicamente (de acordo com a estrutura de dados em questão), opcionalmente, tanto na direção crescente quanto na diminuição, produz pesquisas de faixa multidimensional altamente eficientes, o que é importante em aplicações comerciais e técnicas, por exemplo como um procedimento subjacente às pesquisas mais próximas dos vizinhos. A ordem Z é um dos poucos métodos de acesso multidimensional que chegaram aos sistemas comerciais de banco de dados (Oracle Database 1995, Transbase 2000).
Até 1966, a G.M.Morton propôs a ordem Z para sequenciamento de arquivos de um banco de dados geográfico bidimensional estático. As unidades de dados da área estão contidas em um ou alguns quadros quadráticos representados por seus tamanhos e valores Z do canto inferior direito, os tamanhos que estão em conformidade com a hierarquia da ordem Z na posição da esquina. Com alta probabilidade, mudar para um quadro adjacente é feito com uma ou algumas etapas de varredura relativamente pequenas. [Citação necessária]
Estruturas relacionadas
Como alternativa, a curva de Hilbert foi sugerida, pois possui um melhor comportamento de preservação da ordem e, de fato, foi usado em um índice otimizado, a geometria S2.
Formulários
where x {\displaystyle x} 
and y {\displaystyle y} 
both belong to the Moser–de Bruijn sequence, and the Z-order curve that connects the sums in numerical orderÁlgebra Linear
O algoritmo de Straassen para multiplicação de matrizes é baseado na divisão das matrizes em quatro blocos e, em seguida, dividindo recursivamente cada um desses blocos em quatro blocos menores, até que os blocos sejam elementos únicos (ou mais praticamente: até atingir matrizes tão pequenas que o moser -dé O algoritmo trivial da sequência de Bruijn é mais rápido). Organizar os elementos da matriz na ordem Z melhora a localidade e tem a vantagem adicional (em comparação com a ordem de remar ou colunas) que a sub-rotina para multiplicar dois blocos não precisa saber o tamanho total da matriz, mas apenas os Tamanho dos blocos e sua localização na memória. O uso eficaz da multiplicação de Straassen com a ordem Z foi demonstrado, consulte o artigo de Valsalam e Skjellum em 2002.
Buluç et al. Apresente uma estrutura de dados da matriz esparsa que acorde seus elementos diferentes de zero para ativar a multiplicação de vetor de matriz paralela.
Mapeamento de textura
Alguns mapas de textura da loja de GPUs na ordem Z para aumentar a localidade espacial de referência durante a rasterização mapeada de textura. Isso permite que as linhas de cache representem ladrilhos retangulares, aumentando a probabilidade de que os acessos próximos estejam no cache. Em uma escala maior, também diminui a probabilidade de caro, chamado "quebra de página" (ou seja, o custo das mudanças de linhas) em sdram/ddram. Isso é importante porque a renderização 3D envolve transformações arbitrárias (rotações, escala, perspectiva e distorção por superfícies animadas).
Esses formatos são frequentemente referidos como texturas swizzed ou texturas giradas. Outros formatos de azulejos também podem ser usados.
Problema n-corpo
O algoritmo Barnes-Hut requer construção de uma árvore de outubro. Armazenar os dados como uma árvore baseada em ponteiro requer muitas desreferências de ponteiro seqüencial para iterar sobre o OCT-Tree em profundidade em primeiro lugar (caro em uma máquina de memória distribuída). Em vez disso, se alguém armazenar os dados em uma hashtable, usando o hash da OCT-Tree, a curva da ordem Z naturalmente itera a OCT-Tree em profundidade em primeiro lugar.