Autore Topic: Tracciare percorso minimo in una mappa personalizzata  (Letto 687 volte)

Offline marcuz89

  • Nuovo arrivato
  • *
  • Post: 8
  • Respect: 0
    • Mostra profilo
  • Dispositivo Android:
    Lg G2
  • Sistema operativo:
    Windows 8.1
Tracciare percorso minimo in una mappa personalizzata
« il: 28 Novembre 2014, 12:09:23 CET »
0
Salve a tutti,
sono uno sviluppatore alle prime armi. Dovrei aggiungere al mio applicativo android la seguente cosa in una activity:
Mi servirebbe che l'applicazione fosse in grado di mostrarmi una mappa personalizzata nella quale devo rappresentare un percorso minimo tra una posizione iniziale e una di arrivo. Le posizioni possono venir lette da un database sql che ho già creato, quindi non mi serve usare gps e robe simili e ne tantomeno le api di google maps.
Quello che mi servirebbe è poter semplicemente tracciare lo "shortest path" tra un punto iniziale e punto finale all'interno di una mappa personalizzata (una semplice immagine di planimetria, dove posso indicizzare dei nodi e link).

Mi va bene anche che mi diate delle idee per come approcciarmi al problema.

Offline bradipao

  • Moderatore globale
  • Utente storico
  • *****
  • Post: 4043
  • keep it simple
  • Respect: +567
    • Github
    • Google+
    • bradipao
    • Mostra profilo
  • Dispositivo Android:
    Nexus 5
  • Play Store ID:
    Bradipao
  • Sistema operativo:
    W7
Re:Tracciare percorso minimo in una mappa personalizzata
« Risposta #1 il: 28 Novembre 2014, 12:33:14 CET »
0
Se devi farti in proprio lo shortest path, devi costruirti un grafo pesato dei percorsi e poi applicare uno dei tanti algoritmi che ci sono in letteratura (esemopio Algoritmo di Dijkstra - Wikipedia )
NON rispondo a domande nei messaggi privati
Bradipao @ Play Store

Offline marcuz89

  • Nuovo arrivato
  • *
  • Post: 8
  • Respect: 0
    • Mostra profilo
  • Dispositivo Android:
    Lg G2
  • Sistema operativo:
    Windows 8.1
Re:Tracciare percorso minimo in una mappa personalizzata
« Risposta #2 il: 28 Novembre 2014, 13:09:00 CET »
0
Si, grazie. La teoria dei grafi è già di mia conoscenza. Infatti pensavo di utilizzare Dijkstra.


Il problema è che non so come approcciarmi in Android.
Ti spiego: non saprei come costruire grafi e nodi in in un'applicazione android, e avevo pensato di affidarmi ad un programma esterno (o anche un sito web) che venga letto dall'app e mi mostri il percorso in una planimetria a partire da dei dati in input.


Ad esempio sono in un centro commerciale, clicco sull'app che voglio andare in un negozio e mi mostra la mappa della planimetria con il percorso che devo compiere (a partire da una posizione iniziale nota), con un semplice tratto. Non mi serve per forza un navigatore, ma mi va bene anche un percorso disegnato.

Spero di essermi spiegato meglio.

Offline Alexofalco

  • Nuovo arrivato
  • *
  • Post: 14
  • Respect: 0
    • Mostra profilo
  • Dispositivo Android:
    Samsung Galaxy S Advance
  • Sistema operativo:
    2.3.6
Re:Tracciare percorso minimo in una mappa personalizzata
« Risposta #3 il: 02 Dicembre 2014, 13:53:48 CET »
0
Dipende innanzitutto dalla complessità della mappa. Devi trasformare la mappa in un grafo in modo ottimale. Se dici che le mappe sono inerenti alla planimetria di un centro commerciale forse un grafo di manhattan fa a caso tuo.

Inviato dal mio GT-I9070 con Tapatalk 2


Offline marcuz89

  • Nuovo arrivato
  • *
  • Post: 8
  • Respect: 0
    • Mostra profilo
  • Dispositivo Android:
    Lg G2
  • Sistema operativo:
    Windows 8.1
Re:Tracciare percorso minimo in una mappa personalizzata
« Risposta #4 il: 03 Dicembre 2014, 10:45:11 CET »
0
Apprezzo la risposte, ma ditemi qualcosa di concreto! Un link, una guida, un software, una possibile implementazione...
Per trasformare la mappa in un grafo io avevo pensato a Matlab, li so come farlo e come implementare Dijkstra.
Ma volevo sapere se ci fosse qualcosa di più professionale, più adatto all'editing delle mappe e i percorsi.

Per esempio cosa intendi per il grafo di manhattan?

Offline Alexofalco

  • Nuovo arrivato
  • *
  • Post: 14
  • Respect: 0
    • Mostra profilo
  • Dispositivo Android:
    Samsung Galaxy S Advance
  • Sistema operativo:
    2.3.6
Re:Tracciare percorso minimo in una mappa personalizzata
« Risposta #5 il: 03 Dicembre 2014, 11:44:23 CET »
0
Il grafo di manhattan è un grafo ciclico adatto con nodi ed archi su un piano. In più ha la particolarità di avere tutti i nodi con 4 archi, visti dall'alto come se formassero un griglia, che ricorda la disposizione delle strade del noto quartiere di new york. Solitamente hanno anche archi con peso unitario quindi il costo del percorso unitario è praticamente ricavabile da formule geometriche piane.

Wikipedia e google ti forniscono fin troppe implementazioni, teoria ed esempi su questa tipologia di grafo, basta avere la pazienza di cercare, magari espandendo la ricerca in altre lingue.

Dalle tue risposte do per scontato un minimo di teoria dei grafi. Detto ciò se il tuo problema è la conversione della mappa in grafo... beh.... in che modo è rappresentata la mappa? bitmap? modello 3d?in che senso hai un db con dentro le informazioni della mappa? il punto cruciale ora è convertire l'informazione della mappa in grafo ma non mi è ben chiaro questo punto.