Mathematische Frage / Kugelhülle

Rexxos · Anmeldungsdatum: 17.05.2006 Beiträge: 2 Wohnort: Steyr

Hallo Leute !

Habe folgendes Problem:

Ich habe eine Menge aus ca. 2 Mio. Punkten mit gegebenen X,Y,Z Koordinaten (in einer Datenbank). Ich möchte jetzt für einen Punkt A alle Nachbarpunkte innerhalb einer Entfernung von max E einheiten finden.

Gibt es eine schnellere Methode alle Punkte innerhalb einer Kugelhülle zu finden ???

Derzeit gehe ich folgendermassen vor (ich weiss nicht unbedingt elegant aber es funktioniert):

Ich suche alle Punkte die in einem Kubus um meinen Punkt A liegen:

sax · Anmeldungsdatum: 10.05.2005 Beiträge: 377 Wohnort: Magdeburg

Hmm, die Frage hat nicht viel mit Physik zu tun schau doch mal bei den
Informatikern vorbei.
http://www.informatikerboard.de

Eine kleine Idee habe ich trotzdem, verwende statt der Entfernung das Quadrat der Entfernung. Dann mußt du die die Punkte suchen, deren Entfernungsqudrat kleiner ist als

.

Das hat den Vorteil, dass du dir das ziehen der Wurzel in deiner Routine ersparen kannst, was etwas Rechenzeit spart.

Nikolas

Worum geht es denn eigentlich? Hast du die Daten selbst erstellt? Ich hatte mal ein ähnliches Problem in der zweiten Runde des Bundeswettbewerb Informatik im letzten Jahr. Mein Ansatz war, dass ich meinen Raum, in dem sich die Punkte aufhalten mit einem Raster versehe und dann alle Punkte in einem Würfel zusammen speicher. Wenn du die Größe des Rasters sinnvoll wählst, musst du nur noch eine geringe Anzahl an Kugeln überprüfen.

Wie oft muss denn diese Operation ausgeführt werden?