Verfasst am: 10.09.2018, 11:15
Titel: Suche Koordinatenpaar mit dem geringsten Abstand
Hallo zusammen,
ich habe 2 Matrizen.
Matrix A besteht aus einem Längengrad (Spalte 1) und einem Breitengrad (Spalte 2). Matrix A hat mehr als 100.000 Zeilen.
Matrix B besteht aus einem Längengrad (Spalte 1), einem Breitengrad (Spalte 2) und einem Wert (Staßennamen, Spalte 3). Matix B hat mehr als 4.000.000 Zeilen.
Ich möchte nun für jede Zeile aus Matrix A eine Zeile in Matrix B finden, bei der Abstand der Koordinatenpaare am geringsten ist.
(Ich möchte den Koordinatenpaaren aus Matrix A einen Straßennamen zuordnen, den er aus Matrix B suchen soll).
Idee für die Vorgehensweise:
Um die Zuordnung durchzuführen, bilde ich die Differenz der Längengrade sowie die Differenz der Breitengrade und ermittle mittels Pythagoras daraus den direkten Abstand der Punkte.
Dies bedeutet im Umkehrschluss, dass ich für jeden der 100.000 Längengrade und für jeden der 100.000 Breitengrade 4.000.000 Differenzen bilden muss. Aus den Differenzen wird mittels Pythagoras der Abstand ermittelt. Aus diesen Abständen suche ich mir dann den Abstand, der am nächsten an 0 liegt.
Problem:
Bei meiner Vorgehensweise bräuchte ich für die Differenzbildung eine 100.000 x 4.000.000 Matrix. Wenn ich diese zuvor zur Preallocation mit nullen fülle, bekomme ich bereits die Fehlermeldung: "array exceeds maximum array size preference".
Die Berechnung würde wahrscheinlich eine halbe Ewigkeit dauern.
Gibt es eine Möglichkeit/Funktion mit der ich das Problem gelöst bekomme?
P.S.: auch eine andere Möglichkeit zur Berechnung des geringsten Abstandes zwischen den Koordinatenpaaren ist möglich.
Hat jemand eine Idee???
Vielen Dank und mit freundlichen Grüßen,
Shanox
Den Abstand berechne ich ganz einfach über Pythagoras.
Kleines Beispiel:
Es wird die erste Zeile in Matrix B genommen.
Verfasst am: 10.09.2018, 12:37
Titel: Re: Suche Koordinatenpaar mit dem geringsten Abstand
Hallo Shanox,
Anstatt eine riesige 100.000 x 4.000.000 Matrix zu erstellen, die 3200 GByte benötigen würde, benötigst Du einfach eine Schleife, die Du 100'000 mal durchlaufen lässt. Statt nach dem minimalen Abstand zu suchen, der die teure Berechnung der Wurzel erfordert ist es effizienter nach dem quadrierten Abstand zu suchen.
Wenn Du den bisherigen Code postest, wäre es einfacher einen passend Vorschlag zu schreiben.
Code:
X = rand(1e5, 2);
Y = rand(4e6, 2);
Index = zeros(1e5, 1);
for k = 1:size(X, 1)
Dist = (Y(:, 1) - X(k, 1)) .^ 2 + (Y(:, 2) - X(k, 2)) .^ 2;
[~, Index(k)] = min(Dist);
end
Das braucht natürlich eine gewisse Zeit. Es sind halt eine Menge Daten. Hier gibt es eine Menge intelligenter Methoden zur Reduktion der Suche. Du könntest die Daten z.B. in 4 Quadranten aufteilen und dann nur in jeweiligen Teilgebiet suchen. Eine Parallelizierung mit PARFOR könnte auch helfen. Mit einer C-Mex-Funktion könnte man auch etwas Zeit schinden: Falls die erste Koordinate schon größer ist als das bisherige Minimum, dann braucht man die zweite Koordinate gar nicht mehr zu berücksichtigen.
ich würde eine Schleife über die Zeilen der Matrix A laufen lassen, direkt den minimalen Abstand ausrechnen und die passende Zeile von B abspeichern. Allerdings würde ich ausgehend von den 0,07s für eine Zeile überschlagen, dass das auf meinem Rechner 1-2 Stunden dauern würde.
Man könnte noch versuchen, Blöcke von z.B. 100 Zeilen der Matrix A am Stück rechnen zu lassen.
Ansonsten ist die Frage, ob es zusätzliche Infos über die Daten gibt. Sind beispielsweise die Zeilen von A und B irgendwie geordnet? Wenn A eine Route darstellt, wäre z.B. davon auszugehen.
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Den Tipp von Harald konnte ich bereits anwenden. Ich habe die maximalen und minimalen Koordinaten der Route ermittelt und mit Hilfe dieser die Matrix B auf 300.000 Zeilen verkürzen können.
Trotzdem bleibt mein Rechner jedes mal hängen, wenn ich die Schleife über die gesamte Größe der Abstandsmatrix (die ich mit dieser Schleife erstellen will) laufen lasse.
Die Matrix A habe ich zu lat_Route und lon_Route gemacht (2 Spaltenvektoren).
Die Matrix B habe ich zu Lat_column und Lon_column gemacht (2 Zeilenvektoren).
Nochmal zur Erinnerung:
Ich möchte zu jedem Punkt (bestehend aus lat und lon Koordinate) aus Matrix A einen Punkt in Matrix B (ebenfalls aus lat und lon Koordinate) ermitteln, der zum Punkt aus A den geringsten Abstand hat. Als Ausgabe bräuchte ich für jede Zeile
Hier der relevante Teil meines Codes:
Code:
%Schleife zur Erstellung der Abstandsmatrizen lat_Abstand und lon_Abstand
Erst erstelle ich mit der Schleife, deren Laufvariable über alle Positionen der Matrix läuft, 2 Abstandsmatrizen, die mir die Abstände in Längen- und Breitengradrichtung liefern. Diese beiden Matrizen kombiniere ich zu einer Matrix, die mir die direkten Abstände liefert (Pythagoras). Daraus ermittle ich dann die Zeile, in der ich in einer anderen Matrix gleicher Größe einen Wert finde.
Welche Möglichkeiten habe ich das zu optimieren? Kann ich die Wurzel bei der Abstandsermittlung weglassen und ich bekomme trotzdem den geringsten Abstand, bzw. mein Code würde schneller laufen? Wie kann ich die Schleife in Blöcke einteilen und würde das Vorteile verschaffen?
das war ja nur ein Teil meiner Idee. Der andere war, nur eine Schleife laufen zu lassen. Beispielcode hat Jan geliefert (hatte ich nicht gesehen).
Grüße,
Harald
_________________
1.) Ask MATLAB Documentation
2.) Search gomatlab.de, google.de or MATLAB Answers
3.) Ask Technical Support of MathWorks
4.) Go mad, your problem is unsolvable ;)
Habt mir sehr geholfen! Funktioniert so, wie ich es mir vorgestellt habe!
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS