5

so I have a query that takes an encoded polyline, segmentizes that polyline into smaller pieces, and matches each point on that segmentized line to a "road segment" from a separate table in my database. This query works well and efficiently, matching each point to its closest road segment. What I want to be able to do is then find the total distance traveled within each returned matched segment, but I'm struggling with that part.

Here is the query:

WITH
  points AS (
  SELECT (ST_DumpPoints(
         ST_Segmentize(ml, .000032))
       ).*
  FROM ST_LineFromEncodedPolyline('xxx') AS ml
)
SELECT *
FROM (
  SELECT
     seg.xdsegid,
     pts.path,
     ST_Distance(pts.geom::geography, seg.geom::geography) AS distance
FROM points AS pts
JOIN LATERAL (
  SELECT st.xdsegid,
         st.geom
  FROM alabama AS st
  ORDER BY pts.geom <-> st.geom
  LIMIT 1
) AS seg
  ON true
  ORDER BY seg.xdsegid, path
) q
ORDER BY path;

And it currently returns rows that look like this:

Rows returned

I know I probably need to turn each segment into a line and get the distance that way, but I can't for the life of me figure out how to best go about grouping and measuring each one of the returned segments. Also, sometimes the segments will return in such a way that a small portion of the points will momentarily be matched to another segment before returning to the original. Not sure if this is problematic.

Interpolated segments

  • ...do you actually want the length of the given line when fully projected onto the network? – ThingumaBob Oct 24 '18 at 19:19
  • @ThingumaBob Hey! What I really want is the total distance that my encoded polyline traverses in each segment. Doing it in Javascript, I accumulate the distance between each point that exists on a given road segment and store that with the road segment id as the key. Does that answer your question? – Fell Oct 24 '18 at 19:24
  • but, it will traverse the full length of each segment except for those segments matched by the start and end point. if you'd accumulate only between points on each segment, the first and last of those points will be only somewhere close to the actual start and end points of that segment. you'd be missing out a couple of meters. ...am I getting this right ,)? – ThingumaBob Oct 24 '18 at 19:33
  • That's correct. Segmentizing the line as small as we have should only lose, at most, ~3 meters at the start and end of the segment if the path were to traverse the full length of the segment. It would be nice to know exactly how far, but that's an acceptable margin of error in my book. – Fell Oct 24 '18 at 20:02
  • Forgot to tag, my bad @ThingumaBob – Fell Oct 24 '18 at 23:40
3

Instead of approximating (see comments), let's try to be as precise as possible; the solution to this is even simpler than what you had in mind.

I'm adding just a bit of logic to your query to be able to determine if a segment is matched by the first or last point in the path (i.e. start & end point of your polyline), and

  • if so, get the fraction of line length of that segment where the closest possible projection of the point lies at, times the total segment length
  • if not, simply get the segments total length

Also, since there will be a bunch of duplicate segments returned by the KNN query, the query needs to return only the minimum value of all calculated lengths and DISTINCT the returned rows (this is mainly necessary to get the fractional length of the start/end point segments instead of the full length returned by other points matching these same segments). For best precision the length is calculated using the geography type.

WITH
  points AS (
    -- there are a couple of ways to handle set-returning functions; this one is just another with equal results
    SELECT (dp).path[1],
           (dp).geom AS geom,
           -- get row count to easily identify the last point
           count(*) OVER() AS mx
    FROM ST_DumpPoints(
           ST_Segmentize(
             ST_LineFromEncodedPolyline('xxx'),     
             -- (why not geography type for meter as unit?)                
             .000032
           ) 
         ) AS dp
  ),

SELECT DISTINCT
       seg.xdsegid,
       -- always return minimum length of all duplicates
       MIN(
         CASE
           -- if start point, get inverse fraction of line length
           WHEN pts.path = 1
             THEN ST_Length(seg.geom::geography) * (1 - ST_LineLocatePoint(seg.geom, pts.geom))
           -- if end point, get fraction of line length
           WHEN pts.path = pts.mx
             THEN ST_Length(seg.geom::geography) * ST_LineLocatePoint(seg.geom, pts.geom)
           -- else, get full line length
           ELSE ST_Length(seg.geom::geography)
         END
       ) OVER(PARTITION BY seg.xdsegid) AS len,
       seg.geom
FROM points AS pts
JOIN LATERAL (
    SELECT xdsegid,
           geom
    FROM alabama AS st
    ORDER BY st.geom <-> pts.geom
    LIMIT 1
) AS seg
ON true
ORDER BY ln.id;

This sould return all found segments with their traversed length in meter (use ROUND() or a cast to INTEGER if you are not interested in sub-atomic fractional lengths...); for all inner segments this will be the total segment length, for the two outer segments this will be the fractional length based on the closest projected point to the start/end point of your polyline.

Note: ST_LineLocatePoint, similar to the other functions using or returning fractions of line length, calculates the fraction from the start point of the given line. For the above query, and your usecase in general, to make sense, your road network should be directed correctly, i.e consistent with the direction of the passed in polyline (or vice versa), in order to find the correct (and not inversed) partial distance along the outer segments.


Another useful function btw. is ST_ClosestPoint; in conjunction with your KNN search, you could e.g. simply project the vertices of your polyline onto the road segments if you need.

See e.g. my answer here (albeit in an UPDATE you can see the similar concept).

  • This is great! Only question I have is: My geom column are not LineStrings, they are MultiLineStrings. St_LineLocatePoint doesn't seem to work with them. Do you think it's safe to convert them to LineStrings within the query to have this work? Also, just for clarity, what if my encoded polyline momentarily traverses a segment in the middle of it, but doesn't carry through to the end or start of that segment? Would this still work? – Fell Oct 25 '18 at 13:14
  • @Fell you mean the network geometries? well, honestly, I think it's time to properly rebuilt those roads into a 'network'; single linestrings, correctly noded at intersections. since you are working in PostGIS, I'd also say move on to pgRouting, which provides functionality for both, topology creation (creating the 'network') and routing (finding distances along the network etc.). you have to somehow dump your MultiLinestrings, permanently even, or you cannot really work with 'segments' and their attributes! – ThingumaBob Oct 25 '18 at 13:27
  • a hacky workaround would be to dump the multis (the path column will then have two or more sequences!) get the traversed length like above, and collect back into Multi whith these lengths accumulated; that would hardly represent any valuable info on traversed lengths, though... – ThingumaBob Oct 25 '18 at 13:32
  • I'm not sure I can modify the GIS data so easily. The problem is that I have another table that is very closely related to the segment data for information like traffic counts at time-of-day intervals. Wouldn't doing such sweeping modifications to the segment geometries potentially corrupt the integrity of the related data for segments? – Fell Oct 25 '18 at 13:35
  • @Fell I don't know your data and usecase etc., but, yeah, most likely. point is, a network in terms of GIS is usually based on graph theory, and a graph needs to have a topology of geometric primitives. without it, everything is a hussle, and with Multi geometries it is extra hard to work with. ...I strongly recommend to restructure your data/DB design accordingly, but I know it's a pain in the to do if not familiar with, and from within a setup you use in your daily workflow... – ThingumaBob Oct 25 '18 at 13:49

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.