1

I have a table of POINTs that represent barriers. I would like to be able to find the closest edge id on the edge graph so that I can have the routing algorithm ignore that edge (thus route around it).

My attempt looks something like this:

SELECT id FROM edge_table
ORDER BY (st_distance(edge_table.geom), restrictions_table.points), false) ASC;

The problem is that st_distance requires two geometries and I am trying to pass in all of the barrier points. I can get this to work for one point but I need this whole table of points, returning multiple edge ids.

The only way I can think to do this would be to use a loop and go through all of the points in the restrictions table and then find the edge id they are closest to one by one.

I know loops are usually performance heavy and not recommended in SQL so I was wondering if anyone had a better approach to this problem.

The routing algorithm I am using is pgr_trsp().

  • any progress yet? – ThingumaBob May 29 '18 at 16:14
1

The basic approach to a task like yours would be a JOIN LATERAL; this will effectively iterate over the left hand table select of the join and perform the query on the right for each while enabling to pass in column references from the left. As you hinted yourself, this is necessary to find the closest edge for each point, as your query would simply sort by the distance over all entries in both tables.
This is commonly referred to as a spatial (K) Nearest Neighbor (KNN) search, and you should find plenty of sources on that using PostGIS on GIS SE (e.g. concerning additional filter options to speed up things on very large tables).

For reference, running

SELECT edgs.id
FROM restrictions_table AS pts
JOIN LATERAL (
    SELECT id
    FROM edges_table
    ORDER BY pts.points <-> geom
    LIMIT 1
) AS edgs
ON true;

will return the ids of those edges that are closest to each POINT (assuming restriction_table.points is the geometry column).
With the KNN operator <-> in the ORDER BY statement, this will make excellent use of the spatial indexes on both tables and will perform quite well, given the requirement.

When running this as a CTE (e.g. named barrier) before the pgr_trsp main query, you can exclude those edges with a ... WHERE id NOT IN barriers filter in the function's table selection (excluding them from the graph).
Or simply assign humongous cost values to those edges in an UPDATE edge_table ... command. (Note that the latter will make sure there will be a route despite the barrier, while the first option could return no route at all)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.