Raggruppare celle di una matrice ad n^2 alla volta

[guylmaster]

Mi spiego ho una matrice di una qualsivoglia dimensione, mettiamo che sia 5 righe e 5 colonne.
Vorrei scorrere la matrice in maniera tale da leggere n celle per volta che siano allineate a formare un quadrato, ovvero se n è uguale a 2 voglio leggere:

cella riga i colonna j
cella riga i colonna j+1
cella riga i+1 colonna j
cella riga i+1 colonna j+1

Come posso fare?

Per altro se la matrice è 5x5 ed n è 2 allora allora voglio leggere [0][0] [0][1] [1][0] [1][1], poi [0][2] [0][3] [1][2] [1][3] e poi alla fine della riga voglio leggere solo [4][0] [4][1].

Idem per l'ultima riga dove avrò invece da leggere i nodi a due a due. Non so se mi spiego. Ci sto davvero perdendo la testa quindi qualsiasi suggerimento è ben accetto

[mmx[ngg]]

Per cosa ti serve ?

Cmq nell'esempio che hai riportato, all'ultima riga non hai mica un quadrato...se N è 3 che dovrebbe fare ?

[pabloski]

Non mi pare che si possa fare niente di diverso da

for i = 0 to n-1
   for j = 0 to n-1
      quadrato[i][j] = matrice[i][j]
   endfor
endfor

cioè praticamente non puoi fare altro che scorrere le prime n righe e leggerti le prime n colonne per ogni riga

se stai pensando a qualcosa tipo memcpy, ti faccio notare che le matrici in genere sono organizzate come vettori di vettori, cioè vengono memorizzate contiguamente tutte le righe, ognuno c'avrà le sue m colonne

quindi facendo memcpy, andresti a leggere n righe x m colonne e non nxn come vuoi fare tu

potresti al massimo leggerti con memcpy n righe per ogni colonna, però ci vuole comunque almeno un for

insomma devi saltare, per ogni riga, le ultime (m-n) colonne

[banryu79]

@guylmaster: forse potresti ottenere risposte più circostanziate se scrivessi tutto in un solo thread, così chi ti legge può capire l'intero problema e il suo contesto e aiutarti meglio a trovare una soluzione.

Se devi lavorare con le matrici, fatti una classe ad-hoc per wrappare gli array di array nudi&crudi e definisciti dei metodi di utilità.
Ad esempio, guarda questo vecchio thread
Potresti ad esempio implementare un metodo (getSubRegion) che accetta le coordinate di una cella della matrice (riga,colonna) e la dimensione della sotto-regione (voglio una 9x9, quindi un dim=3) desiderata e che restituisce la sottoregione.

Se le coordinate (riga, colonna) assieme alla dimensione della sottoregione (dim) definiscono una sottoregione che "cade parzialmente fuori" della regione allora potresti riempire i valori delle celle "invalide" con un valore dummy che decidi te, o fare altro: tutto dipende da cosa devi fare in ultima analisi: cioè quale problema stai risolvendo?

[guylmaster]

Allora il problema che sto risolvendo, ed in caso potesse essere utile specifico che lo sto risolvendo in Java, è quello di avere una mappa rappresentata tramite una matrice e devo rappresentare su questa mappa delle rotte.

Per rappresentare delle rotte, sopratutto per mappe molto grandi, devo poter raggruppare assieme più celle della mappa originale andandomi a creare una mappa virtuale rappresentata da una matrice più piccola.

Non sto riuscendo ad abbozzare nessun conduce e sto avendo un po' di difficoltà. Ora comunque mi leggo la discussione che mi hai citato.

[guylmaster]

Ho provato a buttare giù questo codice ma mi sono accorto che le prende male e che ho sbagliato il ragionamento, però magari potrebbe essere un inizio "da correggere" :

package lettura_mappa;

import java.util.ArrayList;

public class Partiziona_matrice {
	public Partiziona_matrice() 
	{
		
	}
	public ArrayList<ArrayList<Coppia>> partiziona(int n, int righe, int colonne)
	{
		ArrayList<ArrayList<Coppia>> partizione = new ArrayList<ArrayList<Coppia>>();
		
		int cella= 0;
		int r= 0;
		int c = 0;
		float rc = righe * colonne;
		float numero_celle = (float)Math.ceil((rc/n) );
		while(cella < numero_celle)
		{
			int righe_prese = 0;
			int colonne_prese = 0;
			ArrayList<Integer> rp = new ArrayList<Integer>();
			ArrayList<Integer> cp = new ArrayList<Integer>();
			ArrayList<Coppia> nodi_cella = new ArrayList<Coppia>();
			
			int i = 0;
			while(r < righe && righe_prese < n)
			{
				rp.add(i, r);
				i++;
				r++;
				righe_prese++;
			}
			int j = 0;
			while(c < colonne && colonne_prese < n)
			{
				cp.add(j, c);
				j++;
				c++;
				colonne_prese++;
			}
			
			for (int k = 0; k < rp.size(); k++) {
				for (int h = 0; h < cp.size(); h++) {
					nodi_cella.add(new Coppia(rp.get(k), cp.get(h) ));
				}
				
			}
			partizione.add(nodi_cella);
			cella++;
		}
		
		
		return partizione;
	}
	
	public static void main(String [] args)
    {
		Partiziona_matrice pa = new Partiziona_matrice();
		System.out.println(pa.partiziona(2, 5, 5));
	}

}

Così facendo mi ritorna:

[[(0,0), (0,1), (1,0), (1,1)], [(2,2), (2,3), (3,2), (3,3)], [(4,4)], [], [], [], [], [], [], [], [], [], []]

E non va bene.

Un'altra idea che mi sta venendo in mente è che scrivo prima tutte le coppie riga e colonna in una lista e poi mi invento un modo per "partizionare" la lista in modo corretto. Voi avete qualche suggerimento?

[wingman87]

Originariamente inviato da banryu79

Potresti ad esempio implementare un metodo (getSubRegion) che accetta le coordinate di una cella della matrice (riga,colonna) e la dimensione della sotto-regione (voglio una 9x9, quindi un dim=3) desiderata e che restituisce la sottoregione.

Quoto, scomponendolo il problema è molto più semplice di quello che sembra.

[PGI-Bis]

Se prendi un rettangolo e pensi "adesso me lo scorro in porzioni di larghezza W e altezza H" che fai? Disegni un rettangolo 0,0,W,H e lo sposti orizzontalmente di W unità finchè non arrivi alla fine della riga. Quando sei lì ti sposti di H unità in basso e riparti da x=0 fino alla fine della riga a passi di W unità.

Detto altrimenti, il ciclo che faresti per scandire l'intera matrice:

for(int r = 0; r < rowCount; r++) {
    for(int c = 0; c < colCount; c++) {
    }
}

altro non è che un caso particolare di lettura di una sottomatrice:

Cella start = new Cella(riga, colonna);
Dimension size = new Dimension(numeroRighe, numeroColonne);
for(int r = start.riga; r < start.riga + size.righe; r++) {
    for(int c = start.colonna; c < start.colonna + size.colonne; c++) {

    }
}

in cui start è (0,0) e size è la dimensione dell'intero "rettangolo".

A onor del vero, per quanto dice mmx[ngg], le condizioni sarebbero

r < Math.min(start.riga + size.righe, MR)
c < Math.min(start.colonna + size.colonne, MC)

con MR e MC numero di righe e colonne della matrice da leggere. Ma non stiamo qua a spaccar capelli in quattro - che non ce li abbiamo neanche.

Comunque se è così allora è chiaro che il procedimento di scansione della matrice di dimensioni MRxMC a blocchi di dimensione BRxBC altro non è che la ripetizione del ciclo suddetto - cioè della lettura di una singola sottomatrice - variando start.riga da 0 a MR a passi di BR unità e start.colonna da 0 a MC a passi di BC unità.

Se puoi evita un array di array (o un array list di array list) e usa un array singolo, lo "leggi" come una matrice con l'accesso tramite subscript (r,c) = r * w + c = i e puoi così usare arraycopy per "copiare" le righe dalla matriciona alla matricina.

Comunque fai prima la versione coi for.

[mmx[ngg]]

MC = MaxCol - (MaxCol % N);
MR = MaxRig - (MaxRig % N);

MC = MaxCol;
MR = MaxRig;

for (C = 0; C < MC; C+=N)
  for (R = 0; R < MR; R+=N)
    for (Y = 0; Y < N && C + Y < MC; Y++)
      for (X = 0; X < N && R + X < MR; X++)
        NMatrice[Y, X] = BMatrice[C+Y, R+X]

NMatrice è quella più piccola che devi allocare di volta in volta
BMatrice è quella di origine
Se inizializzi MC e MR con il primo metodo ti tira fuori solo quelli che te definisci quadrati (matrici della stessa dimensione visto che scarta quelle più piccole)
Se inizializzi con il secondo metodo tiri fuori tutto e le matrici ai margini saranno più piccole delle altre
Se spieghi meglio è meglio perchè sono letteralmente andato a naso

P.S.

Ho letto ora l'altro post, parli di grafi, archi, tracciamento linee ecc. ecc. ma non è che ti serve una specie di BSP tree ?

[mmx[ngg]]

Originariamente inviato da PGI-Bis

Ma non stiamo qua a spaccar capelli in quattro - che non ce li abbiamo neanche.

[guylmaster]

Originariamente inviato da mmx[ngg]

MC = MaxCol - (MaxCol % N);
MR = MaxRig - (MaxRig % N);

MC = MaxCol;
MR = MaxRig;

for (C = 0; C < MC; C+=N)
  for (R = 0; R < MR; R+=N)
    for (Y = 0; Y < N && C + Y < MC; Y++)
      for (X = 0; X < N && R + X < MR; X++)
        NMatrice[Y, X] = BMatrice[C+Y, R+X]

NMatrice è quella più piccola che devi allocare di volta in volta
BMatrice è quella di origine
Se inizializzi MC e MR con il primo metodo ti tira fuori solo quelli che te definisci quadrati (matrici della stessa dimensione visto che scarta quelle più piccole)
Se inizializzi con il secondo metodo tiri fuori tutto e le matrici ai margini saranno più piccole delle altre
Se spieghi meglio è meglio perchè sono letteralmente andato a naso

P.S.

Ho letto ora l'altro post, parli di grafi, archi, tracciamento linee ecc. ecc. ma non è che ti serve una specie di BSP tree ?

Cos'è un BSP tree?
Ad ogni modo ho risolto, o almeno spero (devo fare qualche prova per esserne totalmente sicuro).

[mmx[ngg]]

ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#6.txt

Per fartela spicciola è un algoritmo che potrebbe tornarti comodo per calcolare in tempi umani le entità circostanti (mari o terre che siano) o in alternativa potresti provare ad adattare una parte della struttura di un diagramma di Voronoi http://en.wikipedia.org/wiki/Voronoi_diagram

[guylmaster]

Originariamente inviato da mmx[ngg]

ftp://ftp.sgi.com/other/bspfaq/faq/bspfaq.html#6.txt

Per fartela spicciola è un algoritmo che potrebbe tornarti comodo per calcolare in tempi umani le entità circostanti (mari o terre che siano) o in alternativa potresti provare ad adattare una parte della struttura di un diagramma di Voronoi http://en.wikipedia.org/wiki/Voronoi_diagram

Cioè?

Perché il mio problema successivo, ora che ho partizionato la matrice è questo:

Associo ad ogni partizione un indice crescente che parte da 1 e memorizzo tutte le coppie (indice,paritzione) in un hashmap.

Adesso però mi servirebbe, dato un indice calcolarmi tutti gli indici delle partizioni adiacenti, ovvero quelle che si trovano a Nord, Nord-est, Nord-ovest, Sud, Sud-est, Sud-overt,est, ovest.

A questo punto avrei solo l'hashmap, l'indice della partizione di cui voglio calcolarmi gli adiacenti ed il numero di righe e di colonne delle matrice delle partizioni.
Ovvero prendendo una matrice delle partizioni 3x3:

1 2 3
4 5 6
7 8 9

Se mi viene dato l'indice 7 voglio che mi si ritorni: 4, 5, 6, 8.

[mmx[ngg]]

6 ?

Diciamo che ho capito perchè ho letto l'altro topic (è quello in diagonale) altrimenti ti prendevo per pazzo

Ti stai complicando la vita da morire, per quello che ti serve fare utilizzare un sottoinsieme di matrici è un pò folle. Leggiti come funziona Voronoi (guarda qua).

C'è tanto di codice in javascript che processa le informazioni anche step x step (non ho visto il codice quindi può far schifo come essere ottimo). Partendo dal presupposto che i puntini sono il punto centrale della tua entità, l'algoritmo processa tutti i punti di intersezione. E' quello che ti serve no ?