guylmaster
22-02-2012, 23:59
Avrei un problemino più che altro algoritmico nel realizzare una funzione in java.
Dunque ho una mappa rappresentata su un file nel seguente modo:
Lat/Lon 3.99, 4.00, 4.01,
44.01, 8.00, 8.00, 8.00,
44.00, 8.00, 4.00, 8.00,
43.99, 8.00, 8.00, 8.00,
43.98, 4.00, 8.00, 8.00,
43.97, 8.00, 8.00, 8.00,
Praticamente la prima colonna sono le latitudini, la prima riga le longitudini e i valori in mezzo ci dicono che cosa ce in quel punto (a me interessa schematizzare tutto in mare o terra ma vabbè).
Ora devo cercare di mettere tutto nei nodi di un grafo tenendo presente che:
- Fissero un valore K che rappresenterà quanti punti della mappa devo rappresentare in ogni nodo del grafo, questo valore sarà a discrezione dell'utente ma sarà uguale per ogni nodo della mappa;
- Nella rappresentazione dei nodi ho comunque sia un centroide che gli rappresenta che il range di valori di coordinate (dispongo poi di funzioni per calcolare la distanza tra due punti ed anche per sapere due punti come sono orientati uno con l'altro);
- Gli archi che ogni nodo avrà saranno 8 e saranno del tipo: Nord, Nord-Est, Est, Sud-Est, Sud, Sud-Ovest..
Ora il mio problema principale e che le mappe contengono migliaia e migliaia di punti, quindi le prove che ho fatto sono miseramente fallite perché su mappe "piccole" tutto filava liscio, su mappe grandi arrivavo a computazioni lunghe (vorrei qualcosa che non debba superare il minuto di computazione).
Voi cosa suggerite? Vi dico cosa ho provato a fare io:
- Prendo in fila i K punti (benchè sarebbe più opportuno prenderne a forma di quadrato, del tipo se ne ho 4 prendere due punti dalla prima riga e due punti dalla seconda), ed inizio a caricare i nodi nel grafo. Dopo mi faccio ritornare l'insieme dei nodi del grafo, per ogni nodo ordino tutti gli altri per direzione e per ogni direzione prendo il più vicino.
Ecco questa sembrava veloce da implementare ma ha avuto complessità computazione troppo elevata;
- Quest'altra prova sebbene invece aveva una complessità computazionale migliore non restituitiva bene tutti gli archi. Ovvero prendevo un nodo, cercavo di approssimare le coordinate dei nodi che dovevano stargli attorno e poi se quei nodi esistevano tiravo gli archi. Ho avuto ovviamente problemi ad approssimare le distanze perché innanzi tutto se approssimo un nodo con 4 punti di fila il nodo posizionato accanto sarà molto più distante di quello posizionato sotto e questo mi sballava un po' tutti i calcoli.
Siete liberissimi di deridermi ma se avete qualche idea, anche uno pseudocodice che secondo voi potrebbe funzionare a grandi linee è sicuramente ben accetto :fagiano:
Vi ringrazio in anticipo,
guylmaster.
Dunque ho una mappa rappresentata su un file nel seguente modo:
Lat/Lon 3.99, 4.00, 4.01,
44.01, 8.00, 8.00, 8.00,
44.00, 8.00, 4.00, 8.00,
43.99, 8.00, 8.00, 8.00,
43.98, 4.00, 8.00, 8.00,
43.97, 8.00, 8.00, 8.00,
Praticamente la prima colonna sono le latitudini, la prima riga le longitudini e i valori in mezzo ci dicono che cosa ce in quel punto (a me interessa schematizzare tutto in mare o terra ma vabbè).
Ora devo cercare di mettere tutto nei nodi di un grafo tenendo presente che:
- Fissero un valore K che rappresenterà quanti punti della mappa devo rappresentare in ogni nodo del grafo, questo valore sarà a discrezione dell'utente ma sarà uguale per ogni nodo della mappa;
- Nella rappresentazione dei nodi ho comunque sia un centroide che gli rappresenta che il range di valori di coordinate (dispongo poi di funzioni per calcolare la distanza tra due punti ed anche per sapere due punti come sono orientati uno con l'altro);
- Gli archi che ogni nodo avrà saranno 8 e saranno del tipo: Nord, Nord-Est, Est, Sud-Est, Sud, Sud-Ovest..
Ora il mio problema principale e che le mappe contengono migliaia e migliaia di punti, quindi le prove che ho fatto sono miseramente fallite perché su mappe "piccole" tutto filava liscio, su mappe grandi arrivavo a computazioni lunghe (vorrei qualcosa che non debba superare il minuto di computazione).
Voi cosa suggerite? Vi dico cosa ho provato a fare io:
- Prendo in fila i K punti (benchè sarebbe più opportuno prenderne a forma di quadrato, del tipo se ne ho 4 prendere due punti dalla prima riga e due punti dalla seconda), ed inizio a caricare i nodi nel grafo. Dopo mi faccio ritornare l'insieme dei nodi del grafo, per ogni nodo ordino tutti gli altri per direzione e per ogni direzione prendo il più vicino.
Ecco questa sembrava veloce da implementare ma ha avuto complessità computazione troppo elevata;
- Quest'altra prova sebbene invece aveva una complessità computazionale migliore non restituitiva bene tutti gli archi. Ovvero prendevo un nodo, cercavo di approssimare le coordinate dei nodi che dovevano stargli attorno e poi se quei nodi esistevano tiravo gli archi. Ho avuto ovviamente problemi ad approssimare le distanze perché innanzi tutto se approssimo un nodo con 4 punti di fila il nodo posizionato accanto sarà molto più distante di quello posizionato sotto e questo mi sballava un po' tutti i calcoli.
Siete liberissimi di deridermi ma se avete qualche idea, anche uno pseudocodice che secondo voi potrebbe funzionare a grandi linee è sicuramente ben accetto :fagiano:
Vi ringrazio in anticipo,
guylmaster.