|
|
|
Suche nach nächstem Nachbar für meinen Anwendungsfall |
|
| mesasimo |
Forum-Newbie
|
 |
Beiträge: 2
|
|
|
|
Anmeldedatum: 22.06.14
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 22.06.2014, 00:50
Titel: Suche nach nächstem Nachbar für meinen Anwendungsfall
|
 |
Hallo Community,
ich habe Punkte in der Ebene, die ähnlich verteilt sind wie in diesem Beispielplot (im Anhang) zu sehen.
Sie liegen alle in einem Bereich von x = [0,10] und y = [0,20]. Viele liegen nahe bei einander und einige vereinzelt weiter weg. Nun möchte ich für einen beliebigen Punkt den nächst gelegenen Nachbarn ermitteln und das sehr schnell. Was wäre da die beste Lösung aufgrund der Verteilung der Werte? Kd Baum evtl.?
Gruß
| Beschreibung: |
|
Download |
| Dateiname: |
beispiel.png |
| Dateigröße: |
6.17 KB |
| Heruntergeladen: |
467 mal |
|
|
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.448
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 22.06.2014, 09:29
Titel:
|
|
Hallo,
ich würde (vektorisiert) den Abstand jedes Punktes vom gewünschten Punkt berechnen und davon das Minimum nehmen. Das sollte selbst bei einer relativ großen Anzahl Punkte noch "sehr schnell" gehen.
Grüße,
Harald
|
|
|
|
| mesasimo |
Themenstarter
Forum-Newbie
|
|
Beiträge: 2
|
|
|
|
Anmeldedatum: 22.06.14
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 22.06.2014, 17:28
Titel:
|
|
|
Was tue ich aber, wenn ich ein sehr feines Grid über meinen Bereich drüber lege und dadurch sehr oft die Nachbarschaftssuche durchführe? Dann würde mir ein etwas schnellerer Ansatz eine große zeitliche Verbesserung bringen. Deswegen tendiere ich zu einem Ansatz der darauf basiert, dass der eine Struktur aufbauen, die den Bereich unterteilt und danach nicht mehr mit jedem Datenpunkt getestet wird, sondern nur noch mit denen in einem gewissen Teilbereich (ähnlich wie beim Kd Baum). Nur da ich viele Punkte habe die nahe bei einander liegen wird der Kd Baum nicht die richtige Wahl sein...
|
|
|
|
| Harald |
Forum-Meister
|
|
Beiträge: 24.448
|
|
|
|
Anmeldedatum: 26.03.09
|
|
|
|
Wohnort: Nähe München
|
|
|
|
Version: ab 2017b
|
|
|
|
|
|
|
Verfasst am: 22.06.2014, 17:39
Titel:
|
|
Hallo,
wieviele Datenpunkte, wieviele Gitterpunkte?
Das Berechnen sämtlicher Distanzen ist so schnell, dass ich generell Zweifel habe, dass anderes schneller sein wird.
Grüße,
Harald
|
|
|
|
| steff |
Gast
|
|
Beiträge: ---
|
|
|
|
Anmeldedatum: ---
|
|
|
|
Wohnort: ---
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 07.06.2018, 09:06
Titel: Das wage ich zu bezweifeln
|
|
Natürlich war die Frage sehr allgemein formuliert, aber eene Brute-Force Methode (wie vorgeschlagen) wird sicher nur bei kleinen Datenmengen respektive wenigen Berechnungen schneller sein, wobei "wenig" zu spezifizieren ist. Ab einer gewissen Grenze wird ein kd-Baum wesentlich schneller sein (grob O(log(n)) anstelle n*n). Der einzige Aufwand, der hinzukommt, ist das Aufstellen des kd-Baumes, welcher auch Zeit benötigt und welecher jedesmal neu erstellt werden muss, sobald sich die Datenstruktur, in der gesucht werden soll, ändert.
Insofern kann man die Antwort nicht so pauschal stehen lassen. Ein feineres Grid mit vielen Datenpunkten (> 1 Mio (?)) und eine Datenpunktwolke von 20 zufälligen Punkte wird sicherlich per kd-Baum schneller zugeordnet sein, als Brute-Force.
Ansonsten einfach ausprobieren: tic ...toc ...
|
|
|
|
|
|
|
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
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
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.
|
|
