Comment faire pour convertir les index de la matrice triangulaire dans la rangée, coordonnées de la colonne?

Question

I ont idxs:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15...ect. 

qui sont des indices de noeuds de matrice (y compris les éléments diagonaux):

1 
2 3 
4 5 6 
7 8 9 10 
11 12 13 14 15 
16 17 18 19 20 21 
etc.... 

et i doivent i obtenir, j les coordonnées à partir des indices de thees:

1,1 
2,1 2,2 
3,1 3,2 3,3 
4,1 4,2 4,3 4,4 
5,1 5,2 5,3 5,4 5,5 
6,1 6,2 6,3 6,4 6,5 6,6 
etc.. 

lorsque j'ai besoin de calculer les coordonnées, je n'ai qu'un idx et ne peux pas accéder aux autres.

Answer 1

pas optimisé du tout:

int j = idx; 
int i = 1; 

while(j > i) { 
    j -= i++; 
} 

optimisé:

int i = std::ceil(std::sqrt(2 * idx + 0.25) - 0.5); 
int j = idx - (i-1) * i/2; 

Et voici la démonstration:

Vous êtes à la recherche i tel que:

sumRange(1, i-1) < idx && idx <= sumRange(1, i) 

lorsque sumRange (min, max) somme des entiers entre min et max, tous deux inclus. Mais puisque vous savez que:

sumRange(1, i) = i * (i + 1)/2 

Ensuite, vous avez:

idx <= i * (i+1)/2 
=> idx <= i * (i+1) 
=> 2 * idx <= i² + i + 1/4 - 1/4 
=> 2 * idx + 1/4 <= (i + 1/2)² 
=> sqrt(2 * idx + 1/4) - 1/2 <= i