Fórum de discussão

Salve,

Aqui vão alguns comentários sobre o método

    // This method should return the k points that are closest to the query point (in any order);
    // return all N points in the data structure if N <= k.
    public Iterable<Point2D> nearest(Point2D p, int k) 

do EP08 KdTree.

Hoje implementei esse método. Achei tudo muito divertido. Assim, permitam-me compartilhar um pouco do processo tentando não ser um spoiler.

Eis os passos que segui.

Sotāpanna

Já havia implementado e testado toda a classe KdTreeST como exceção feita a esse método. Para testar usei inicialmente o meu unit-test do main(). Em seguida, testei os métodos através do RangeSearchVisualizer.java e o NearestNeighborVisualizer.java.

É muito bom imagens como a que estão a seguir para verificarmos visualmente se a solução força-bruta dada pela classe PointST e a solução usando a 2d-tree da classe KdTreeST estão de acordo.

Os pontos vermelho mostram o que a classe PointST pensa. Já os pontos em azul mostram a opinião da classe KdTreeST. É bom que as duas opiniões coincidam. Além disso, visualmente, é possível verificar se as coisas estão ok.

Para testar utilizei o conjunto de pontos no arquivo pontos.txt (está aqui). Para testar o método public Point2D nearest(Point2D p) fiz

% java NearestNeighborVisualizer pontos.txt

O programa mostra o ponto mais-próximo do pointer.:

Para testar o método public Iterable<Point2D> range(RectHV rect) fiz

% java RangeSearchVisualizer pontos.txt

O programa mostra os pontos dentro do retângulo definido através do mouse:

Sakadāgāmin

Fiz uma copia do método

    //  a nearest neighbor to point p; null if the symbol table is empty 
    public Point2D nearest(Point2D p) {
        blá
    }

e mudei a assinatura dessa copia para

    public Iterable<Point2D> nearest(Point2D p, int k) {
        blá
    }    

Afinal de contas, o método anterior era o este para k == 1.

Troquei a variável que Point2D nearestPoint que utilizava para uma referência para o ponto mais-próximo até o momento por uma variável XXX<Point2D> nearestKPoints para manter os k pontos mais-próximos até o momento. Qual classe deve ser XXX? Ao final do método fazia

    return nearestKPoints;

Achei que a modificação que fiz no método foi pequena. Apenas no trecho que examinava um ponto específico.

Anāgāmi

Testei esse novo método para k == 1. Se isso não funcionasse...

Em seguida testei para k == 2, k == 3, ...

Para fazer testes utilizando o visualizador, inclui na classe PointST um método

    // This method should return the k points that are closest to the query point (in any order);
    // return all N points in the data structure if N <= k.
    public Iterable<Point2D> nearest(Point2D p, int k) 

Em seguida modifiquei um pouco o programa NearestNeighborVisualizer.java e chamei essa versão um pouco modificada de NearestKNeighborVisualizer.java (está aqui).

Para fazer um teste visual fiz:

% java NearestKNeighborVisualizer pontos.txt 5

O programa mostrava os 5 pontos mais-próximos do pointer.:

Arahant

Finalmente, depois de tudo feito, fiz uma alteração do método public Point2D nearest(Point2D p) que achei que fazia sentido. Hmm, pelo menos do ponto de engenharia de software. Se bem que não entendo nada disso. Bem, eis o método modificado:

    // a nearest neighbor to point p; null if the symbol table is empty 
    public Point2D nearest(Point2D p) {
        if (p == null) throw new java.lang.NullPointerException("KdTreeST.nearest(): argument is null");
        if (this.isEmpty()) return null;
        return nearest(p, 1).iterator().next(); // retorna o único ponto na coleção iterable
    }

Comentários ou críticas

Comentários ou críticas?  Sinto falta de ouvir vocês falarem das suas ideias ao fazer os EPs. Acho que todos aprendem muito ouvindo as ideias do outros.

BoidSimulator

Depois de tudo feito baixem os programas BoidSimulator.java, Boid.java e Hawk.java. Compilem tudo, junto com o KdTreeST.java e executem o comando abaixo. Como diz o enunciado Behold their flocking majesty!.

% java BoidSimulator