Implémentation de KDTree en Java

Question

Je suis à la recherche d'une implémentation de KDTree en Java.
J'ai fait une recherche sur Google et les résultats semblent assez aléatoires. Il y a en fait beaucoup de résultats, mais il s'agit surtout de petites implémentations uniques, et je préférerais trouver quelque chose avec un peu plus de "valeur de production". Quelque chose comme les collections Apache ou l'excellente bibliothèque de collections C5 pour .NET. Quelque chose où je peux voir le bug tracker public et vérifier quand le dernier commit SVN a eu lieu. De même, dans un monde idéal, je trouverais une belle API bien conçue pour les structures de données spatiales, et le KDTree ne serait qu'une classe parmi d'autres dans cette bibliothèque.

Pour ce projet, je ne travaillerai qu'en 2 ou 3 dimensions, et je suis surtout intéressé par une bonne implémentation des plus proches voisins.

Answer 1

Dans le livre Les algorithmes en quelques mots il y a une implémentation de l'arbre kd en java avec quelques variations. L'ensemble du code se trouve sur oreilly.com et le livre lui-même vous guide également à travers l'algorithme pour que vous puissiez en construire un vous-même.

Answer 2

Pour les futurs chercheurs. La bibliothèque Java-ml possède une implémentation de kd-tree qui fonctionne bien. http://java-ml.sourceforge.net/

Answer 3

J'ai eu du succès avec l'implémentation du professeur Levy qui a trouvé aquí . Je me rends compte que vous recherchez une mise en œuvre plus certifiée pour la production, donc ce n'est probablement pas une bonne solution.

Cependant, je signale à tous les passants que je l'utilise depuis un certain temps déjà dans mon projet de photomosaïque sans aucun problème. Ce n'est pas une garantie, mais c'est mieux que rien :)

Answer 4

J'ai créé une implémentation de KD-Tree dans le cadre d'une bibliothèque de géocodage inverse hors ligne.

https://github.com/AReallyGoodName/OfflineReverseGeocode

Answer 5

Peut-être Recherche du plus proche voisin y Arbres KD du dépôt d'algorithme de Stony-Brook peut aider.