Найти первый и последний индекс каждой координаты в списке координат, используя MATLAB - PullRequest
Новая
       6

Найти первый и последний индекс каждой координаты в списке координат, используя MATLAB

0 голосов
/ 27 февраля 2019

У меня есть список координат (x, y), и мне нужно найти индекс первого и последнего вхождения каждой координаты в списке.Пример (в моем использовании-приведении у меня ~ 30M координат): 

x = [1 3 7 1 3];
y = [5 1 6 5 1];
first = [1 2 3 1 2];
last  = [4 5 3 4 5];

Я реализовал это с помощью матрицы и цикла, это выглядит так, но медленно: 

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

Я пытался векторизовать весь процесс, но мне удалось только с Mlast: 

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

Есть ли способ получить это также для первого случая?

Ответы [ 3 ]

0 голосов
/ 27 февраля 2019

Предполагая, что координаты являются положительными целыми числами, и, особенно, когда диапазон координат небольшой, вы можете использовать accumarray: 

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);

Для более высоких диапазонов вы можете использовать параметр разреженного:

ifirst = accumarray(ind(:), 1:numel(ind), [], @min,[],1);
ilast  = accumarray(ind(:), 1:numel(ind), [], @max,[],1);
0 голосов
/ 28 февраля 2019

Если у вас 30M баллов, вам, вероятно, не хватит памяти для этого метода ... но он довольно быстр для небольших массивов 

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;

Редактировать Вы также можете сделать это с помощью findgroups и циклически проходить по уникальным координатам вместо каждой координаты, чтобы иметь потенциально гораздо более короткий цикл ... 

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

Edit2 Я думаю, что оба они довольно медленны по сравнению с другими ответами здесь ...

0 голосов
/ 27 февраля 2019

Функция unique может сделать это: 

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