Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Bücher:

Fachkräfte:
weitere Angebote

Partner:


Vermarktungspartner


Forum
      Option
[Erweitert]
  Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Suche Koordinatenpaar mit dem geringsten Abstand

 

Shanox
Forum-Anfänger

Forum-Anfänger


Beiträge: 20
Anmeldedatum: 15.08.18
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 10.09.2018, 10:15     Titel: Suche Koordinatenpaar mit dem geringsten Abstand
  Antworten mit Zitat      
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.
Private Nachricht senden Benutzer-Profile anzeigen


Jan S
Moderator

Moderator


Beiträge: 10.712
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 10.09.2018, 11:37     Titel: Re: Suche Koordinatenpaar mit dem geringsten Abstand
  Antworten mit Zitat      
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.

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.198
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 10.09.2018, 11:55     Titel:
  Antworten mit Zitat      
Hallo,

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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Shanox
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 20
Anmeldedatum: 15.08.18
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 11.09.2018, 10:46     Titel:
  Antworten mit Zitat      
Danke für eure Antworten.

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

lat_Abstand = zeros(length(Lat_column),length(lat_reale_Fahrt)); %preallocation
lon_Abstand = zeros(length(Lon_column),length(lon_reale_Fahrt));

row=1;
column=1;
for r=1:length(Lat_column)*length(lon_Route)
    if column <= length(lon_Route)
        lat_Abstand(row,column) = abs(Lat_column(row,1)-lat_Route(1,column));
        lon_Abstand(row,column) = abs(Lon_column(row,1)-lon_Route(1,column));
        column=column+1;
    else
        column=1;
        row=row+1;
        lat_Abstand(row,column) = abs(Lat_column(row,1)-lat_Route(1,column));
        lon_Abstand(row,column) = abs(Lon_column(row,1)-lon_Route(1,column));
        column=column+1;        
    end
end

%Kombination der Abstandsmatrizen zu einem Gesamtabstand

Abstand_total = sqrt(lon_Abstand.^2 + lat_Abstand.^2);
[Abstand_min Zeile_Abstand_min] = min(Abstand_total);

 


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?

Vielen Dank im Voraus!
Private Nachricht senden Benutzer-Profile anzeigen
 
Harald
Forum-Meister

Forum-Meister


Beiträge: 19.198
Anmeldedatum: 26.03.09
Wohnort: Nähe München
Version: ab 2014a
     Beitrag Verfasst am: 11.09.2018, 17:41     Titel:
  Antworten mit Zitat      
Hallo,

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 ;)
Private Nachricht senden Benutzer-Profile anzeigen
 
Shanox
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 20
Anmeldedatum: 15.08.18
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 11.09.2018, 19:29     Titel:
  Antworten mit Zitat      
Danke ihr beiden!

Habt mir sehr geholfen! Funktioniert so, wie ich es mir vorgestellt habe! Smile
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

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
.



goMatlab ist ein Teil des goForen-Labels
goForen.de goMATLAB.de goLaTeX.de


 Impressum  | Nutzungsbedingungen  | Datenschutz  | Werbung/Mediadaten | Studentenversion | FAQ | goMatlab RSS Button RSS


Copyright © 2007 - 2018 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
Partner: LabVIEWforum.de

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.