3

I am seeking an algorithm, not GIS software.

To find the shortest path between two points at sea with land between them, you can consider land as a polygon shaped obstacle between these. The concept of finding the shortest path avoiding obstacles is outlined here: http://alienryderflex.com/shortest_path/

Is there a publicly available algorithm to find the shortest path between two points at sea, but going along the coast and not across land?

I am working with thousands of points, so it has to be an algorithm, not a workaround using GUI software.

Creating optimised path between nodes avoiding polygons entities using QGIS asks and gets help to do this in QGIS, but it currently has only one answer and that is not applicable for this problem. To do this manually, as proposed in the answer in that question is not an answer to my problem as that solution is unfeasible with high amount of data. I am asking for an algorithm, not a method to do it in QGIS.

PolyGeo
  • 65,136
  • 29
  • 109
  • 338
bjornasm
  • 196
  • 1
  • 10
  • 1
    Thanks for reposting your question as it saved me finding your other one, reopening it and closing it as a duplicate – Ian Turton Nov 15 '22 at 19:47
  • 2
    @IanTurton Your "duplicate" solves this is qgis, this specifically asks for an algorithmical implementation in Python or in Postgis. – bjornasm Nov 15 '22 at 19:50
  • 3
    @IanTurton I agree and think it's a valid question. – Shawn Nov 15 '22 at 21:34
  • 2
    @bjornasm the searoute python package will probably work for you. https://github.com/genthalili/searoute-py – Shawn Nov 16 '22 at 01:39
  • 1
    how about https://gis.stackexchange.com/questions/158972/find-shortest-path-between-points-avoiding-shapefile then – Ian Turton Nov 16 '22 at 13:09

1 Answers1

2

I would expect any maze solving algorithm to be applicable to finding a route across a raster representing oceans with ports around the edges.

Ian Turton
  • 81,417
  • 6
  • 84
  • 185