Trabalho Computação ED

CRIAÇÃO DE UMA KD TREE DE DUAS DIMENSÕES
Relatório da Primeira Etapa

1. DESCRIÇÃO DAS ATIVIDADES REALIZADAS :

Esta etapa do trabalho contou com a participação dos membros da equipe, os quais se reuniram para discutir ou resolver algumas questões do trabalho. Este trabalho foi feito na linguagem de programação Java, o que demandou algumas adaptações em estruturas apresentadas paraexibição dos pontos em tela. As tarefas foram divididas e delegadas a cada um dos membros, visando uma maior agilidade no desenvolvimento do trabalho. A divisão a seguir apresenta a participação de cada membro no trabalho:

Célio: Correção dos erros e melhoria na implementação dos métodos da etapa do trabalho; implementação das funções pedidas no trabalho; verificação, melhoria e correção de código;escrita do relatório;

Felipe: Verificação, melhoria e correção de código; realização de testes; escrita do relatório; implementação de código para exibir vizinhos em uma busca que não retornou um local.

Pedro: Apoio nas buscas relacionadas ao conteúdo do trabalho;


2. DESCRIÇÃO DAS PRINCIPAIS FUNÇÕES (MÉTODOS) IMPLEMENTADAS EM CADA CLASSE:

2.1 – Classe KDTRee:

Esta classe possui osmétodos de busca e contrução de uma kd tree.

private void verificaVizinhos(KdTreeNode raiz, double coordX, double coordY);

Esse método guarda os 3 vizinhos mais próximos a coordenada pesquisada pelo usuário.

É utilizado uma lista auxiliar global para armazenar os vizinhos. As 3 primeiras chamadas ao método já adicionam direto no vetor o nó, já que este possui posições livres. A partir daquarta chamada ao método é verificado se o candidato a vizinho possui distância menor que o vizinho de maior distancia armazenado.

É feito a ordenação dos vizinhos em relação a distancia para coordenadas de busca. O vizinho com maior distância será utilizado para comparação com o nó candidato. Caso o nó candidato possua a distancia menor que a do vizinho, o nó atual será inserido na lista nolugar do nó vizinho .

private void limpaDados:

Método para limpar as variáveis gloabais ao efetuar uma nova busca.

public KdTreeNode busca(KdTreeNode raiz, double coordX, double coordY, int profundidade);

Esta função é a responsável por efetuar a busca binária pelo nó da classe KdTreeNode que possui as informações a latitude e longitude que serão comparadas comas coordenadas passadas .

O método de busca inicialmente efetua a verificação se a raiz passada é nula, caso seja o método não continua a sua execução e retorna nulo. Caso a raiz não seja nula é efetuada a verificação de qual coordenada deve ser comparada, isto é feito em relação a profundidade divindade pela dimensão (no nosso caso dimensão é 2), caso a divisão de resto zero será feito acomparação dos valores de longitude, caso contrario será feito a comparação com a longitude .

Após a verificação de qual coordenada deve ser comparada é realizado a verificação dos valores passados com o valor atual da raiz. Caso os valores sejam iguais as coordenadas passadas retorno o nó como sendo o nó procurado (Longitude = coodX e latitude = coordY).

Caso o valor das coordenadas não sejamiguais ao do nó raiz, é feito a verificação se a coordenada (de acordo com a coordenada escolhida para comparação) passada como parâmetro é maior ou igual que a coordenada do nó raiz. Caso seja é feito a buca na arvore da direita da raiz. Caso a coordenada seja menor ou igual que a coordenada do nó raiz,é feito a buca na arvore da esquerda da raiz. (foi utilizado como comparação o operando de“maior ou igual” e “menor igual” pois poderíamos ter o valores repetidos para uma coordenada X com Y distinto, e vice-versa)

A cada chamada do método busca é feito a chamada do método verificaVizinhos caso ocorra inssucesso da verificação das coordenadas com o nó atual. O método verificaVizinhos é responsável por verificar se o nó atual é um vizinho próximo a coordenada passada.

Caso...