WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Direktionale nächste Nachbarn einsammeln -- schneller?

 

Nras
Forum-Meister

Forum-Meister


Beiträge: 608
Anmeldedatum: 21.02.12
Wohnort: ---
Version: 7.12.0.635 (R2011a)
     Beitrag Verfasst am: 11.12.2013, 12:25     Titel: Direktionale nächste Nachbarn einsammeln -- schneller?
  Antworten mit Zitat      
Hallo liebes Forum,
für ein Projekt möchte ich vom Ursprung aus von einem Datensatz von Punkten mit x und y Koordinaten, eine Anzahl nPoints an direktionalen nächsten Nachbarn finden. Als Beispiel: Die "Richtung" der Punkte sei dadurch gegeben, in welchem Quadrant die Punkte liegen, das ist dann das "Segment" in dem der jeweilige Punkt liegt. Am liebsten hätte ich dann etwa nPoints/4 aus jedem Segment, wenn ein Segment aber weniger Punkte beinhaltet, dann muss das aus den anderen Segment geholt werden.

Meine Funktion dafür funktioniert, wird aber sehr oft augerufen und ist mit > 90% der Laufzeit das absolute Bottle Neck. Hier ist ein Auszug aus dem Code. Das in der while Schleife wird dabei mehrere Millionen mal aufgerufen und ist einfach zu lahm. Ich würde mich über neue Ansätze, die nächsten Nachbarn aus den Quadranten zu finden, sehr freuen.
Code:
% Beispieldaten erzeugen, die irgendwie um (0,0) in der Ebene liegen. Finde
% die Quadranten, in denen die Punkte P liegen.

P = rand(100,2)-0.2;         % Daten um (0,0) streuen
P = [P; rand(30,2)*0.1];  % künstlich den ersten Quadranten dicht besetzen

% ----- Ordne dem Punkten in Prot ihren Quadranten (ihr Segment) zu
segmentedIndices = cell(4,1);
for iQuadrant = 1:4
    switch iQuadrant
        case 1  
            idx = find(P(:,1) > 0 & P(:,2) > 0);
        case 2        
            idx = find(P(:,1) < 0 & P(:,2) > 0);          
        case 3
            idx = find(P(:,1) < 0 & P(:,2) < 0);
        case 4  
            idx = find(P(:,1) > 0 & P(:,2) < 0);
    end
    segmentedIndices{iQuadrant,1} = idx;
end

% ----- nach euklidischem Abstand zum Ursprung sortierte Indexlisten
order = cell(size(idx));
for seg = 1:4;
    [~,idx] = sort(sqrt((P(segmentedIndices{seg},1)).^2 + (P(segmentedIndices{seg},2)).^2));
    order{seg,1} = segmentedIndices{seg}(idx);
end

%% ------ Ab hier ist es zu langsam ------
% Jetzt sind die vier Richtungen (Quadranten) fertig und das Sammeln der
% Punkte beginnt.
nPoints = 50;
pointsgathered = 0; % bereits gesammelt
seg = 0;            % welches Segment?
takenFromSeg = zeros(4,1);  % wieviele aus welchem Segment genommen?

% man kann nicht mehr sammeln als da sind
totalInSeg = cellfun(@length, segmentedIndices);
nPoints = min(nPoints,sum(totalInSeg));
idxList = NaN(nPoints,1);

% ----- hier wird eingesammelt
while pointsgathered < nPoints
   
    % update segment to take point out of ...->1->2->3->4->1-> ...
    seg = mod(seg,4)+1;
   
    % if there are less taken from the segment seg, than there are points
    % in that segment, we take one more out of it.
    if takenFromSeg(seg) < totalInSeg(seg)
        idxList(pointsgathered+1,1) = order{seg}(takenFromSeg(seg)+1);
        pointsgathered = pointsgathered + 1;
        takenFromSeg(seg) = takenFromSeg(seg)+1;
    % else-- there are no more points to take from that segment, so we
    % carry on with the next segment    
    end
   
end

% ----- Beispielplot
figure
plot(P(:,1),P(:,2),'k.')
hold on
plot(P(idxList,1),P(idxList,2),'ro')
legend('alle Punkte','direktionale nächste Nachbarn')
% Hilfslinien
plot([0,0],[-0.4,1],'k-')
plot([-0.4,1],[0,0],'k-')
 

Anbei ebenfalls ein Bild zur Visualisierung.

direktionaleNachbarn.png
 Beschreibung:

Download
 Dateiname:  direktionaleNachbarn.png
 Dateigröße:  5.83 KB
 Heruntergeladen:  235 mal
Private Nachricht senden Benutzer-Profile anzeigen


Nras
Themenstarter

Forum-Meister

Forum-Meister


Beiträge: 608
Anmeldedatum: 21.02.12
Wohnort: ---
Version: 7.12.0.635 (R2011a)
     Beitrag Verfasst am: 11.12.2013, 12:48     Titel:
  Antworten mit Zitat      
Eine weitere Umschreibung des Problems könnte folgende sein, die beeinflusst vielleicht nicht so sehr, wie der obige Beitrag, durch vorgefertigten Code:

Ich habe 4 Töpfe, i = 1 bis 4. Dabei hat der i-te Topf N_i Elemente und ich möchte daraus n_i, mit folgenden Einschränkungen
1) \sum n_i = N (ich ziehe am Ende genau N Elemente)
2) alle N, N_i \text{ und } n_i sind natürliche Zahlen
3) n_i \leq N_i (nicht mehr ziehen als da sind)
4) n_i sollte ungefähr N/4 ergeben, im Idealfall, wenn alle Töpfe mindestens N/4 Elemente haben.
5) \sum N_i \geq N. (Es sind genug Elemente auf die Töpfe verteilt).

Eigentlich ist es genau dieses Szenario, das ich auf irgendeine Weise gerne lösen möchte. Falls da jemand einen schnelleren Ansatz hat als den, den ich oben postete, dann wäre das dufte.

Viele Grüße,
Nras.
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
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2025 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.