Je ne suis pas sûr du concept mathématique pour soutenir ma question. ^^
Disons que nous avons Pointa comme référence. Le problème est de trouver les points autour du pointal dans un rayon donné (utilisant des coordonnées). Mon approche serait de calculer la distance de chaque point (Pythagorean), puis de comparer avec le rayon donné. Je suis sûr que cela sucerait en termes de complexité.
Quel algorithme pourriez-vous suggérer? Un exemple de code pour pointer des choses serait très apprécié. Merci.
4 Réponses :
Si vos points ne sont pas indexés, c'est un algorithme optimal. Il y a n points, et cela prendra l'heure de O ( N ) pour les chercher tous, en l'absence de tout autre index.
La micro-optimisation consiste à ignorer l'opération SQRT et à comparer la somme des carrés des deltas de coordonnées avec le carré du rayon souhaité.
Si vous allez faire plusieurs requêtes par rapport au même ensemble de données, vous pouvez utiliser divers systèmes d'indexation qui prennent un certain temps pour calculer (o (n log n)), mais faire la recherche plus rapide (O (M + journal n), où m est le nombre de points trouvés.)
Les arbres KD sont probablement l'endroit pour commencer là-bas.
Je voudrais ajouter que vous ne pouvez sauter que l'opération SQRT si vous êtes confiant que les coordonnées sont toutes inférieures à la SQRT (DBL_MAX)., Qui est généralement le cas. Le moyen de calcul de la distance euclidienne numériquement stable ne déborde pas de déborder à moins que la distance qui obtient déborde.
@Anonymous je sais que c'est une vieille question .. Mais comment allez-vous indexer ces points? Merci.
Je commencerais par créer une boîte autour du cercle et d'abord tester si quelque chose tombe à l'intérieur de la boîte. Ensuite, vous évitez probablement de calculer les SQRTS et les carrés tout le temps. Choisissez un bord de la boîte (dites celui du côté gauche) et calculez sa valeur x: alors tout ce qui sait p> peut être ignoré. Répétez quelque chose de similaire pour les quatre côtés. Le moment où un test échoue, arrête ensuite de travailler sur ce point. Ne faites pas de calculs inutiles. P> Cela vous dit qu'un point est proche mais pas nécessairement dans le rayon. Suivant Calculer: P> abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest))
Votre seule complexité ici est le calcul de la distance. Juste tamis et simplifier ce calcul et vous êtes optimal.
Si votre "centre" est un (x, y), alors pour tout point B (x1, y1) considérer:
1 / si B est dans votre distance requise D du point B, alors il s'ensuit que les deux 2 / plutôt que de calculer la distance, calculez le carré de la distance et comparez-le sur le carré de la distance maximale autorisée (que vous devez évidemment précalculer et référencer, plutôt que de recalculer à chaque fois). Cela signifie ne pas avoir à calculer une racine carrée pour chaque point.
Ce sont des optimisations assez mineures, mais en supposant que les points sont non formés et que c'est au hasard, c'est le meilleur que vous obtiendrez. x-x1 y-y1
La meilleure réponse dépendrait du nombre de dimensions. Je suppose que vous travaillez dans un espace 2D ou 3D.
Une simple approche serait de faire une grille uniforme de la taille de la cellule, dites "R". Puis épinglez tous les points à leurs cellules respectives.
Chaque point de requête interverse uniquement une poignée de cellules, disons 9. Vous devez inspecter uniquement les cellules intersectives, puis.
Une approche plus efficace serait de construire un quadtree ou un kd-arbre (il y a beaucoup d'autres options mais que le 2D, Quadree ou KD-Tree feraient).
Vérification de l'intersection du rectangle de cercle est nécessaire avec des structures hiérarchiques, mais cela est décrit dans l'algorithme voisin du voisin de KD-Tree (vous n'avez besoin que de la modifier légèrement).
Si vous êtes vraiment préoccupé par la performance, il est possible de construire plusieurs grilles (décalées ou tournées) et de sélectionner toujours celle avec la cellule la plus centrée sur le point de sorte que la recherche soit limitée au moins de cellules. < / p>
Vous voulez une fonction qui retournera chaque paire de coordonnées entier inférieure à une certaine distance d'une paire de coordonnées donnée? Ou vous avez un ensemble d'objets flottant et vous voulez savoir lesquels sont à l'intérieur du rayon?
Vous voudrez peut-être regarder cela ainsi de réponse: Stackoverflow.com/questions/1318595/...