Discussion :

[nscott32]

Bonjour,

Dans le cadre d'un projet de licence j'ai implémenté l'algorithme d'interpolation de Voronoï dans lequel je dois chercher pour tout les points d'une carte en deux dimensions le point le plus proche parmi un ensemble de points de références.
Pour cela je stoque les points de référence dans un arbre kd.

Je dispose d'une méthode

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

searchNearest(Point p, Node parent, Node child)

Qui effectue une recherche dans la branche entre child et parent.

Pour effectuer une recherche dans l'arbre entier j'ai une méthode permettant de récupérer la bonne extrémité de l'arbre en fonction du point en paramètre, ensuite il suffit d'appeler

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

searchNearest(Point p, null, head.getChild())

pour chaque point pour effectuer une recherche sur l'arbre entier.

Le prof m'a dit que l'on pouvait optimiser encore la recherche en parcourant les points car le point le plus proche de deux points voisins à de forte chance d'être le même...
Seulement je ne vois pas comment m'y prendre...


Le code de searchNearest :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
    public Node searchNearest(Point _p, Node parent, Node child) {
 
        Node current = child;
        Node best = current;
        double currD = distance(_p, best.getDataPoint());
        double bestD = currD;
 
        while (current != parent) {
            currD = distance(_p, current.getDataPoint());
            if (currD == 0) return current;
 
            if (currD < bestD) {
                best = current;
                bestD = currD;  
            }
 
            // HYPERSPHERE TEST
            boolean xAxis   = current.getAxis()%2 == 0;
            Node sphere = null;
            int c1, c2;
            if (xAxis) {
                c1 = _p.x;
                c2 = current.getDataPoint().getX();
            }
            else {
                c1 = _p.y;
                c2 = current.getDataPoint().getY();
            }
 
            if (Math.abs(c1-c2) < bestD) {
                if (c1 > c2 && current.getSide1() != null)
                    sphere = searchNearest(_p, current, current.getSide1().getChild(_p));
                else if ( current.getSide2() != null )
                    sphere = searchNearest(_p, current, current.getSide2().getChild(_p));
 
                if (sphere != null) {
                    double sphereD = distance(_p, sphere.getDataPoint());
                    if ( sphereD < bestD ) {
                    bestD = sphereD;
                    best = sphere;
                    }
                }
            }
            current = current.getParent();
        }
 
 
        return best;
    }

et le code de getChild (dans la class Node) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
public Node getChild(Point p) {
 
            if (side1 == null && side2 == null)
               return this;
 
            boolean xAxis = axis%2 == 0;
            if (xAxis) {  
               if (p.x < point.getX())
                  if (side1 != null) return side1.getChild(p);
                  else return this;
               else 
                  if (side2 != null) return side2.getChild(p);
                  else return this;
            }
            else {
               if (p.y < point.getY())
                  if (side1 != null) return side1.getChild(p);
                  else return this;
               else 
                  if (side2 != null) return side2.getChild(p);
                  else return this;
            }  
         }

ps : La methode searchNearest fonctionne bien sauf pour quelques cas. J'ai une version de Voronoï sans kd tree , à la barbare, sur l'affichage des valeurs on peut voir quelques bizarreries... Je précise que l'affichage est indépendant de l'algorithme. Je vous montre :
Voronoi sans kd-tree :


Voronoi avec kd-tree :


On voit quelques zone fines de mauvaise couleur...
Pourtant j'ai eu beau lire relire et débugger cette méthode, je n'y vois rien. Si quelqu'un a une idée.

C'est à rendre demain (vendredi) à 20h, si je pourrais avoir de l'aide d'ici là ce serait super cool.
Merci !