[ALGORITMO] Prendere una percentuale di punti di una rotta

[Neptune]

Salve,
ho il classico problema algoritmico che mi sta facendo impazzire, però questa volta è molto semplice da spiegare:

Ho una rotta composta da una lista contenente un certo numero di punti, io voglio prendere solo una certa percentuale della rotta, come posso fare?

Ovviamente se ho la rotta rappresentata dalla seguente lista di punti 1,2,3,4,5,6,7,8,9,10 e voglio prenderne il 30% voglio grossomodo che mi restituisca qualcosa del tipo:
1,5,10

Ovvero voglio che i punti li prenda in maniera uniforme nella mia lista e non che vengano presi tutti uno dopo l'altro.

Come posso fare considerato che le uniche informazioni che io avrò saranno la lista, quindi il numero totale dei punti contenuti e la percentuale di punti che voglio prendere?

Io stavo pensando a qualcosa del tipo se i è la posizione del punto nella lista allora se i % qualcosa == 0 allora prendilo/non prenderlo. Non riesco però bene a formulare questa condizione. Avete qualche suggerimento?

Vi ringrazio in anticipo per l'aiuto,
Neptune.

[MItaly]

Puoi scremarli in maniera brutale appunto prendendo un punto ogni tot; in Python sarebbe ad esempio:

# prende il 20% dei punti
percentualePunti = 0.2
numeroPunti=len(listaPunti)*percentualePunti
for i in range(0, numeroPunti):
    # lo "step" tra i punti è l'inverso della percentuale
    listaOutput.append(listaPunti[int(i/percentualePunti)])

O anche, potresti invece sostituire ogni punto con una media (eventualmente pesata) sulla "finestra di punti" che va a sostituire (un po' il concetto dello smoothing).

Ma secondo me questi metodi non sono una buona idea, se hai una rotta è facile che ti serva poco dettaglio in punti dove è sostanzialmente dritta, ma tanti dove gira molto. Personalmente cercherei calibrare l'accuratezza in maniera diversa in zone diverse, ad esempio andando a vedere - ad esempio - la norma del laplaciano discretizzato calcolato sulla successione dei tuoi punti, che dovrebbe darti la velocità di cambiamento della direzione della tua curva sul piano. Ottenuta la successione dei valori della norma del laplaciano nei vari punti ci applicherei uno smooth e userei i valori così ricavati per determinare l'importanza relativa dei vari punti, in base a cui andrei a scegliere in quali zone campionare maggiormente per il mio "percorso semplificato".

[Neptune]

Originariamente inviato da MItaly
Puoi scremarli in maniera brutale appunto prendendo un punto ogni tot; in Python sarebbe ad esempio:

# prende il 20% dei punti
percentualePunti = 0.2
numeroPunti=len(listaPunti)*percentualePunti
for i in range(0, numeroPunti):
    # lo "step" tra i punti è l'inverso della percentuale
    listaOutput.append(listaPunti[int(i/percentualePunti)])

O anche, potresti invece sostituire ogni punto con una media (eventualmente pesata) sulla "finestra di punti" che va a sostituire (un po' il concetto dello smoothing).

Ma secondo me questi metodi non sono una buona idea, se hai una rotta è facile che ti serva poco dettaglio in punti dove è sostanzialmente dritta, ma tanti dove gira molto. Personalmente cercherei calibrare l'accuratezza in maniera diversa in zone diverse, ad esempio andando a vedere - ad esempio - la norma del laplaciano discretizzato calcolato sulla successione dei tuoi punti, che dovrebbe darti la velocità di cambiamento della direzione della tua curva sul piano. Ottenuta la successione dei valori della norma del laplaciano nei vari punti ci applicherei uno smooth e userei i valori così ricavati per determinare l'importanza relativa dei vari punti, in base a cui andrei a scegliere in quali zone campionare maggiormente per il mio "percorso semplificato".

Diciamo che la questione che è una rotta è un dettaglio che ti sta portando "fuori rotta"

Mi serve scremare quei punti perchè ho la rotta reale, voglio prendere solo il tot% e vedere se il mio algoritmo con solo quel tot% è in grado di ricostruirsi la rotta reale. O meglio vedere di quanto (mediante l'algoritmo della dtw) la rotta ricostruita si discosta da quella reale.

Alla fine ho pensato ad una cosa del genere (e pare funzionare):

float modulo = (((float)rotta.size()) / 100) * percentuale;
	    	  modulo = ((float)rotta.size()) / modulo;
	    	  int salta = 0;

Poi nel for che scandisce la rotta (usando come indice l'intero i) metto questo:

	    		  if(salta < modulo && i > 0)
	    		  {
                                  //Lo salto, ovvero aggiungo alla linea % che è il mio carattere di commento
	    			  linee.add(0,"% "+linea);
	    			  salta++;
	    		  }
	    		  else
	    		  {
	    			  linee.add(0,linea);
	    			  salta = 0;
	    		  }

Ovvero modulo mi dice quanti ne devo prendere, in base alla percentuale e alla lunghezza totale della rotta. Forse il mio ragionamento è stato un po' più intricato

[Neptune]

Dubbio matematico (speriamo che non mi spostino dinuovo ):

Se la mia rotta è di 915 punti e ne voglio prendere il 10% quindi 91 punti, se ne prendo 1 si e 10 no ne sto prendendo 1/10 ovvero il 10%? Oppure mi sto confondendo?

[MItaly]

Lo step che ti interessa è l'inverso della percentuale, per cui 10%=0.1 => step=1/0.1=10.

[ramy89]

Se ho capito bene qual'è il tuo problema, vuoi prendere i punti in posizioni regolari, quindi ad esempio in posizione 0,3,6,9.
Puoi usare l' aritmetica in modulo.Qualcosa mi dice che lo devi fare in Java
Se lo fai con un linguaggio in cui è presente l' operatore modulo, allora puoi:

1)<Calcolare la lunghezza della lista, dividerla per 100 e moltiplicarla per la percentuale, mettere tale valore in N>
2)<Fare un ciclo con l' iteratore che va da N alla lunghezza della lista, e ad ogni passo:
....Selezioni il punto;
....Incrementi l' iteratore di N.

Tutto questo tenendo conto del fatto che N potrebbe non essere un numero intero.

Se la mia rotta è di 915 punti e ne voglio prendere il 10% quindi 91 punti, se ne prendo 1 si e 10 no ne sto prendendo 1/10 ovvero il 10%? Oppure mi sto confondendo?

Ne prendi 1 e ne "scarti" 9 in questo caso.