Trouver le voisin le plus proche dans un rayon

Question

J'ai un ensemble de points A dans mon espace (points géographiques mais je peux supposer qu'ils sont sur un avion 2D).

J'ai un autre ensemble de points B .

pour chaque point de B Je veux trouver tous les points de A à l'intérieur d'un rayon r avec centre dans le point considéré de B SET.

Je l'ai fait avec Kdtree, cela me fournissait un algorithme très rapide et facile à créer la structure de données et à trouver des voisins mais il ne trouve pas tous les points d'un rayon parce qu'il pourrait éviter un chemin qui contient l'élément de mon rayon mais pas dans le même sous-ensemble du centre de rayon.

Exemple minimal de Kdtree défaillance :

Tout en explorant Kdtree, le point cible (rouge) est sous la ligne de point de point 1. Cela procédera à l'exploration du point sous la ligne, cela manquera le point réel à l'intérieur du rayon de point rouge.

Quelle algorithme ou quelle structure de données permet de 100% exactitude?

Je sais bien sûr, je vais jouer pire mais je cherche un équilibre entre la vitesse de recherche et la correction complète.

Answer 1

L'arbre K-D est une bonne structure de données pour résoudre ce problème.Cependant, vous ne pouvez pas appliquer aveuglément la procédure de recherche uniquement au point central, vous devez être un peu plus intelligent.

Lors de la recherche de l'arborescence KD pour vos points, chaque fois que vous devez choisir l'enfant gauche ou droit pour rechercher dans l'intérieur, vérifiez si le plan de fractionnement est à gauche de votre cercle, le recule ou est à droite du cercle..

Si le plan de fractionnement se trouve à gauche de votre cercle, vous devez continuer à rechercher dans le bon enfant et vice versa.Cependant, lorsque le plan de fractionnement intersecte votre cercle, vous devez rechercher les deux enfants.