4
votes

Trouvez le premier et le dernier index de chaque coordonnée dans une liste de coordonnées à l'aide de MATLAB

J'ai une liste de coordonnées (x, y) et j'ai besoin de trouver l'index de la première et de la dernière occurrence de chaque coordonnée de la liste. Exemple (dans mon use-cast j'ai ~ 30M de coordonnées):

ind = sub2ind(size(Mlast),y-y1+1, x-x1+1);
t = (1:length(x))';
Mlast(ind) = t;
Mfirst = ???

Je l'ai implémenté en utilisant une matrice et une boucle, ça ressemble à ça, mais c'est lent:

XXX

J'ai essayé de vectoriser tout le processus, mais je ne réussis qu'avec Mlast:

x1 = min(x);
y1 = min(y);
x2 = max(x);
y2 = max(y);
tic
Mlast = zeros(y2-y1+1, x2-x1+1);
Mfirst = Mlast;

ind = sub2ind(size(Mlast),y-y1+1, x-x1+1);

for i1=1:length(ind)
    first = Mfirst(ind(i1));

    if first == 0
        first = i1;
    end

    Mlast(ind(i1)) = i1;
    Mfirst(ind(i1)) = first;
end

Y a-t-il un moyen d'obtenir cela pour le premier occurrence aussi?

arrays matlab unique

1 commentaires

find (x == y, 1, 'first') trouve la première entrée confirmant le critère. D'autres fonctions utiles peuvent être unique ()

3 Réponses :

5
votes

La fonction unique peut faire que:

[~, b, c] = unique([x(:) y(:)], 'rows', 'first');
first = b(c).';
[~, b, c] = unique([x(:) y(:)], 'rows', 'last');
last = b(c).';

3 commentaires

En effet cela fonctionne, mais c'est env. 20x plus lent que la version avec la boucle

Bizarre; Je me serais attendu à ce que unique soit assez rapide

@LuisMendo: Oui, mon mal.

2
votes

En supposant que les coordonnées sont des entiers positifs et en particulier lorsque la plage de coordonnées est petite, vous pouvez utiliser accumarray :

ifirst = accumarray(ind(:), 1:numel(ind), [], @min,[],1);
ilast  = accumarray(ind(:), 1:numel(ind), [], @max,[],1);

Pour les plages plus élevées, vous pouvez utiliser l'option sparse:

x1 = min(x);
y1 = min(y);
x2 = max(x);
y2 = max(y);
sz = [y2-y1+1, x2-x1+1];
ind = sub2ind(sz,y-y1+1, x-x1+1);

ifirst = accumarray(ind(:), 1:numel(ind), [], @min);
ilast  = accumarray(ind(:), 1:numel(ind), [], @max);
Mfirst = ifirst(ind);
Mlast  = ilast(ind);

1 commentaires

Ça marche! Mais c'est environ 30 fois plus lent que l'implémentation avec la boucle. Mais intéressant à apprendre sur accumarray ...

1
votes

Si vous avez 30M points, vous n'avez probablement pas assez de mémoire pour cette méthode ... mais c'est assez rapide pour les petits tableaux

x = [1 3 7 1 3];
y = [5 1 6 5 1];

g = findgroups( x, y );   
first = zeros( size( x ) );
last = first;
for ii = 1:max(g)
    idx = (ii==g);
    first( idx ) = find( idx, 1, 'first' );
    last( idx ) = find( idx, 1, 'last' );
end

Modifier Vous pouvez également le faire avec findgroups , et en boucle sur les coordonnées uniques au lieu de chaque coordonnée pour avoir une boucle potentiellement beaucoup plus courte ...

x = [1 3 7 1 3];
y = [5 1 6 5 1];

xy = cat( 3, x, y );

chk = all( xy == permute( xy, [2 1 3] ), 3 );

[~,first] = max( chk );
[~,last] = max( flipud( chk ) );
last = size(chk,1) - last + 1;

0 commentaires