wie finden Sie k-TEN nächsten Nachbarn eines Punktes in eine Reihe von Punkt

Habe ich eine Reihe von Punkt (x,y) auf der 2d-Ebene. Gegeben ein Punkt (x0,y0), und die Zahl k, so finden Sie den k-TEN nächsten Nachbarn von (x0,x0) im Punkt gesetzt. Im detail, den Punkt zu setzen sind vertreten durch zwei Arrays: x und y. Der Punkt (x0,y0) ist gegeben durch den index i0. Es bedeutet, x0=x(i0) und y0=y(i0).

Gibt es eine Funktion oder etwas in Matlab hilft mir dieses problem. Wenn Matlab nicht haben diese Art von Funktion, können Sie schlagen jede andere wirksame Möglichkeiten.

BEARBEITEN: ich habe zur Berechnung dieser Art von Entfernung für jeden Punkt (x0,y0) im set. Die Größe des sets ist etwa 1000. Der Wert von k sollte etwa sqrt(1500). Das Schlimmste ist, dass ich dies viele Male. Bei jeder iteration werden die änderungen an, und ich berechne die Entfernungen wieder. So, die Laufzeit ist auf ein kritisches problem.

InformationsquelleAutor James Do | 2012-02-22
  1. 6

    wenn Sie dies tun, überprüfen Sie für viele Punkte möchten Sie vielleicht, um zu konstruieren, ein inter-Punkt-Abstand-Tabelle

    squareform(pdist([x y]))
    • Ja. Ich wird dies für alle Punkte in der Menge. Also eine Art Tabelle, der Abstand würde helfen Sie sparen die Laufzeit. Ich finden Sie heraus, wie squareform-Funktion funktioniert in meinem problem. Ich danke Ihnen sehr.
    • die Funktion ist pdist eigentlich squareform, nur macht das die einer quadratischen matrix aus pdist der vector-Ausgang
    • Dank zamazalotta. Ich habe es.
    • Aber nur, wenn Sie über die Statistik toolbox.
    • es funktioniert für mich. Vielleicht ist es nicht die beste Lösung, aber es ist einfach zu implementieren und zu verwenden. Um ehrlich zu sein, habe ich nicht mehr viel Zeit bis zum Ende des Codes. Ich danke Ihnen sehr.
    • Das ist O(N^2), wobei N die Anzahl der Punkte, mit jeder Abfrage, dann wird O(N lg N). Ein kd-Baum, die unten erwähnt werden, und unter bestimmten Bedingungen durch knnsearch, ist in der Regel viel schneller, wenn man O(N lg^2 N) zu konstruieren, O(lg N) für 1-nearest neighbour, und, ich vermute, um O(k(lg k)(lg N)) für k-nächsten Nachbarn, wenn k klein ist und mit einem günstigen dataset (denken: über binäre Suche). (Das bedeutet zum Beispiel, dass wenn Sie über 10000 Punkte, es sollte irgendwo um 100-bis 1000-mal schneller.) Daher knnsearch ist viel lieber,.

    InformationsquelleAutor zamazalotta
  2. 4

    Wenn Sie über die Statistik toolbox, die Sie verwenden können, die Funktion knnsearch.

    • knnsearch scheint eine Lösung aber ich bin mir nicht sicher, wie Sie anzuwenden knnsearch, um mein problem genau. Ich werde es finden. Trotzdem, können Sie mir mehr Details über die Art und Weise der Verwendung knnsearch. Ich danke Ihnen sehr.
    • Haben Sie schaute auf die Matlab-Hilfe (link Hinzugefügt, um meine obige Antwort)?
    • Ich lese die online-Dokument über knnsearch aber es ist ein wenig erschweren zu mir und ich habe nicht wirklich viel Zeit, um zu verstehen und zu verwenden. Ich habe versucht, die einfacheren Ansatz. Es braucht mehr Zeit, der läuft, aber ich werde versuchen, diesen Ansatz zuerst. Danke für Eure Hilfe.
    InformationsquelleAutor 3lectrologos
  3. 2

    Einen brute-force-Algorithmus wäre so etwas wie dieses:

    array x[n] = ()
array y[n] = () 
array d[n] = ()

... populate x and y arrays with your n points ...

/* step over each point and calculate its distance from (x0, y0) */
for i = 1 to n
do
  d[i] = distance((x0, y0), (x[i], y[i])
end 

/* sort the distances in increasing order */
sort(d)

/* the k'th element of d, is the k'th nearest point to (x0, y0) */
return d[k]
    • vielen Dank für Ihre Hilfe!
    InformationsquelleAutor ardnew
  4. 2

    Die freie und opensource VLFeat toolbox enthält ein kd-Baum Implementierung, unter andere nützliche Dinge.

    • ich danke Ihnen sehr. Ich werde suchen, ob Sie helfen kann.
    InformationsquelleAutor Maurits
  5. 2

    Den brute-force-Ansatz sieht wie folgt aus:

    %Create some points
n = 10;
x = randn(n,1);
y = randn(n,1);

%Choose x0
ix0 = randi(n);

%Get distances
d = sqrt(...
    (x - x(ix0) ).^2 + ...
    (y - y(ix0) ).^2 );

%Sort distances
[sorted_Dstances, ixSort] = sort(d);

%Get kth point
k = 3;
kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element.
    • Sollten Sie nicht entfernen Sie das element selbst? Denken Sie über den Fall k=1
    • Guter Punkt. Ich mag es allgemein nicht ändern die Größen von match-Vektoren wie diese. Vielleicht fügen Sie ein '+1', um die endgültige Indizierung. EDIT: obwohl, das hinterlässt eine Lücke, wenn es einen Punkt gibt, identisch zu dem ersten Punkt. Wenn Sie gewährleisten wollen, die Antwort ist ein anderer Punkt, auch wenn einige Punkt könnte gleich sein, dann wird mehr Arbeit gebraucht.
    • es hat keinen Sinn, das entfernt auch die gleichen Punkte. wenn Sie 5 gleiche Punkte an der Stelle, die Sie suchen, sind die 3. am weitesten Abstand sollte 0 sein
    • ich danke Ihnen sehr! aber ich habe zur Berechnung dieser Art von Strecke mit jedem Punkt in dem Satz. So, es scheint, dass dies Konzept ist ein wenig einfacher, als ich erwartet hatte. Ich bin traurig, dass ich nicht früher klären.
    InformationsquelleAutor Pursuit
Schreibe einen Kommentar