# PostGIS: minimum distance path between polygons, constrained by a mask polygon

I need to find the shortest path between two polygons (source and target), but where the possible paths are constrained by a third (mask) polygon. I am currently using ST_ShortestLine on my source and target polygons, then checking if the result lies within the mask polygon and flagging the resulting line as 'invalid' for manual followup if not. But I'd like to fully automate the process.

I can see how I could theoretically do this in a GIS that supports cost-distance calculations - convert the mask polygon to a raster and run a lowest-cost function between the source and target.

But I can see no way of doing this in PostGIS - either using vector or raster functions.

I am running the SQL via ruby scripts, so have the option of scripting as part of the solution.

Suggestions?

Edit: Hand-drawn example below showing what my polygons look like

• Triangulate many points inside other polygon and compute path. More points, better result Commented Mar 20 at 19:08
• OK - get the concept I think. Can't see a way of generating a triangle grid, but something like: Create a grid: ST_Dump(ST_Boundary(ST_SquareGrid)), then use pgRouting to find the shortest route? Commented Mar 20 at 19:24
• Perhaps, but simplify line after, because you'll get Manhattan shortest distance, which is always longer. Suggest using Chaikin smoothing algorithm Commented Mar 20 at 21:19
• – BJW
Commented Mar 23 at 5:52
• Reduce each polygon to its `ST_Intersection()` with the mask shape, then find the `ST_ShortestLine()` between those. It won't use the index so I'd keep your current two-step process, where you just grab the `ST_ShortestLine()` between unprocessed inputs, then only use the thing with `ST_Intersection()` to correct those that weren't `ST_Within()` the mask in the first step. Commented Mar 24 at 14:09

## A mask allowing a direct, straight line

Generate an `st_makeline()` between all vertices of both polygons, discard the ones that aren't `st_coveredby()` the mask shape, pick the shortest one left. This risks that you will get no path that way, if the mask requires curving/turning/bending around it. Added to the demo:

``````select st_shortestline(dp1.geom,dp2.geom)
from __test.generated_shapes a
join __test.generated_shapes b
on a.n=25 and b.n=29
cross join st_dumppoints(a.geom) with ordinality as dp1(path,geom,n)
cross join st_dumppoints(b.geom) with ordinality as dp2(path,geom,n)
where st_coveredby(st_shortestline(dp1.geom,dp2.geom),m.geom)
order by st_length(st_shortestline(dp1.geom,dp2.geom))
limit 1;
``````

Except for filtering against the mask, that's the gist of what `st_shortestline()` does internally.

## Non-straight, indirect route, with `pgrouting`

You can generate a carthesian product of `st_makeline()` between all vertices of both shapes and the mask, discard the ones that aren't `st_coveredby()` the mask or the shapes `st_cover()` them (leaves you with edges on the boundary and a dense skeleton network between the exteriors of the shapes and interior of the mask) and hand those over to `pgr_aStar()` in `pgrouting` extension.

`Pgrouting` expects vertex and edge identifiers, cost info as well as separate columns with x and y coordinates for `A*` heuristics.

``````create table __test.graph_edges as
with all_vertices as (
select 1 as source_set_id,1e6::int+vid as vid,dp.geom
from __test.generated_shapes a
cross join st_dumppoints(a.geom) with ordinality as dp(path,geom,vid)
where a.n=25 union all
select 2 as source_set_id,2e6::int+vid as vid,dp.geom
from __test.generated_shapes a
cross join st_dumppoints(a.geom) with ordinality as dp(path,geom,vid)
where a.n=29  union all
select 3 as source_set_id,3e6::int+vid as vid,dp.geom
from __test.generated_shapes a
cross join st_dumppoints(a.geom) with ordinality as dp(path,geom,vid)
where a.n=777 )
--`distinct on` is there to get rid of A-B, B-A duplicates
select distinct on (least(   a.vid,b.vid),greatest(a.vid,b.vid))
a.source_set_id --useful to identify vertex origin shape
,a.vid as source
,b.vid as target
,st_makeline(a.geom,b.geom) as geom
,st_x(a.geom) as x1
,st_y(a.geom) as y1
,st_x(b.geom) as x2
,st_y(b.geom) as y2
from all_vertices a
join all_vertices b --self-join
on (1=a.source_set_id and 3=b.source_set_id )
or (2=a.source_set_id and 3=b.source_set_id )
--you do want to consider the entire scaffolding of the mask
or (3=a.source_set_id and 3=b.source_set_id
and a.vid<>b.vid      )
order by least(a.vid,b.vid),greatest(a.vid,b.vid);
``````

Not all edges are required: you don't want those sticking out the mask, or crossing either shape.

``````create table __test.graph_edges_filtered as
select row_number()over()as id,*
,st_length(geom) as cost
,st_length(geom) as reverse_cost
from __test.graph_edges as e
cross join lateral (
select a.geom as lft
,b.geom as rght
, m.geom as msk
from __test.generated_shapes a
,__test.generated_shapes b
,__test.generated_shapes m
where a.n=25 and b.n=29 and m.n=777)_
where not st_crosses(e.geom,lft)
and not st_crosses(e.geom,rght)
and st_coveredby(e.geom,msk);
``````

Once that's ready, the extension can generate all paths connecting the shapes, routed inside the mask. From that, you can pick the shortest one:

``````create table __test.shortest_route_from_a_to_b as
select st_union(e.geom) as geom
from pgr_aStar(
'SELECT id, source, target, cost, reverse_cost, x1,y1,x2,y2
FROM __test.graph_edges_filtered ',
(select array_agg(source) from __test.graph_edges_filtered
where source_set_id=1),
(select array_agg(source) from __test.graph_edges_filtered
where source_set_id=2)) pgr
join __test.graph_edges_filtered e
on e.id=pgr.edge
group by start_vid,end_vid
order by sum(pgr.cost)
limit 1;
``````

Final graph in grey, the shortest route in purple:

This method could still make sense even if you did already find a direct, straight connection - there could be cases where navigating through the mask can get you a shorter path than the shortest straight line. A straight line placed in the tunnel in the north would be way longer than the route that twists through the one in the center:

You can add some logic to narrow down which vertices of each shape you want to use. For example, you could only grab some portion of vertices that are closest to the other shape, if the "bridge" tends to be located like that.
Here I took the entire mask but only 200 closest, target-facing vertices of each shape, which ended up in a graph just 30% the size of the original, and only 5% of the original paths were simulated to get the same result. Same purple line, just way less grey edges of the graph, going down from `1.7s` to `90ms` on a single thread:

## Indirect route, without `pgrouting`

It's possible to handle some cases where only a single turn is required by generating a line connecting the source with the target, elongating that with `st_scale()` so that it can `st_split()` the mask/obstacle boundary. In simple cases, it'll split the obstacle boundary in two (or more), and you just need to select the shorter part, then use `st_union()` to add the connection jumping from the origin to the newly established path on the obstacle boundary, and from that to the target.

It's way more, way less robust code than employing proper routing, but it does eliminate save you the dependency. It might very well be easier to type out your own PL/pgSQL `A*` for this.

## The simple case

Reduce each polygon to its `ST_Intersection()` with the mask shape, then find the `ST_ShortestLine()` between those. Demo:

``````select st_shortestline(st_intersection(m.geom,a.geom),
st_intersection(m.geom,b.geom))
from __test.generated_shapes a
join __test.generated_shapes b
on a.n=25 and b.n=29
It won't use the index so I'd keep your current two-step process, where you just grab the `ST_ShortestLine()` between unprocessed inputs, then only use the thing with `ST_Intersection()` to correct those that weren't `ST_Within()` the mask in the first step.
• @madpom I added the `pgrouting` example. Unless there's additional logic used when you set up the path manually, you can handle all your cases using just that - I've added an example where routing could potentially offer a shorter path than what you can get from only considering shortest straight lines within the mask. Commented Apr 17 at 19:38