Algoritmo para resolver el problema de restricción planar ("Descubrimiento de monstruos de Pokémon Go")

8

[Nota: este problema fue inspirado por Pokemon Go. Primero explicaré el problema en términos matemáticos, luego explicaré la conexión con Pokemon Go. Mi objetivo no es hacer trampa en el juego. Si quisiera hacer trampa, mejor información estaría disponible más fácilmente.]

Supongamos que hay puntos (los "puntos desconocidos") en un plano, , con coordenadas desconocidas. Además, tenemos mediciones tomadas en ubicaciones conocidas .Nn1,,nNMm1,,mM

Sea la distancia euclidiana (generalmente desconocida) desde el punto de medición al punto desconocido .dist(mi,nj)minj

Para cada medida , tenemos la siguiente información:mi

  1. Las coordenadas exactas de cada punto desconocido para el cual para alguna constante conocida ; ynjdist(mi,nj)<dmindmin
  2. Una lista de todos los índices para los cuales para alguna constante conocida , ordenada por .jdist(mi,nj)<dmaxdmax>dmindist(mi,nj)

¿Existe un algoritmo eficiente para calcular las áreas del plano donde pueden estar los puntos desconocidos, o un punto desconocido dado ? El algoritmo recibe las coordenadas de los puntos de medición, la información de medición enumerada anteriormente y el número de puntos desconocidos; el objetivo es reducir la región de posibles ubicaciones para cada uno de los puntos desconocidos tanto como sea posible.nj(Xi,Yi)Nn1,,nN

La conexión de Pokémon:

En Pokemon Go, un juego de realidad aumentada, el objetivo es encontrar Pokémon en la naturaleza. De vez en cuando, el juego muestra los Pokémon en un "rango visible" ( ) de la posición del jugador. Además, tiene un "buscador de Pokémon" que muestra una lista de Pokémon cercanos ( ), ordenados por distancia. (También se supone que muestra una distancia aproximada como uno, dos o tres pasos, pero aparentemente hay un error y siempre muestra tres pasos).dmindist<dmax

Sami Liedes
fuente
3
"ordenado por " - ¡eso es realmente desagradable! Sin esta información adicional, solo tendría que tomar la intersección de unos pocos anillos y terminar con ella, pero la clasificación le brinda información adicional que lo dificulta. dist(m,n)
Tom van der Zanden
No me queda claro si se conoce ni qué información se proporciona para cada . ¿La información dada para algo así como "El elemento 3 está en ; los otros elementos cercanos son el elemento 1, el elemento 7, el elemento 4 en ese orden"? Nm(X1,Y1)(X1+1,Y10.2)
Peter Taylor
@ PeterTaylor, sí, es cierto. Mira mi edición. ¿Está claro ahora?
DW

Respuestas:

3

Creo que podría usar una "unión espacial". No he jugado el juego, pero supongo que es bastante pequeño, es decir, hay en el orden de 10 más o menos y en la vecindad de cada . Además, supongo que y son grandes, digamos 1,000,000 o más.dmaxnmmNM

  1. Ponga todos los como puntos 2D en un índice espacialm
  2. Para cada en el índice, realice una consulta de rango espacial con distancia . Esto le proporciona todos los demás que potencialmente pueden contener el mismo que . Esto debería ser manejable porque el número de debería ser pequeño (como supuse anteriormente).m12dmaxmxnm1mx
  3. Ahora, al obtener todas las otras medidas estimadas para un particular , puede intentar aproximar el correctonn
  4. (Optimización potencial): dependiendo de su índice espacial, puede eliminar el después de procesar todo lo que es . Esto hace que el conjunto de datos sea más pequeño para las siguientes consultas de rango. También,m1n

De alguna manera, también necesitaría identificar de forma exclusiva cada , de modo que no calcule la posición de nuevamente si aparece al procesar otro .nnm

Como optimización, es posible que desee utilizar consultas de ventana (rectangulares) en lugar de consultas de rango circular. Las consultas de ventana pueden ser mucho más rápidas y dar solo un poco más de resultados. Además, podría ser que el juego en realidad no use la distancia euclidiana (círculos) sino la distancia más rápida del hombre, que sería exactamente un rectángulo.

Para dicha unión espacial, puede usar cualquier índice espacial, como R-Tree, kd-Tree, quadtree o cualquiera de sus variantes.

Para conjuntos de datos grandes, probablemente no usaría un R-Tree (R + tree, R * -tree, X-Tree), o una variante especial del quadtree, el PH-Tree, que es muy adecuado para consultas de rango, así como permitiendo la eliminación rápida (o adición) de puntos.

Para Java, las implementaciones de R-Trees se pueden encontrar en cualquier parte de Internet, por ejemplo, en el marco ELKI o en mi propia biblioteca TinSpin Index . El PH-Tree también está disponible en Java.

Un algoritmo genérico de unión espacial se llama TOUCH , pero no creo que sea de código abierto.

TilmannZ
fuente
1
No veo cómo esto resuelve el problema. Le permite encontrar todos los pares para los cuales el punto desconocido está dentro del rango del punto de medición , pero eso no parece ser la parte difícil. La parte difícil es usar esa información para identificar el conjunto de ubicaciones posibles para cada . ¿Cómo se ve la forma de esa región? ¿Se puede generar la región exacta? ¿Cómo está tomando en cuenta la información del pedido, como lo destaca Tom van der Zanden ? (mi,nj)njminj
DW
Uh, explosión del pasado :-). "Unión espacial" es algo de lo que pocas personas han oído hablar, así que pensé que era el núcleo de la pregunta. Simplemente consideré la respuesta para 'qué región' estar 'alrededor de este punto'. Aparentemente no entendí esto.
TilmannZ
Por lo que yo puedo decir, las regiones resultantes serán muy irregular, pero es bastante fácil de visualizar dibujando un anillo (entre el y alrededor de cada (digamos no sea que con una leve verde. Si un superposiciones de llamada con otro anillo, el verde se intensifica. Después de dibujar todos los anillos, elimine todas las áreas con intensidad no máxima de verde. También puede hacerlo completamente en la memoria 'dibujando' los anillos en una cuadrícula / matriz de grano fino y simplemente aumentando un . contador en cada celda de la cuadrícula que es lo que están pidiendo?dmindmaxm
TilmannZ
1

Si alguna posición del objeto se conoce exactamente (por ejemplo, porque está dentro de de alguna medición), entonces cada vez que este aparezca en el anillo para alguna medición (que significa ), podemos reducir las regiones posibles para otras posiciones desconocidas en ese mismo anillo. Específicamente, podemos simplemente calcular ya que conocemos ambas posiciones ( y ) exactamente, y luego podemos dividir el anillo para en dos subanulos: una pieza "cercana" ( que contiene todos los puntos tales quenjdminnjmidmindist(mi,nj)<dmaxdij=dist(mi,nj)minjmipdmindist(mi,p)<dij) y una pieza "lejana" (que contiene todos los puntos modo que ). Todos los objetos enumerados antes de para la medición están necesariamente confinados al anillo cercano, y todos los objetos listados después de están confinados al anillo lejano.pdijdist(mi,p)<dmaxnjminj

¿Qué se puede hacer (más allá de la intersección de los anillos ya sugeridos por Tom van der Zanden en un comentario) para las posiciones de objeto que no están relacionadas con alguna posición de objeto ya conocida de esta manera? Esto parece muy difícil. La declaración

" no puede aparecer en "njp

es equivalente a

"Para todas las ubicaciones posibles de todos los puntos desconocidos restantes, establecer , junto con las desigualdades de distancia implicadas por el orden en que se enumeran los objetos que pertenecen al anillo de cada medición, conduce a una contradicción".nj=p

Me parece que para llegar a cualquier parte, necesitamos tener (al menos) 2 posiciones de objetos desconocidos que aparecen en el anillo de (al menos) las mismas 2 mediciones. Pero aunque esta información descartará muchos pares de posiciones para los dos objetos, no pude encontrar ninguna circunstancia en la que se pudiera descartar una posición solo para uno de ellos, independientemente de la posición del otro objeto.

j_random_hacker
fuente