Autor Nachricht
Nikolas
BeitragVerfasst am: 07. Sep 2006 17:45    Titel:
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?
sax
BeitragVerfasst am: 07. Sep 2006 03:30    Titel:
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.
Rexxos
BeitragVerfasst am: 07. Sep 2006 01:15    Titel: Mathematische Frage / Kugelhülle
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:
Zitat:
SELECT id FROM PUNKTE
WHERE
(
(X BETWEEN (Position_X-Max_Entfernung) AND (Position_X+Max_Entfernung))
AND (Y BETWEEN (Position_Y-Max_Entfernung) AND(Position_Y+Max_Entfernung))
AND (Z BETWEEN (Position_Z-Max_Entfernung) AND(Position_Z+Max_Entfernung))
)



Aus dieser Ergebnismenge ermittle ich jetzt mit unten stehender Funktion jeweils die Entfernung der entsprechenden Punktes der Erebnismenge zum Punkt A und verwerfe alle Punkte die weiter Als MaxEntfernung entfern sind:
Zitat:


FUNCTION `entfernung`(param1 INTEGER(11), param2 INTEGER(11))
RETURNS double
DETERMINISTIC
SQL SECURITY DEFINER
COMMENT ''
BEGIN
declare Xa INT;
declare Ya INT;
declare Za INT;
declare Xb INT;
declare Yb INT;
declare Zb INT;
declare ergebnis DOUBLE;

SELECT X,Y,Z into Xa,Ya,Za FROM Punkte WHERE id = param1;
SELECT X,Y,Z into Xb,Yb,Zb FROM Punkte WHERE id = param2;
SELECT ROUND((sqrt( pow((Xa-Xb),2) + pow((Ya-Yb),2) + pow((Za-Zb),2))), 2) INTO ergebnis ;
return ergebnis;
END;


Powered by phpBB © 2001, 2005 phpBB Group