Funksjonsnedsatte og døve

1)

O cálculo das intersecções para uma célula do detetor pode ser visto como um raio que atravessa a região de interesse com origem no foco e destino no detetor, como foi visto na secção 3.4 (Figura 3.6). Actualmente são calculadas todas as intersecções possíveis, mesmo que estas estejam fora da região de interesse. Um raio, por norma, descreve o mesmo caminho, entra na região de interesse e a certa altura sai da mesma. As intersecções são calculadas por ordem, por isso, caso se obtenha uma intersecção fora da região de interesse, é possível deduzir que as próximas intersecções estão fora da mesma e que não vão ser utilizadas no resto do cálculo da matriz. Com este método, temos a vantagem de encurtar o ciclo do cálculo das intersecções de um eixo e de evitar calcular intersecções que mais tarde não iam ser utilizadas. Não estamos a adicionar carga ao algoritmo ao verificar se cada intersecção está dentro da região de interesse, porque isso teria que ser feito durante ou depois de calcular as intersecções.

2)

O segundo detalhe é que a carga imposta ao algoritmo de ordenação pode ser diminuída, onde a implementação anterior usava a biblioteca de ordenação do próprio C++. Em cada ciclo do cálculo das distâncias (cada ciclo é responsável por uma célula do detetor), se ordenarmos as intersecções da célula em questão, conseguimos obter na mesma o resultado da Figura 4.1. Isto porque, como sabemos a célula actual, podemos guardar os resultados ordenados dessa célula. Desta maneira o que fazemos é ordenar os resultados parciais para cada célula, sendo que no fim obtemos da mesma forma os resultados ordenados pela célula. Com este método, são ordenadas na mesma N inter- secções, com a diferença de não ser necessário ordenar pela célula, isto porque as inter- secções já são obtidas ordenadas pela célula (inicio na célula 0 até célula M, em que M representa o número de células).

3)

Após uma interpretação mais exaustiva na obtenção das intersecções para cada um dos três eixos (x, y e z), foi possível constatar que os resultados podem ser adquiri- dos de forma ordenada (por x, nomeadamente).

Tal como foi referido na explicação do cálculo da matriz sistema (secção 3.4), pa- ra cada célula, necessitamos de encontrar todas as intersecções para os três eixos (x, y e

62

z). Segue-se uma explicação sobre as características de cada plano que permitem esta ordenação por x.

Eixo X

Neste eixo, o que vamos incrementando é a coordenada X, se começarmos na célula do detetor e formos avançando para o foco, os resultados estarão sempre ordenados pela coordenada X (Figura 4.2, seta 1).

Eixo Y

A identificação da ordenação neste eixo é semelhante ao eixo X. Se a coordenada Y da célula do detetor for inferior à coordenada Y do foco, calculamos as intersecções in- crementando a coordenada Y a partir da célula e com destino no foco (Figura 4.2, seta 1). Caso contrário, se a coordenada Y da célula do detetor for superior ou igual à coor- denada Y do foco, calculamos as intersecções decrementando a coordenada Y a partir da célula e com destino no foco (Figura 4.2, seta 2). Em ambos os casos as intersecções são obtidas ordenadas pela coordenada X.

Eixo Z

Só necessitamos de calcular as intersecções para uma das metades da dimensão x, co- mo foi explicado na secção 3.4. A metade escolhida é a que vai desde a posição 0 → 𝐷𝑒𝑡𝑒𝑡𝑜𝑟𝐷𝑖𝑚𝑥⁄ . Desta forma, podemos obter as intersecções ordenadas começando 2 na célula do detetor e incrementar a coordenada Z até chegar ao foco. Os resultados vêm ordenados pela coordenada X, como pode ser verificado pela seta 3 na Figura 4.2 b).

Figura 4.2: a) Posição do foco no eixo xy b) Posição do foco no eixo xz [1].

A maior parte dos algoritmos de ordenação comportam-se de maneira diferente para diferentes tipos de distribuição de dados. Os dados podem estar distribuídos aleatori-

63

amente, parcialmente ordenados, invertidos ou com poucas ocorrências únicas (Figura 4.3). É difícil escolher o algoritmo certo quando não sabemos como é que os dados vêm ordenados, por isso os algoritmos usados pela biblioteca do C++ têm que ser genéricos e estáveis, fazendo aproximadamente 𝑁 ∗ 𝑙𝑜𝑔₂(𝑁) (em que N é o número de elementos) comparações entre os elementos e trocas entre eles até esse valor [28].

a) b) c) d)

Aleatório Parcialmente ordenado

Invertido _{Poucas ocorrências} únicas

Figura 4.3: Alguns exemplos de distribuição de dados que podemos encontrar.

Mas para este caso, já constatámos que os dados podem ser obtidos parcialmente ordenados, ou seja, ordenados pela coordenada X em cada plano. Só que o objectivo final é ter todas as intersecções ordenadas pela coordenada X, independentemente do seu eixo. É então que surge a possibilidade de criar um algoritmo de ordenação adap- tado para este problema.

64

4)

Algoritmo de ordenação adaptado

Para conseguir aplicar este algoritmo, é necessário saber o número de intersecções em cada eixo. Já se sabe que as intersecções estão ordenadas pela coordenada X em cada eixo, assim o algoritmo pode ser dividido nas seguintes etapas (Figura 4.4):

1) Para cada eixo, escolher a intersecção com o valor da coordenada X mais baixo. Como as intersecções já estão ordenadas pela coordenada X basta escolher a pri- meira intersecção de cada eixo.

2) Escolher o eixo com o valor da coordenada X, da intersecção, mais baixo. Para tal, basta fazer o mínimo entre as três coordenadas (Min(x,y,z)).

3) O valor mínimo do eixo que foi escolhido na etapa anterior é copiado para uma nova célula (célula com a ordenação final).

4) Para o eixo que foi escolhido, se existirem mais intersecções, avançar para a pró- xima, caso contrário o plano já não é usado para a escolha do próximo valor mí- nimo.

65

5) Se ainda existirem elementos em pelo menos um eixo, voltar para o passo 2), caso contrário, obtemos a nova célula ordenada e termina o ciclo.

O que permite a utilização deste algoritmo é o conhecimento da estrutura dos dados para cada célula. Apesar do número de intersecções variar entre as células do detetor, a sua estrutura é sempre a mesma. Cada eixo (x, y e z) tem as intersecções or- denadas pela coordenada X. Os algoritmos de ordenação genéricos têm que funcionar para todos os casos e não tiram partido do conhecimento da estrutura dos dados. No máximo são realizadas 𝑁 comparações e 𝑁 cópias, em que 𝑁 é o número de intersec- ções da célula (soma das intersecções do plano x, y e z).

A Figura 4.5 mostra o esquema do programa sequencial atendendo ao que foi di- to anteriormente.

CPU

Figura 4.5: Esquema do programa sequencial executado num único core do CPU.

Início Cálculo das intersecções Cálculo das distâncias Calcular distância entre duas intersecções consecutivas Calcular voxel associado à distância calculada

Para cada par de intersecções

Determinar intersecções com eixo X, Y e Z Apagar intersecções fora da região de interesse Ordenar intersecções pela coordenada X

Para cada célula do detetor

Guardar intersecções do

vector final ordenado

66