Shapely: Get Nearest Point on Linestring

Created on 18 Oct 2014 · 3Comments · Source: Toblerity/Shapely

Hello,
Given a point, I am trying to get the nearest point on a linestring. It seems to work fine for a simple linestring, e.g
Python 3.4.0 (default, Apr 11 2014, 13:05:11)
[GCC 4.8.2] on linux
Type "help", "copyright", "credits" or "license" for more information.

from shapely.geometry import Point, LineString
line = LineString([(0,0),(5,7),(12,6)])
p = Point(4,8)
np = line.interpolate(line.project(p))
print(np)
POINT (5 7)

However, for a complex linestring I am not getting the intended results.e.g.

route=LineString([(19.119318,72.902800),(19.119660,72.901455),(19.119673,72.901401),(19.119848,72.900553),(19.119975,72.899972),(19.120129,72.899675),(19.120308,72.899385),(19.120589,72.899162),(19.121131,72.898909),(19.121597,72.898739),(19.122330,72.898471),(19.122696,72.898429),(19.123296,72.897991),(19.123680,72.897623),(19.124095,72.897035),(19.124402,72.896411),(19.124483,72.896177),(19.124573,72.895796),(19.124585,72.895470),(19.124603,72.895014),(19.124652,72.894291),(19.124686,72.894067),(19.124929,72.893177),(19.124971,72.893049),(19.125097,72.892666),(19.125214,72.892323),(19.125450,72.891802),(19.125757,72.891281),(19.125951,72.890874),(19.126170,72.890413),(19.126833,72.889417),(19.127319,72.888873),(19.128909,72.886714),(19.129060,72.886402),(19.129109,72.886299),(19.129238,72.885913),(19.129302,72.885370),(19.129372,72.881686),(19.129396,72.880652),(19.129413,72.880540),(19.129366,72.880167),(19.129382,72.880070),(19.129419,72.879849),(19.129509,72.879205),(19.129709,72.877766),(19.129969,72.876684),(19.130029,72.876511),(19.128367,72.875341),(19.127365,72.874602),(19.125882,72.873536),(19.125160,72.873014),(19.124815,72.872761),(19.124413,72.872457),(19.123149,72.871568),(19.122517,72.871091),(19.122162,72.870822),(19.121981,72.870749),(19.121736,72.870651),(19.121013,72.870576),(19.119933,72.870464),(19.119596,72.870432)])

list(route.coords)
[(19.119318, 72.9028), (19.11966, 72.901455), (19.119673, 72.901401), (19.119848, 72.900553), (19.119975, 72.899972), (19.120129, 72.899675), (19.120308, 72.899385), (19.120589, 72.899162), (19.121131, 72.898909), (19.121597, 72.898739), (19.12233, 72.898471), (19.122696, 72.898429), (19.123296, 72.897991), (19.12368, 72.897623), (19.124095, 72.897035), (19.124402, 72.896411), (19.124483, 72.896177), (19.124573, 72.895796), (19.124585, 72.89547), (19.124603, 72.895014), (19.124652, 72.894291), (19.124686, 72.894067), (19.124929, 72.893177), (19.124971, 72.893049), (19.125097, 72.892666), (19.125214, 72.892323), (19.12545, 72.891802), (19.125757, 72.891281), (19.125951, 72.890874), (19.12617, 72.890413), (19.126833, 72.889417), (19.127319, 72.888873), (19.128909, 72.886714), (19.12906, 72.886402), (19.129109, 72.886299), (19.129238, 72.885913), (19.129302, 72.88537), (19.129372, 72.881686), (19.129396, 72.880652), (19.129413, 72.88054), (19.129366, 72.880167), (19.129382, 72.88007), (19.129419, 72.879849), (19.129509, 72.879205), (19.129709, 72.877766), (19.129969, 72.876684), (19.130029, 72.876511), (19.128367, 72.875341), (19.127365, 72.874602), (19.125882, 72.873536), (19.12516, 72.873014), (19.124815, 72.872761), (19.124413, 72.872457), (19.123149, 72.871568), (19.122517, 72.871091), (19.122162, 72.870822), (19.121981, 72.870749), (19.121736, 72.870651), (19.121013, 72.870576), (19.119933, 72.870464), (19.119596, 72.870432)]

end=Point(19.125150,72.893218)

np = route.interpolate(route.project(end))

print(np)
POINT (19.12493833590478 72.89314854771877)

I was expecting the result to be 19.124929, 72.893177. Is it something which I am doing wrong? Any help appreciated.

Thanks!

Source

chivasblue

Most helpful comment

The point returned is the nearest point on the line to the original point. The nearest point is _not_ necessarily an existing vertex in the LineString, and in this case it isn't.

end = Point(19.125150,72.893218)
np = Point(19.12493833590478, 72.89314854771877)
expected = Point(19.124929, 72.893177)

print end.distance(np) # 0.000222767386696
print end.distance(expected) # 0.000224770994572

If you want to find the nearest vertex you should first convert the LineString to a MultiPoint geometry, then use the nearest_points operation (note the minor floating point error):

from shapely.ops import nearest_points
from shapely.geometry import MultiPoint
mp = MultiPoint(route)
print nearest_points(mp, end)[0] # POINT (19.124929 72.89317699999999)

This query requires calculating the distance between the original point and each vertex in the original linestring. For very complex routes this could be rather slow. If this is the case you should consider using the rtree module, which uses spatial indexing to make this kind of query very fast:

http://toblerity.org/rtree/tutorial.html

snorfalorpagus on 18 Oct 2014

❤5 👍5 🎉1

All 3 comments

The point returned is the nearest point on the line to the original point. The nearest point is _not_ necessarily an existing vertex in the LineString, and in this case it isn't.

end = Point(19.125150,72.893218)
np = Point(19.12493833590478, 72.89314854771877)
expected = Point(19.124929, 72.893177)

print end.distance(np) # 0.000222767386696
print end.distance(expected) # 0.000224770994572

If you want to find the nearest vertex you should first convert the LineString to a MultiPoint geometry, then use the nearest_points operation (note the minor floating point error):

from shapely.ops import nearest_points
from shapely.geometry import MultiPoint
mp = MultiPoint(route)
print nearest_points(mp, end)[0] # POINT (19.124929 72.89317699999999)

http://toblerity.org/rtree/tutorial.html

snorfalorpagus on 18 Oct 2014

❤5 👍5 🎉1

Oh ok Thanks for your response.

chivasblue on 18 Oct 2014

@snorfalorpagus . I was searching for something like this. any smart suggestions to get rid of the floating point error? Same issue is there with this tool also.