Match linestrings using Fréchet distance

Question

I have two datasets of roads (both in WGS84). One has nicely digitized geometries, but lack some of the attributes and the other has heeded attributes, but digitized terribly. I want to transfer attributes from the second set to the first one.

Here is an example of two sets (black and orange lines) aligned against OSM

Basically the challenge is to determine which linestring from one dataset corresponds to the given linestring from the other. I'm going to use PostGIS for this task because one dataset is already in the database and there is a ST_FrechetDistance function in PostGIS. I searched for the function that would help to accomplish my task and it seems that Fréchet distance is what is needed - or maybe there are better solutions?

I wonder how to determine reasonable threshold for Fréchet distance value to conclude that lines are related or not?

I measured several distances for the test area and it seems that 0.006 is the threshold I'm looking for, but there is no guarantee that this is true for the rest of the dataset.

Here is example value from the 2 linestrings that do align (one is half the length of the other though):

SELECT ST_FrechetDistance(
'LineString (37.01317091699999651 55.89133175799999975,         
37.01350427900000284 55.89167322899999846, 37.01370659599999868 
55.8918562969999968, 37.01392270800000261 55.89202131599999746, 
37.0140330629999994 55.89208319800000169, 37.01427676299999803 
55.89205225700000312, 37.01486072400000182 55.89188466000000233, 
37.01598266399999915 55.89158040499999913, 37.01677354000000264 
55.89136381499999828, 37.01698045500000234 55.89129935300000085, 
37.01726093999999989 55.89123231300000327, 37.01741727600000331 
55.89123489199999995, 37.01775293899999753 55.8912735689999991, 
37.01881510399999797 55.89140249199999744, 37.01888867400000294 
55.89141538399999831, 37.01929330800000173 55.89149015899999995, 
37.01949102700000083 55.89163197399999916, 37.01986807200000129 
55.89198521800000208, 37.02038306200000051 55.89246480100000269, 
37.02068653700000311 55.89278322999999915, 37.02096242399999682 
55.89309649999999863, 37.02124290900000148 55.89327956099999994, 
37.02149810499999916 55.89351160999999735, 37.02196021500000001 
55.89395765599999777, 37.02218552299999743 55.89415102699999949, 
37.02241083100000196 55.89438564900000017, 37.02290282900000307 
55.89484973300000092, 37.02305456700000263 55.8949966910000029, 
37.02307755799999711 55.8950817719999975, 37.02338103400000335 
55.89511013300000286, 37.02368450899999885 
55.89508435100000128)'::geometry,
'LineString (37.01323479507839664 55.89131127098399787, 
37.01327962101100155 55.89137207276179709, 37.01333908948289775 
55.8914527722402994, 37.01408630813619993 55.89211050199340036, 
37.01414990885830036 55.89209669970679784, 37.01470506770390045 
55.89197610579609687, 37.01728871229249762 55.89122951334790201, 
37.01752766415810214 55.89125747115409837, 37.01901716073069792 
55.89143226995420122, 37.01948167956410174 
55.89158208247790327)'::geometry
) as value

-------------------------------------
value
0.005470800678888038

What is the measurement unit for this value? Is it degrees or something else? Should geometries be transformed to other CRS before distance calculation? How to find out value of the proper threshold?

Answer 1

The function returns a distance measure in CRS units, and transformations are not necessary.

In general, the closer two geometries are according to this measure, the higher the likelihood of a match; in theory, sth. like this should do the trick (in practice you might need to adjust to work with multiple shorter segments matching one larger linestring):

SELECT a.id,
       b.id
FROM   <layer_1> AS a
CROSS JOIN LATERAL (
  SELECT id
  FROM   <layer_2>
  -- WHERE ST_DWithin(a.geom, geom, <distance>)         -- optional: index lookup for closest lines only
  ORDER BY
         ST_FrechetDistance(a.geom, geom, <frac>)
  LIMIT  1
) AS b
;

And in the reality of network matching, you likely still get a headache...

Notes:

• this function only takes vertices into account; the densifyFrac parameter is useful to homogenize the vertex distribution for more confident results, at a (significant) cost in performance
• this function considers vertices in order: it might be better to use the ST_HausdorffDistance when the orientation of linestrings are not identical.
  As per @SS_Rebellious' comment, this might, however, introduce ambiguous minimum distances at intersections.
• naturally, this only works to a degree