Algorithme pour résoudre le problème de contrainte planaire ("Recherche de monstre Pokemon Go")

8

[Remarque: ce problème a été inspiré par Pokemon Go. Je vais d'abord expliquer le problème en termes mathématiques, puis expliquer la connexion à Pokemon Go. Mon objectif n'est pas de tricher dans le jeu. Si je voulais tricher, de meilleures informations seraient disponibles plus facilement.]

Supposons qu'il y ait N points (les "points inconnus") dans un avion, appelez-les n1,,nN, avec des coordonnées inconnues. De plus, nous avonsM mesures prises à des endroits connus m1,,mM.

Laisser dist(mi,nj) être la distance euclidienne (généralement inconnue) du point de mesure mi au point inconnu nj.

Pour chaque mesure mi, nous avons les informations suivantes:

  1. Les coordonnées exactes de chaque point inconnu nj Pour qui dist(mi,nj)<dmin pour une constante connue dmin; et
  2. Une liste de tous les indices j Pour qui dist(mi,nj)<dmax pour une constante connue dmax>dmin, trié par dist(mi,nj).

Existe-t-il un algorithme efficace pour calculer les zones de l'avion où les points inconnus, ou un point inconnu donné nj, peut être? L'algorithme reçoit les coordonnées(Xi,Yi) des points de mesure, les informations de mesure répertoriées ci-dessus et le nombre Nde points inconnus; l'objectif est de réduire la région des emplacements possibles pour chacun des points inconnusn1,,nN autant que possible.

La connexion Pokemon:

Dans Pokemon Go, un jeu de réalité augmentée, le but est de trouver des Pokémons dans la nature. De temps en temps, le jeu montre les Pokémons dans une "plage visible" (dmin) de la position du joueur. De plus, il dispose d'un "Pokemon finder" qui affiche une liste des environs (dist<dmax) Pokémons, triés par distance. (Il est également censé montrer une distance approximative comme un, deux ou trois pas, mais apparemment il y a un bug et il montre toujours trois pas.)

Sami Liedes
la source
3
"trié par dist(m,n)"- c'est vraiment méchant! Sans ces informations supplémentaires, il vous suffirait de prendre l'intersection de quelques anneaux et d'en finir, mais le tri vous donne des informations supplémentaires qui rendent les choses difficiles.
Tom van der Zanden
Je ne sais pas si N est connu, ni quelles informations sont données pour chaque m. Les informations sont-elles fournies pour(X1,Y1) quelque chose comme "l'article 3 est à (X1+1,Y10.2); les autres articles à proximité sont l'article 1, l'article 7, l'article 4 dans cet ordre "?
Peter Taylor
@PeterTaylor, oui, c'est vrai. Voir mon montage. Est-ce clair maintenant?
DW

Réponses:

3

Je pense que vous pourriez utiliser une "jointure spatiale". Je n'ai pas joué au jeu, mais je supposedmax est assez petit, c'est-à-dire qu'il y en a environ 10 n et m au voisinage de chacun m. Je suppose en outre queN et M sont grandes, disons 1 000 000 ou plus.

  1. Met tout m en tant que points 2D dans un index spatial
  2. Pour chaque m1 dans l'index, effectuez une requête de plage spatiale avec la distance 2dmax. Cela vous donne tous les autresmx qui peut potentiellement contenir le même n comme m1. Cela devrait être gérable car le nombre demx devrait être petit (comme je l'ai supposé ci-dessus).
  3. Maintenant, en obtenant toutes les autres mesures estimées pour un particulier n, vous pouvez essayer d'approximer la bonne n
  4. (Optimisation potentielle): En fonction de votre indice spatial, vous pouvez supprimer le m1 après avoir traité tout c'est n. Cela rend l'ensemble de données plus petit pour les requêtes de plage suivantes. Aussi,

D'une manière ou d'une autre, vous auriez également besoin d'identifier n, de sorte que vous ne calculez pas la position de n à nouveau s'il apparaît lors du traitement d'un autre m.

À titre d'optimisation, vous souhaiterez peut-être utiliser des requêtes de fenêtre (rectangulaires) plutôt que des requêtes de plage circulaire. Les requêtes de fenêtres peuvent être beaucoup plus rapides et donner seulement un peu plus de résultats. De plus, il se peut que le jeu n'utilise pas réellement la distance euclidienne (cercles) mais la distance manhatten plus rapide, qui serait exactement un rectangle.

Pour une telle jointure spatiale, vous pouvez utiliser n'importe quel index spatial, tel que R-Tree, kd-Tree, quadtree ou l'une de leurs variantes.

Pour les grands ensembles de données, je n'utiliserais probablement pas d'arbre R (arbre R +, arbre R *, arbre X) ou une variante spéciale de l'arbre quadruple, l'arbre PH, qui convient bien aux requêtes de plage ainsi qu'aux permettant le retrait (ou l'ajout) rapide de points.

Pour Java, les implémentations de R-Trees peuvent être trouvées n'importe où sur Internet, par exemple dans le cadre ELKI ou ma propre bibliothèque d'index TinSpin . Le PH-Tree est également disponible en Java.

Un algorithme générique de jointure spatiale est appelé TOUCH , mais je ne pense pas qu'il soit open source.

TilmannZ
la source
1
Je ne vois pas comment cela résout le problème. Il vous permet de trouver toutes les paires(mi,nj) pour quel point inconnu nj est dans la plage du point de mesure mi, mais cela ne semble pas être la partie difficile. La partie difficile est d'utiliser ces informations pour identifier l'ensemble des emplacements possibles pour chaquenj. À quoi ressemble la forme de cette région? Pouvez-vous produire la région exacte? Comment tenez-vous compte des informations de la commande, comme l'a souligné Tom van der Zanden ?
DW
Euh, souffle du passé :-). "La jointure spatiale" est quelque chose dont peu de gens ont entendu parler, donc je pensais que c'était le cœur de la question. J'ai simplement considéré la réponse pour «quelle région» être «autour de ce point». Apparemment, j'ai mal compris cela.
TilmannZ
Pour autant que je sache, les régions résultantes seront très irrégulières, mais assez faciles à visualiser en dessinant un anneau (entre dmin et dmax autour de chacun m(de peur de dire avec un vert pâle. Si un anneau chevauche un autre anneau, le vert est intensifié. Après avoir dessiné tous les anneaux, supprimez toutes les zones avec une intensité de vert non maximale. Vous pouvez également le faire complètement en mémoire en «dessinant» le sonne sur une grille / matrice à grains fins et augmente simplement un compteur dans chaque cellule de la grille. C'est ce que vous demandez?
TilmannZ
1

Si une position d'objet nj est connue exactement (par exemple, parce dmin d'une certaine mesure), puis chaque fois que cela nj apparaît dans l'espace annulaire pour une mesure mi (sens dmindist(mi,nj)<dmax), nous pouvons réduire les régions possibles pour d'autres positions inconnues dans ce même anneau. Plus précisément, nous pouvons simplement calculerdij=dist(mi,nj) puisque nous connaissons les deux positions (mi et nj) exactement, et nous pouvons ensuite diviser l'anneau pour mi en deux sous-anneaux: une pièce "proche" (contenant tous les points p tel que dmindist(mi,p)<dij) et une pièce "lointaine" (contenant tous les points p tel que dijdist(mi,p)<dmax). Chaque objet répertorié avantnj pour la mesure mi est nécessairement confiné à l'anneau proche, et chaque objet répertorié après nj est confiné à l'anneau lointain.

Que peut-on faire (au-delà de l'intersection des anneaux déjà suggérée par Tom van der Zanden dans un commentaire) pour des positions d'objet qui ne sont pas liées à une position d'objet déjà connue de cette manière? Cela semble très difficile. La déclaration

"nj ne peut pas apparaître à p"

est équivalent à

"Pour tous les emplacements possibles de tous les points inconnus restants, la définitionnj=p, ainsi que les inégalités de distance impliquées par l'ordre dans lequel les objets appartenant à l'anneau de chaque mesure sont répertoriés, conduit à une contradiction ".

Il me semble que pour aller n'importe où, nous devons avoir (au moins) 2 positions d'objets inconnus qui apparaissent dans l'espace annulaire (au moins) des 2 mêmes mesures. Mais alors que ces informations excluront de nombreuses paires de positions pour les deux objets, je n'ai pu trouver aucune circonstance dans laquelle une position pourrait être exclue pour un seul d'entre eux, indépendamment de la position de l'autre objet.

j_random_hacker
la source