algorithm - latitude - google maps geocoding api

Encuentre el camino por mar desde el punto costero A hasta el punto costero B

Question

Tengo el reto aparentemente difícil de tratar de encontrar un camino, por mar, de un puerto marítimo a otro. El objetivo final es trazar esto en un mapa de Google (o Bing) como una polilínea.

El camino necesita:

• Sea plausible, ya que un barco no puede ir por tierra (obviamente)
• No correr demasiado cerca de la línea de costa. Los barcos no pueden ir tan cerca de la orilla
• No sea demasiado complejo. Se va a trazar en Google Maps, por lo que una polilínea de 2000 puntos no sirve.
• Sea el más corto, pero no a expensas de los tres puntos anteriores

Entonces, mi primera idea fue obtener datos sobre las líneas costeras de todo el mundo. Tal cosa está disponible here . Desafortunadamente es incompleto sin embargo. OpenStreetMap muestra estos datos y faltan líneas costeras para cosas como las islas del Caribe.

También pensé en la codificación geográfica (no es lo suficientemente confiable, además de que quemaría miles de solicitudes al intentar trazar una ruta)

Mi siguiente idea fue utilizar Google Maps y probar si un punto es azul o no. GMaps.NET , un excelente componente de Mapeo .NET, me permitió lograrlo creando un mapa de bits de lo que representa y probando el color de un píxel.

El primer problema es que la precisión de esta prueba de aciertos es tan buena como la imagen de resolución de la imagen con la que hago la prueba. Para puertos cercanos entre sí, esto está bien para puertos más alejados, la precisión se ve afectada.

El segundo problema , suponiendo que use algún tipo de método de "prueba de píxeles azules", es el algoritmo correcto para encontrar una ruta. El algoritmo A * parece prometedor, pero no estoy seguro de cómo empujar el camino ''fuera'' del ser a la costa. Tampoco cómo reducir la complejidad de la polilínea.

Entonces, cualquier entrada : ideas, pensamientos, enlaces, código de muestra, etc. sería bienvenida. Gracias.

(Debo agregar que esto es para un sitio de viajes. La precisión no es muy importante, no estoy dirigiendo el envío ni nada)

Answer 1

El segundo problema, suponiendo que use algún tipo de método de "prueba de píxeles azules", es el algoritmo correcto para encontrar una ruta. El algoritmo A * parece prometedor, pero no estoy seguro de cómo empujar el camino ''fuera'' del ser a la costa. Tampoco cómo reducir la complejidad de la polilínea.

Primero cree la imagen binaria de mar del mundo (blanco: es mar, negro: no mar), luego erosione la imagen. Todos los puntos blancos después de la erosión son navegables. Despreciando el banco de arena impar o dos, por supuesto.

Como puede imaginar, este enfoque revela un problema central en su búsqueda de caminos: la mayoría de los barcos tienen que dirigirse bastante cerca de la tierra para llegar a un puerto, lo que infringe las reglas de navegación. Sin embargo, esto podría resolverse comenzando la navegación en el punto de navegación más cercano al mar adyacente a un puerto determinado.

Answer 2

Aquí hay una solución que utiliza R. Podría ser mucho más refinado, simplemente haciendo que ciertas regiones sean caras o baratas para el algoritmo de ruta más corto. Por ejemplo, excluir el Océano Ártico, permitir los ríos / canales principales, hacer conocidas las rutas de envío preferidas para viajar.

library(raster)
library(gdistance)
library(maptools)
library(rgdal)

# make a raster of the world, low resolution for simplicity
# with all land having "NA" value
# use your own shapefile or raster if you have it
# the wrld_simpl data set is from maptools package
data(wrld_simpl)

# a typical world projection
world_crs <- crs(wrld_simpl)
world <- wrld_simpl
worldshp <- spTransform(world, world_crs)
ras <- raster(nrow=300, ncol=300)

# rasterize will set ocean to NA so we just inverse it
# and set water to "1"
# land is equal to zero because it is "NOT" NA
worldmask <- rasterize(worldshp, ras)
worldras <- is.na(worldmask)

# originally I set land to "NA"
# but that would make some ports impossible to visit
# so at 999 land (ie everything that was zero)
# becomes very expensive to cross but not "impossible" 
worldras[worldras==0] <- 999
# each cell antras now has value of zero or 999, nothing else

# create a Transition object from the raster
# this calculation took a bit of time
tr <- transition(worldras, function(x) 1/mean(x), 16)
tr = geoCorrection(tr, scl=FALSE)

# distance matrix excluding the land, must be calculated
# from a point of origin, specified in the CRS of your raster
# let''s start with latlong in Black Sea as a challenging route
port_origin <- structure(c(30, 40), .Dim = 1:2)
port_origin <- project(port_origin, crs(world_crs, asText = TRUE))
points(port_origin)

# function accCost uses the transition object and point of origin
A <- accCost(tr, port_origin)

# now A still shows the expensive travel over land
# so we mask it out to display sea travel only
A <- mask(A, worldmask, inverse=TRUE)

# and calculation of a travel path, let''s say to South Africa
port_destination <- structure(c(20, -35), .Dim = 1:2)
port_destination <- project(port_destination, crs(world_crs, asText = TRUE))

path <- shortestPath(tr, port_origin, port_destination, output = "SpatialLines")

# make a demonstration plot
plot(A)
points(rbind(port_origin, port_destination))
lines(path)

# we can wrap all this in a customized function
# if you two points in the projected coordinate system,
# and a raster whose cells are weighted 
# according to ease of shipping
RouteShip <- function(from_port, to_port, cost_raster, land_mask) {
  tr <- transition(cost_raster, function(x) 1/mean(x), 16)
  tr = geoCorrection(tr, scl=FALSE)
  A <- accCost(tr, from_port)
  A <- mask(A, land_mask, inverse=TRUE)
  path <- shortestPath(tr, from_port, to_port, output = "SpatialLines")

  plot(A)
  points(rbind(from_port, to_port))
  lines(path)
}

RouteShip(port_origin, port_destination, worldras, worldmask)

Answer 3

Para simplificar la polilínea que obtiene de, por ejemplo, una búsqueda A *, puede utilizar un algoritmo como Douglas-Peucker . Consulte también esta lista de referencias: http://maven.smith.edu/~orourke/TOPP/P24.html .

Idea alternativa: la forma habitual de aplicar A * sería considerar cada píxel como un posible estado (posición), pero no hay razón por la que no pueda usar solo un subconjunto de los píxeles como posibles estados. Si hace que la densidad de los estados cercanos al principio y los puntos finales sea alta, y la densidad de los estados alejados de los puntos finales bajos, automáticamente obtendrá rutas que comienzan y terminan con movimientos cortos y precisos, pero tienen segmentos rectos largos en el medio (Por ejemplo, al cruzar el Pacífico). Si lo hace, es posible que también desee aumentar la densidad de las posiciones cerca de la tierra.

Otro posible A * tweak: puede incorporar la "dirección actual" en el estado y penalizar los movimientos que causan un cambio en la dirección. Esto tenderá a producir largas líneas rectas en su camino. Esto multiplicará tu espacio de estado por 8, pero eso es probablemente soportable. Debido a que solo aumenta el costo de una solución, la heurística de línea recta a destino que normalmente usaría sigue siendo admisible para esta nueva función de costo, por lo que no surgen complicaciones allí.

Answer 4

Si yo fuera tú elegiría un enfoque de teoría de grafos. Su único problema sería reunir los bordes de la base de datos. Si los tiene, puede utilizar A * o algo de Dijkstra para planificar la ruta más corta. De todos modos, si lo asumo correctamente, necesitas algo similar a (Searoutefinder), ¿no? ¡Buena suerte!