I am trying to get cells names (in a sequence) by way trajectory is passing through them. For example in the photo shown below:

Blue markers represent a grid and red line represent a trajectory passing through them. (Its a 5x5 grid).

enter image description here

The result should be{C22, C21, C31, C30, C40, C41} where C21 etc are the cell names by row & column number. All it means is trajectory is starting from cell_names C22 to C21 to C31 and so on. I am using following query to retrieve this result:

select ce.cell_names
from cells ce, traj tr
where st_intersects(tr.traj_path, ce.coordinates) and tr.traj_id = 207 and ce.grid_id = 7776

Where traj_path is LINESTRING and coordinates is POLYGON.

The problem of keeping cell order was solved by the answer of one previous contributor and it also works through following query:

SELECT tr.traj_id, ce.cell_id
from cells_new_york AS ce, real_traj AS tr,
ST_LineLocatePoint(tr.traj_path, ST_Centroid(ce.coordinates)) as saim
where st_intersects(tr.traj_path, ce.coordinates) and ce.grid_id = 9 and tr.traj_id = 572
order by saim

But this misses the revisited polygons. As in the figure below C22 and C21 are visited twice. But they are not captured by the query.

Can you guide me towards a relevant PostGIS function?

enter image description here


For get all the visited grid cells in order, even if the grid cell is revisited, I wrote the SQL query below :

SELECT tr.tr_id,
FROM cells ce, traj tr
ORDER BY ST_LineLocatePoint(
            ST_Intersection(ce.coordinates, tr.traj_path)

Explanations :

The big part is in the ORDER clause, the rest is for the selection.

  • ST_INTERSECTION (doc) : for return traj line layer geometry clipped by cells polygon layer geometries.

  • ST_DUMP (doc) with .geom : for return the geometry part of the ST_DUMP set, for have only single part geometries. A trajectory that revisit many times a grid cell, clipped by the grid cells, gives only one multi-part geometry.

  • ST_CENTROID (doc) : for return the centroid of the clipped line part, the latter being in the grid cell (pay attention to the trajectories that follow the cell boundaries)

  • ST_LineLocatePoint (doc) : for return the proportion of the distance of the location of the closest point on the trajectory of the clipped part centroid.


Following the good remark from @ThingumaBob, for avoiding repetitions of grid cells which contains self intersections of a trajectory (ST_INTERSECTION split the trajectory if it self intersects), I rewrote the SQL code :

WITH t1 AS (
  SELECT tr.tr_id,
              ST_Intersection(ce.coordinates, tr.traj_path)
  ) AS distance
  FROM cells ce, traj tr

t2 AS (
  SELECT t1.tr_id,
  COALESCE(LEAD(t1.grid_id) OVER(ORDER BY t1.tr_id, t1.distance), -1) AS next_grid_id
  FROM t1

SELECT t2.tr_id,
WHERE t2.grid_id <> t2.next_grid_id

Explanations 2 :

  • Subquery t1 : this is the query explained above, the ORDER part is now in the SELECT for use in other query parts.

  • Subquery t2 (from t1) (doc) : with the window function LEAD, this subquery returns the next grid cell id in the distance order. And the last trajectory part has no grid cell next id, hence the use of COALESCE for replace the NULL value with -1 (which is, normally, an impossible id, but not NULL).

  • Final select from t2 : returns all records that have a grid cell id different from the next grid cell id (an even grid cell id means a same trajectory part in the same grid cell, means a trajectory self-intersection).

  • Good one...I was literally a click away from posting this as an update to my answer ,) one addition maybe: for self-intersecting paths (very possible with vehicle movement...) this would return the same ce.id at least twice for a single visit; you can add a filter for ce.id <> LEAD(ce.id) (pseudo-code: you'd need to add the window function in an outer query to use it's results in another outer query...) – ThingumaBob Sep 2 at 12:09
  • Thank you so much for an amazing answer! It'll take me some time to fully understand it. Your first query is working as required by my current need. Your second query is not giving required results. Thanks for making the effort. :) – Saim Mehmood Sep 2 at 22:30
  • I've made the correction, I have only tested it with only one trajectory and now, it's work with many. – J. Monticolo Sep 3 at 7:42
  • Thank you, your second query is also working. What do you mean by "self intersections of a trajectory"? – Saim Mehmood Sep 3 at 20:14
  • A trajectory loop, when the trajectory crosses a place where it has already gone. – J. Monticolo Sep 3 at 20:19

You should be able to order by the fraction of line-length at which each cells centroid projects onto the line:

SELECT cell_names
FROM   (
  SELECT ce.cell_names,
         ST_LineLocatePoint(tr.traj_path, ST_Centroid(ce.coordinates)) AS frac
  FROM   cells AS ce
  JOIN   traj AS tr
    ON   ST_Intersects(ce.coordinates, tr.traj_path)
) q

Those cells need to be a regular grid. There may be rare edge cases, though, where this fails.

  • Thank you so much! It's working and I'm trying to understand why. Reading through postgis docs. Hoping it'll make sense after sometime. – Saim Mehmood Apr 1 at 22:21
  • 1
    glad it works! but one major drawback I forgot to mention: a line returning to a previously passed polygon likely produces wrong results, and that polygon is not counted twice! might be essential to your needs, so consider if this truly answers your question...,) – ThingumaBob Apr 1 at 23:41
  • Kindly let me know how I can make sure that revisited polygon gets counted twice. – Saim Mehmood Aug 8 at 16:32
  • I'm getting same result after running slightly different query. SELECT tr.traj_id, ce.cell_id from cells_new_york AS ce, real_traj AS tr, ST_LineLocatePoint(tr.traj_path, ST_Centroid(ce.coordinates)) as saim where st_intersects(tr.traj_path, ce.coordinates) and ce.grid_id = 9 and tr.traj_id = 572 order by saim – Saim Mehmood Aug 8 at 16:45
  • But this also misses revisited polygons. Which is important, as I am taking trajectories as walks of objects on grid cells i.e., polygons. Let me know if you're familiar with any other function that will do the task. – Saim Mehmood Aug 8 at 16:47

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.