Algorithme pour trouver l'objet le plus proche sur la grille 2D
dites que vous avez une grille 2D avec chaque point sur la grille ayant x nombre d'objets (avec x >=0). J'ai du mal à imaginer un algorithme propre de sorte que lorsqu'un utilisateur spécifie une coordonnée, l'algorithme trouve la coordonnée la plus proche (y compris celle spécifiée) avec un objet dessus.
pour des raisons de simplicité, nous supposerons que si 2 coordonnées sont à la même distance la première sera retournée (ou si votre algorithme ne de cette façon, la dernière, n'a pas d'importance).
Edit: une coordonnée qui est à 1 doit être en haut, en bas, à gauche ou à droite. Les coordonnées diagonales sont 2.
comme note secondaire, qu'est-ce qu'une référence en ligne gratuite pour les algorithmes?
4 réponses
Udate
avec de nouvelles informations:
en supposant qu'une coordonnée diagonale est 2 de suite
cet algorithme fonctionnerait. L'algorithme cherche vers l'extérieur dans une sorte de spirale testant chaque point dans chaque "anneau" commencé de l'intérieur.
notez qu'il ne traite pas les situations hors limites. Vous devriez donc changer cela pour répondre à vos besoins.
int xs, ys; // Start coordinates
// Check point (xs, ys)
for (int d = 1; d<maxDistance; d++)
{
for (int i = 0; i < d + 1; i++)
{
int x1 = xs - d + i;
int y1 = ys - i;
// Check point (x1, y1)
int x2 = xs + d - i;
int y2 = ys + i;
// Check point (x2, y2)
}
for (int i = 1; i < d; i++)
{
int x1 = xs - i;
int y1 = ys + d - i;
// Check point (x1, y1)
int x2 = xs + d - i;
int y2 = ys - i;
// Check point (x2, y2)
}
}
ancienne version
en Supposant que dans votre grille 2D de la distance entre (0, 0) et (1, 0) est la même que (0, 0) et (1, 1). Cet algorithme fonctionne. L'algorithme cherche vers l'extérieur dans une sorte de spirale testant chaque point dans chaque "anneau" commencé de l'intérieur.
notez qu'il ne traite pas les situations hors limites. Vous devriez donc changer cela pour répondre à vos besoins.
int xs, ys; // Start coordinates
if (CheckPoint(xs, ys) == true)
{
return (xs, ys);
}
for (int d = 0; d<maxDistance; d++)
{
for (int x = xs-d; x < xs+d+1; x++)
{
// Point to check: (x, ys - d) and (x, ys + d)
if (CheckPoint(x, ys - d) == true)
{
return (x, ys - d);
}
if (CheckPoint(x, ys + d) == true)
{
return (x, ys - d);
}
}
for (int y = ys-d+1; y < ys+d; y++)
{
// Point to check = (xs - d, y) and (xs + d, y)
if (CheckPoint(x, ys - d) == true)
{
return (xs - d, y);
}
if (CheckPoint(x, ys + d) == true)
{
return (xs - d, y);
}
}
}
Si vous avez une liste d'objets
si vous aviez toutes les positions de tous les objets dans une liste, ce serait beaucoup plus facile car vous n'auriez pas besoin de chercher tous les carrés vides et pourrait effectuer 2D distance calculations pour déterminer celui qui vous est le plus proche. Bouclez votre liste d'objets et calculez la distance comme suit:
Define your two points. Point 1 at (x1, y1) and Point 2 at (x2, y2).
xd = x2-x1
yd = y2-y1
Distance = SquareRoot(xd*xd + yd*yd)
alors il suffit de choisir celui avec le la distance la plus courte.
si vous n'avez qu'un tableau 2D
si toutefois le problème tel que décrit suppose un tableau 2D où les emplacements des objets ne peuvent pas être listés sans d'abord les chercher tous, alors vous allez devoir faire une boucle en spirale.
Searching for ' Spiral Search Method " propose quelques liens intéressants. voici un code qui fait boucle en spirale autour d'un tableau, mais cela ne fonctionne pas d'un point arbitraire et spirale vers l'extérieur, mais devrait vous donner de bonnes idées sur la façon d'atteindre ce que vous voulez.
Voici une question similaire sur le remplissage des valeurs en ordre spirale dans un tableau 2D.
de toute façon, voici comment je m'attaquerais au problème:
point donné P , créer une paire de vecteurs qui spécifie une zone autour de P .
si P = 4,4
Alors votre paire de vecteurs serait 3,3|5,5
Boucle chaque valeur dans ces limites.
for x = 3 to 5
for y = 3 to 5
check(x,y)
next
next
si une valeur est trouvée, exit. Si pas, augmenter les limites par un nouveau. Donc dans ce cas nous irions à 2,2 / 6,6
lors de la boucle pour vérifier les valeurs, s'assurer que nous n'avons pas entré d'indices négatifs, et aussi s'assurer que nous n'avons pas dépassé la taille du tableau.
aussi si vous prolongez les limites n fois, vous avez seulement besoin de boucler les valeurs limites externes, vous n'avez pas besoin de revérifier les valeurs internes.
Quelle méthode est la plus rapide?
tout dépend de:
- la densité de votre réseau
- technique de Distribution
- nombre d'objets
Densité du réseau
si vous avez un tableau 500x500 avec 2 objets dedans, alors boucler la liste sera toujours plus performant faire une spirale
technique de Distribution
S'il existe des motifs de distribution (C'est-à-dire que les objets tendent à se regrouper les uns autour des autres), une spirale peut être plus rapide.
nombre d'objets
A spiral fonctionnera probablement plus rapidement s'il y a un million d'objets, car la technique de liste vous demande de vérifier et de calculer chaque distance.
vous devriez être en mesure de calculer la solution la plus rapide en calculant la probabilité d'un espace étant rempli, par rapport au fait que la solution de liste doit vérifier chaque objet à chaque fois.
cependant, avec la technique de liste, vous pouvez être en mesure de faire un tri intelligent pour améliorer les performances. C'est probablement la peine de regarder dans.
si vos objets sont denses, alors juste la recherche des points à proximité sera probablement le meilleur moyen de trouver l'objet le plus proche, s'échappant du centre. Si vos objets sont épars, alors un quadtree ou une structure de données associée (arbre R, etc.) est probablement mieux. Voici un writeup avec des exemples.
Je ne sais pas d'une bonne référence d'algorithme en ligne, mais je peux dire que si vous allez écrire plus que le une ligne de code occasionnelle, économisant vos pièces d'un cent pour acheter CLRS vaudra la peine. Il y a des conférences basées sur ce livre en ligne qui ont été minutieusement annotées par Peteris Krumins , mais ils ne couvrent qu'une partie du livre. C'est l'un des rares livres que vous devez posséder.
la solution simple suivante suppose que vous pouvez vous permettre de stocker des informations supplémentaires par cellule de grille, et que le coût de temps de l'ajout de nouveaux objets à la grille est permis d'être relativement élevé.
l'idée est que chaque cellule contient une référence à la cellule occupée la plus proche, permettant ainsi O(1) le temps d'interrogation. Chaque fois qu'un objet est ajouté à la position (i,j), effectuer un balayage des cellules environnantes, couvrant des anneaux de taille croissante. Pour chaque cellule scannée, évaluer sa référence actuelle la plus proche de la cellule occupée, et la Remplacer si nécessaire. Le processus se termine lorsque le dernier anneau scanné n'est pas modifié du tout. Dans le pire des cas, le processus scanne toutes les cellules de la grille, mais il finit par s'améliorer lorsque la grille devient assez dense.
cette solution est simple à mettre en œuvre, peut avoir un espace aérien significatif (selon la façon dont votre grille est organisée en mémoire), mais fournit le temps d'interrogation optimal.