postgis - Maritime route prediction avoiding land masses

I am working on a project where the following functions have to be implemented:

1. 
   

   Predicting the locations of the ships (in maritime environment) at a future time. (Can be done with Kalman filter, IMM filter and some other algorithms.) Ships can be in any part of the world.

   
   



2. 
   

   Avoiding landmasses during prediction.

   
   


3. 
   

   Finding the shortest paths along the shorelines.

   
   

I am totally done with the first part which is predicting without considering the shoreline information. I have problems with the functions 2 and 3.

Function 2 At times, the predicted location can fall into the landmass area which is totally unacceptable. I am using the coastal area shapefile http://openstreetmapdata.com/data/coastlines. This file has converted XY values of the world shoreline data. I have loaded this shapefile into postgreSQL and used postgis to read it from the database.

My idea is to go through all the polygons (shoreline defined based on polygons) and check whether the line connecting the present location and the predicted location crosses the polygon. If it crosses, that means we have to find where the ship intercepts the shoreline first. But if I follow this approach going through all the polygons, it is going to take forever. (It has around 62000 polygons and each of them has thousands of points). Any advice on this?

I thought about initially dividing the world map into hierarchical areas (Level 1: 10 polygons; Level 2: each polygon has 10 polygons inside). But I am not sure how to divide the world map into the levels of polygons I require. Is any functionality of postgis helpful for this? Or any other libraries for this purpose? I believe this kind of functionality should be available already. But I am not able to figure it out so far.

Function 3 Since now we know where the ship intercepts the shoreline first, we can predict its route along the shoreline using the shortest path algorithm given we know the destination information. But to do this, you need to divide the shoreline map into grids so the shortest path can be used. So how can you make grids based on this along the shorelines? I am not doing image processing here. What I have is this shapefile now. Or should I go with some image processing approach and make the grid shorelines? If so please provide some links.

Answer

You don't want coastlines, you want land polygons. Also, you need the grid for whole area, not only around the coast cause you don't know when the ship will intercept the land (ship that is on the middle of Atlantic and is going to India won't just sail in straight line until it hits the land, it will head straight for the South of Africa (or choose the way thru Suez canal).

The most basic code that will give you what you want is:

WITH line AS(
            SELECT ST_TRANSFORM(ST_SetSRID(ST_GeomFromText(('LINESTRING(10 -85, 10 85)')),4736),3785) as line
        ),
        lands AS(
            SELECT ST_UNION(geom) AS geom FROM simplified_land_polygons CROSS JOIN line WHERE ST_INTERSECTS(geom,line.line)

        )
        SELECT ST_Difference(line.line,lands.geom) FROM lands LEFT JOIN line ON 1=1;