Finde k nächste Nachbarn auf einer Kugel

7

Gegeben ein Satz $S$ von $N$ zeigt auf eine Kugel und einen anderen Punkt $P$ auf der Kugel möchte ich die finden $k$ Punkte in $S$ das sind die nächsten (euklidische oder Großkreisentfernung).

Ich bin bereit, eine angemessene Menge an Vorberechnungen durchzuführen. Die Lösung muss genau und effizient sein (schneller als die lineare Zeit).

data-structures computational-geometry nearest-neighbour JohnJ
quelle

1

Es sieht so aus, als ob diese Frage auf der Website leichter zu lösen ist

R^{2}

$\mathbb{R}^2$ Flugzeug. Haben Sie darüber nachgedacht und lassen sich die Antworten leicht auf die Sphäre übertragen, und warum (nicht)? Zum Beispiel können Sie berechnen

A (v) = {p | \forall_{w \in S} d (p, v) \leq d (p, w)}

$A(v)=\{p | \forall_{w\in S} d(p,v) \leq d(p,w)\}$ Dies ist ein konvexes Polygon, das durch Linien definiert ist, die orthogonal zu Linien dazwischen sind

v

$v$ und

w

$w$ und verwenden Sie dies zusammen mit der Raumaufteilung, um den nächsten Nachbarn zu finden und von dort aus zu arbeiten.

Lieuwe Vinkhuijzen

@LieuweVinkhuijzen Die sphärische Topologie ist wichtig, da der Anwendungsfall ein GIS-Problem ist. Ich habe das, was ich für eine funktionierende Lösung halte, bin aber neugierig auf den Stand der Technik. Vielen Dank!

JohnJ

1

JohnJ, Lieuwe hat nicht gesagt, dass die sphärische Topologie unwichtig ist; Stattdessen denke ich, dass er sagt, dass es viele Standardtechniken gibt, um dies zu lösen

R^{2}

$\mathbb{R}^2$ und ich vermute, er hat empfohlen, dass Sie zunächst diese Standardansätze untersuchen und dann prüfen, ob sie geringfügig geändert werden können, um zu berücksichtigen, dass Sie sich tatsächlich auf einer Kugel befinden und nicht auf einer

R^{2}

$\mathbb{R}^2$ .

DW

4

Verwenden Sie den Raumpartitionierungsansatz für die Suche nach nächsten Nachbarn .

Ein Ansatz ist beispielsweise die Verwendung von a $k$ -d Baum auf der Oberfläche der Kugel. Sie können jeden Punkt auf der Kugel mit sphärischen Koordinaten ausdrücken : Jeder Punkt auf der Kugel hat Koordinaten $(1,\theta,\phi)$ . Wir haben also einen zweidimensionalen Raum mit Koordinaten $(\theta,\phi)$ . Organisieren Sie nun Ihre Punkte mit a $k$ -d Baum, wo wir hier sind $k=2$ Maße. Es gibt Standardalgorithmen für die Suche nach dem nächsten Nachbarn in a $k$ -d Baum; heuristisch ist die erwartete Laufzeit $O(\lg N)$ .

Sie müssen kleine Änderungen an der Datenstruktur vornehmen, um zu berücksichtigen, dass die Koordinaten modulo "umlaufen" $2\pi$ , aber das ist nicht schwer. Die Schlüsselunterroutine, die bei der Suche nach dem nächsten Nachbarn in a verwendet wird $k$ -d Baum ist: gegeben einen Punkt $P$ und einen "rechteckigen" Bereich $R$ , finde die Entfernung von $P$ zum nächsten Punkt in $R$ . In Ihrem Fall die Region $R$ ist $[\theta_\ell,\theta_u] \times [\phi_\ell, \phi_u]$ dh die Menge der Punkte $\{(1,\theta,\phi) : \theta_\ell \le \theta \le \theta_u, \phi_\ell \le \phi \le \phi_u\}$ . Es ist einfach, die Entfernung von zu berechnen $P$ zum nächsten Punkt in $R$ . Auf diese Weise können Sie den Standardalgorithmus für die Suche nach dem nächsten Nachbarn in a verwenden $k$ -d Baum.

Alternativ anstelle von a $k$ -d Baum, Sie könnten jeden anderen Binärraum-Partitionierungsbaum verwenden oder sich metrische Bäume ansehen , obwohl ich keinen Grund habe zu erwarten, dass sie wesentlich besser sind.

DW
quelle

1

Hier finden Sie Links zu zwei verschiedenen Softwarepaketen, die Ihre Frage beantworten. Es kann sich lohnen, jeden einzelnen zu untersuchen, um festzustellen, ob die von ihm verwendeten Methoden Ihren Anforderungen entsprechen:

(1) Matlab GridSphere . "Ein geodätisches Gitter ist ein gleichmäßiges Gitter über der Oberfläche einer Kugel. Der Algorithmus ist für ein von GridSphere erzeugtes Gitter optimiert und funktioniert nicht mit einem beliebigen geodätischen Gitter."

(2) DarkSkyApp Sphere-Knn .js . "Bietet schnelle Suche nach dem nächsten Nachbarn auf einer Kugel ... gut getestet und funktioniert korrekt, unabhängig davon, wo sich die Dinge auf der Erde befinden."

Joseph O'Rourke
quelle

Finde k nächste Nachbarn auf einer Kugel

Antworten: