Trouver l'élément "vrai" le plus proche dans une matrice booléenne 2D?

Question

J'ai une matrice 2D avec des valeurs booléennes, qui est mise à jour très fréquemment. Je veux choisir un index 2D {x, y} dans la matrice, et trouver l'élément le plus proche qui soit "vrai" dans la table, sans passer par tous les éléments (la matrice est massive).

Par exemple, si je la matrice:

0000100 
0100000 
0000100 
0100001 

et je choisis une coordonnée {x1, y1} tel que {4, 3}, je souhaite en retour l'emplacement de la valeur la plus proche « true », qui dans ce Le cas est {5, 3}. La distance entre les éléments est mesurée en utilisant l'équation de Pythagore standard:

distance = sqrt(distX * distX + distY * distY) où distX = x1 - x et distY = y1 - y.

Je peux parcourir tous les éléments de la matrice et garder une liste de «vraies» valeurs et sélectionner celle qui a le résultat de distance le plus court, mais c'est extrêmement inefficace. Quel algorithme puis-je utiliser pour réduire le temps de recherche?

Détails: La taille de la matrice est 1920x1080, et environ 25 requêtes seront effectuées chaque image. La matrice entière est mise à jour à chaque image. J'essaie de maintenir un framerate raisonnable, plus de 7fps est suffisant.

Answer 1

Si la matrice est toujours mise à jour, il n'y a pas besoin de construire une structure auxillary comme la distance transformer Voronoy diagramme etc.

Vous pouvez simplement exécuter la recherche comme BFS (recherche de pain premier) se propageant à partir du point d'interrogation . La seule différence par rapport à la BFS habituelle est la métrique euclidienne. Ainsi, vous pouvez générer (u, v) paires ordonnées par (u^2+v^2) et les points de contrôle symétriques décalées par (+-u,+-v),(+-v,+-u) combinaisons (quatre points lorsque u ou v est égal à zéro, huit points autrement)

Answer 2

Vous pouvez utiliser une structure de données d'arbre comme un quad-arbre (voir https://en.wikipedia.org/wiki/Quadtree) pour stocker tous les emplacements avec la valeur "true". De cette façon, il devrait être possible de parcourir rapidement toutes les "vraies" valeurs dans le voisinage d'un emplacement donné. De plus, l'arbre peut être mis à jour en temps logarithmique, si la valeur d'un emplacement change.