Trova percorso via mare dal punto costiero A al punto costiero B

Question

Ho la sfida apparentemente difficile di cercare di elaborare un percorso, via mare, da un porto marittimo a un altro porto marittimo. L'obiettivo finale è di tracciare questo su una mappa di Google (o Bing) come una polilinea.

Il percorso ha la necessità di:

• essere plausibile, come una nave non può andare sulla terra (ovviamente)
• Non correre troppo vicino alla linea di costa. Le navi non possono arrivare così vicino alla riva
• Non essere troppo complesso. Sarà tracciato su Google Maps, quindi una polilinea a 2000 punti non funzionerà.
• essere la più breve, ma non a scapito dei suddetti tre punti

Quindi, la mia prima idea era ottenere dati sulle linee di costa di tutto il mondo. Una cosa del genere è disponibile here. Purtroppo è incompleto comunque. OpenStreetMap mostra questi dati e le coste per cose come isole caraibiche sono mancanti.

Ho anche pensato di Geocoding (non abbastanza affidabile, più vorrei bruciare migliaia di richieste che cercano di tracciare un percorso)

mio prossima idea era quella di utilizzare in qualche modo Google Maps e verificare se un punto è blu o non. GMaps.NET, un ottimo componente .NET Mapping, mi ha permesso di ottenere ciò creando una bitmap di ciò che rende e verifica il colore di un pixel.

Primo problema è che l'accuratezza di questo test di successo è valida solo come l'immagine di risoluzione dell'immagine a cui si prova. Per le porte vicine l'una all'altra, questo va bene per le porte più lontane, la precisione soffre.

Secondo problema, supponendo che io utilizzi una sorta di metodo di "test dei pixel blu", è l'algoritmo giusto per trovare una rotta. Il A* algorithm sembra promettente, ma non sono sicuro di come spingere il percorso "fuori" dall'essere verso la costa. Né come ridurre la complessità della polilinea.

Quindi ... qualsiasi input: idee, pensieri, collegamenti, codice di esempio, ecc. Sarebbe il benvenuto. Grazie.

(devo aggiungere che questo è per un sito di viaggi. La precisione non è troppo importante, non sto dirigendo spedizione o nulla)

Answer 1

Secondo problema, supponendo che io uso una sorta di 'pixel blu test ', è quello che l'algoritmo è giusto per trovare una rotta. L'algoritmo A * sembra promettente, ma non sono sicuro di come spingere il percorso 'fuori' dall'essere alla costa vicina. Né come ridurre la complessità della polilinea.

Prima creare l'immagine binaria del mondo (bianco: è mare, nero: non mare), quindi erodere l'immagine. Tutti i punti bianchi dopo l'erosione sono navigabili. Trascurando lo strano banco di sabbia o due, ovviamente.

Come si può intuire, questo approccio rivela un problema centrale nella ricerca del percorso: la maggior parte delle navi deve sterzare abbastanza vicino alla terra per raggiungere un porto, violando le regole di navigazione.Tuttavia, ciò potrebbe essere risolto avviando la navigazione nel punto di mare navigabile più vicino adiacente ad un determinato porto.

Answer 2

Per semplificare la polilinea ottenuta ad es. A * ricerca, è possibile utilizzare un algoritmo come Douglas-Peucker. Vedi anche questo elenco di riferimenti: http://maven.smith.edu/~orourke/TOPP/P24.html.

idea alternativa: Il solito modo per applicare una * sarebbe quella di considerare ogni pixel come un possibile stato (posizione), ma non c'è alcun motivo per cui non si poteva usare solo un sottoinsieme dei pixel come possibili stati invece . Se rendi alta la densità degli stati vicino all'inizio e al punto finale, e la densità degli stati lontana da entrambi gli endpoint bassi, otterrai automaticamente percorsi che iniziano e finiscono con movimenti brevi e precisi, ma hanno segmenti rettilinei lunghi nel mezzo (ad esempio quando si attraversa il Pacifico). Se lo fai, potresti anche aumentare la densità delle posizioni vicino alla terra.

Un'altra possibile modifica A *: È possibile incorporare "la direzione corrente" nello stato e penalizzare i movimenti che causano un cambiamento di direzione. Questo tenderà a produrre lunghe linee diritte nel tuo percorso. Questo moltiplicherà lo spazio degli stati per 8, ma probabilmente è sopportabile. Poiché stai solo aggiungendo al costo di una soluzione, l'euristica da linea diret-to-destination che utilizzeresti normalmente rimane ammissibile per questa nuova funzione di costo, quindi non si presentano complicazioni.

Answer 3

Google per "Percorso più breve di Euclide". Wikipedia ha anche alcune informazioni

"Il problema del percorso più breve degli Euclidi è un problema nella geometria computazionale: dato un insieme di ostacoli poliedrici in uno spazio euclideo, e due punti, trova il percorso più breve tra i punti che non interseca nessuno di gli ostacoli. "

http://en.wikipedia.org/wiki/Euclidean_shortest_path

Answer 4

Se fossi in te sceglierei un approccio teoria dei grafi. Il tuo unico problema sarebbe quello di raccogliere i bordi del database. Se li hai, puoi usare A * o Dijkstra's algo per pianificare il percorso più breve. Comunque, se presumo giusto hai bisogno di qualcosa di simile a (Searoutefinder) giusto? In bocca al lupo!

Answer 5

Un litorale ad alta risoluzione può essere trovato sul sito da NOAA.

Per risolvere il tuo si può anche prendere la via più facile e chiedere un preventivo per il webservice percorso trasporto AtoBviaC e precalculate tutti gli itinerari previsti, ma che potrebbe essere troppo costoso per le vostre esigenze.