Algorithmus zur Lösung des Problems der planaren Beschränkung ("Pokemon Go Monster Finding")

8

[Hinweis: Dieses Problem wurde von Pokemon Go inspiriert. Ich werde das Problem zuerst in mathematischen Begriffen erklären und dann die Verbindung zu Pokemon Go erklären. Mein Ziel ist es nicht, im Spiel zu schummeln. Wenn ich schummeln wollte, wären bessere Informationen leichter verfügbar.]

Angenommen, eine Ebene enthält N Punkte (die "unbekannten Punkte"). Nennen Sie sie mit unbekannten Koordinaten. Darüber hinaus haben wir Messungen an bekannten Orten .n1,,nNm 1 , , m M.Mm1,,mM

Sei der (allgemein unbekannte) euklidische Abstand vom Messpunkt zum unbekannten Punkt .m i n jdist(mi,nj)minj

Für jede Messung haben wir folgende Informationen:mi

  1. Die genauen Koordinaten jedes unbekannten Punktes für den für eine bekannte Konstante ; und dist ( m i , n j ) < d min d minnjdist(mi,nj)<dmindmin
  2. Eine Liste aller Indizes für die für eine bekannte Konstante , sortiert nach .dist ( m i , n j ) < d max d max > d min dist ( m i , n j )jdist(mi,nj)<dmaxdmax>dmindist(mi,nj)

Gibt es einen effizienten Algorithmus zur Berechnung der Bereiche der Ebene, in denen die unbekannten Punkte oder ein gegebener unbekannter Punkt können? Der Algorithmus erhält die Koordinaten der Messpunkte, die oben aufgeführten und die Anzahl unbekannter Punkte; Ziel ist es, den Bereich möglicher Orte für jeden der unbekannten Punkte so weit wie möglich . ( X i , Y i ) N n 1 , , n N.nj(Xi,Yi)Nn1,,nN

Die Pokemon-Verbindung:

In Pokemon Go, einem Augmented Reality-Spiel, ist das Ziel, Pokemons in der Natur zu finden. Hin und wieder zeigt das Spiel die Pokemons in einem "sichtbaren Bereich" ( ) der Position des Spielers. Darüber hinaus verfügt es über einen "Pokemon Finder", der eine Liste von Pokemons in der Nähe ( ) anzeigt, sortiert nach Entfernung. (Es soll auch eine ungefähre Entfernung als ein, zwei oder drei Schritte anzeigen, aber anscheinend gibt es einen Fehler und es werden immer drei Schritte angezeigt.) d i s t < d m a xdmindist<dmax

Sami Liedes
quelle
3
"sortiert nach " - das ist wirklich böse! Ohne diese zusätzlichen Informationen müssten Sie nur den Schnittpunkt einiger Annuli nehmen und damit fertig sein, aber die Sortierung liefert Ihnen zusätzliche Informationen, die es schwierig machen. dist(m,n)
Tom van der Zanden
Mir ist nicht klar, ob bekannt ist oder welche Informationen für jedes . die Informationen für etwa "Punkt 3 ist bei ; die anderen in der Nähe befindlichen Gegenstände sind Punkt 1, Punkt 7, Punkt 4 in dieser Reihenfolge"? m ( X 1 , Y 1 ) ( X 1 + 1 , Y 1 - 0,2 )Nm(X1,Y1)(X1+1,Y10.2)
Peter Taylor
@ PeterTaylor, ja, das stimmt. Siehe meine Bearbeitung. Ist es jetzt klar?
DW

Antworten:

3

Ich denke, Sie könnten eine "räumliche Verknüpfung" verwenden. Ich habe das Spiel nicht gespielt, aber ich davon aus, dass ziemlich klein ist, dh es gibt in der Größenordnung von 10 oder so und in der Nachbarschaft jedes . Ich gehe weiter davon aus, dass und groß sind, sagen wir 1.000.000 oder mehr. n m m N M.dmaxnmmNM

  1. Fügen Sie alle als 2D-Punkte in einen räumlichen Index einm
  2. für jedes im Index eine räumliche Bereichsabfrage mit dem Abstand . Dies gibt Ihnen alle anderen , die möglicherweise das gleiche wie . Dies sollte überschaubar sein, da die Anzahl von klein sein sollte (wie ich oben angenommen habe). 2 d m a x m x n m 1 m xm12dmaxmxnm1mx
  3. Wenn Sie nun alle anderen geschätzten Messungen für ein bestimmtes , können Sie versuchen, das richtige zu approximierennnn
  4. (Mögliche Optimierung): Abhängig von Ihrem räumlichen Index können Sie entfernen, nachdem Sie alle . Dadurch wird das Dataset für die folgenden Bereichsabfragen kleiner. Ebenfalls, nm1n

Irgendwie müssten Sie auch jedes eindeutig identifizieren , damit Sie die Position von erneut berechnen, wenn sie bei der Verarbeitung eines weiteren auftaucht .n mnnm

Zur Optimierung möchten Sie möglicherweise Fensterabfragen (rechteckig) anstelle von Abfragen mit kreisförmigem Bereich verwenden. Fensterabfragen können viel schneller sein und nur geringfügig mehr Ergebnisse liefern. Es könnte auch sein, dass das Spiel tatsächlich keinen euklidischen Abstand (Kreise) verwendet, sondern den schnelleren Manhatten-Abstand, der genau ein Rechteck wäre.

Für eine solche räumliche Verknüpfung können Sie einen beliebigen räumlichen Index verwenden, z. B. R-Tree, kd-Tree, Quadtree oder eine ihrer Varianten.

Für große Datenmengen würde ich wahrscheinlich keinen R-Tree (R + -Baum, R * -Baum, X-Tree) oder eine spezielle Variante des Quadtree, den PH-Tree, verwenden, der auch für Bereichsabfragen gut geeignet ist Ermöglichen des schnellen Entfernens (oder Hinzufügens) von Punkten.

Für Java finden Sie Implementierungen von R-Trees überall im Internet, beispielsweise im ELKI- Framework oder in meiner eigenen TinSpin Index-Bibliothek . Der PH-Tree ist auch in Java verfügbar.

Ein generischer räumlicher Join-Algorithmus heißt TOUCH , aber ich denke nicht, dass es Open Source ist.

TilmannZ
quelle
1
Ich sehe nicht, wie dies das Problem löst. Sie können alle Paare für die der unbekannte Punkt im Bereich des Messpunkts , aber das scheint nicht der schwierige Teil zu sein. Der schwierige Teil besteht darin, diese Informationen zu verwenden, um die Menge möglicher Orte für jedes zu identifizieren . Wie sieht die Form dieser Region aus? Können Sie die genaue Region ausgeben? Wie berücksichtigen Sie die von Tom van der Zanden hervorgehobenen Bestellinformationen ? (mi,nj)njminj
DW
Äh, Explosion aus der Vergangenheit :-). "Spatial Join" ist etwas, von dem nur wenige gehört haben, deshalb dachte ich, es sei der Kern der Frage. Ich habe einfach die Antwort für "welche Region" als "um diesen Punkt herum" betrachtet. Anscheinend habe ich das falsch verstanden.
TilmannZ
dmindmaxm
1

njdminnjmidmindist(mi,nj)<dmaxdij=dist(mi,nj)minjmipso dass ) und ein "fernes" Stück (das alle Punkte so dass ). Jedes Objekt, das vor für die Messung ist, ist notwendigerweise auf den nahen Ring beschränkt, und jedes Objekt, das nach ist, ist auf den fernen Ring beschränkt. p d i jd i s t ( m i , p ) < d m a x n j m i n jdmindist(mi,p)<dijpdijdist(mi,p)<dmaxnjminj

Was kann (jenseits des von Tom van der Zanden bereits in einem Kommentar vorgeschlagenen Schnittpunkts von Annuli) für Objektpositionen getan werden, die auf diese Weise nicht mit einer bereits bekannten Objektposition zusammenhängen? Das scheint sehr schwer zu sein. Die Aussage

" kann nicht bei erscheinen " pnjp

ist äquivalent zu

"Für alle möglichen Platzierungen aller verbleibenden unbekannten Punkte führt die Einstellung von zusammen mit den Abstandsungleichungen, die sich aus der Reihenfolge ergeben, in der Objekte, die zum Ringraum jeder Messung gehören, aufgelistet sind, zu einem Widerspruch."nj=p

Es scheint mir, dass wir (mindestens) 2 unbekannte Objektpositionen haben müssen, die im Ring von (mindestens) denselben 2 Messungen erscheinen, um irgendwohin zu gelangen. Aber während diese Informationen werden viele ausschließen Paare von Positionen für die beiden Objekte, war ich nicht in der Lage mit jedem Umstand zu kommen , in dem eine Position für nur eine ausgeschlossen von ihnen werden könnte, unabhängig von der anderen Objektposition.

j_random_hacker
quelle