# Algorithms for finding nearest road

Having two LineStrings I want to know if they actually are the same gps path or not. I guess something like if the distance between these are lower than x for a few points I would assume that they are equal and can be plotted as one. The purpose would be to increase the accuracy of the gps when I know that a given path is followed. Is there any algorithms for this and what are they called?

You can use Hausdorff distance:

Two sets are close in the Hausdorff distance if every point of either set is close to some point of the other set.

Here I cross join the table to itself to compare the three lines to eachother:

``````with lines as
(
select 1 as id, st_setsrid(st_geomfromtext('LineString (521330 6577690, 521026 6578189, 520734 6578542, 520496 6578791, 520448 6578913, 519687 6579029, 519443 6579224, 519157 6579631, 518889 6579826, 518670 6580210, 518689 6580514)'), 3006) as geom
union
select 2 as id, st_setsrid(st_geomfromtext('LineString (521324 6577726, 520551 6578901, 519577 6579084, 518829 6579814, 518646 6580240, 518670 6580654)'), 3006) as geom
union
select 3 as id, st_setsrid(st_geomfromtext('LineString (521817 6577793, 519699 6578840, 518847 6580703)'), 3006) as geom
)

select a.id as aid, b.id as bid, round(st_hausdorffdistance(a.geom, b.geom)) as distance
from lines a
cross join lines b
order by aid
``````

Line 1 is most similar to itself and most dissimilar to line 3:

``````aid bid distance
1   1   0.0
1   3   498.0
1   2   141.0
2   2   0.0
2   3   498.0
2   1   141.0
3   1   498.0
3   3   0.0
3   2   498.0
``````

Another algorithm you can use is FrechetDistance