Finding the point in a polyline that is closest to an arbitrary point A

[Daryl Wilding-McBride]

Hello,

I'm trying to find the point in a polyline that is closest to an
arbitrary point A (that is not part of the polyline). A couple of
approaches come to mind:

1. Iterate through each point in the polyline and calculate the
distance to A, and then select the polyline point with the smallest
distance.
2. Draw a circle with a small radius with its centre at A and find if
it intersects with the polyline. Gradually increase the radius until
the circle intersects with the polyline, and somehow find the closest
point on the polyline to the point of intersection.

Is there a better approach? Is there a function in rgeo that will help
with this?

Thanks,
Daryl.

[Daniel Azuma]

Hi Daryl,

RGeo itself doesn't give you this function. However, the libgeos C library that provides most of the underlying geometric implementation, does provide an implementation that will help you. So the trick is accessing the C library calls from the RGeo Ruby objects.

To accomplish this, use the geos ffi factory (which requires the ffi-geos gem). Object created by this factory give you access to low-level geos objects that you can manipulate using ffi-geos's api (which themselves are basically thin wrappers around the libgeos C api calls).

# Create a Geos factory that uses the ffi interface
factory = RGeo::Geos.factory(:native_interface => :ffi)

# Create your polyline and point A using that ffi-backed factory.
# You can create the objects directly using the factory, or cast objects to the
# factory, whatever is the easiest way for you to get objects that are attached
# to the ffi factory.
polyline = factory.line_string( ... )
point = factory.point( ... )

# Objects that are attached to an ffi-geos factory provide access, via the
# fg_geom method, to low-level objects that understand the ffi-geos api.
# This is not really documented well, but it's a stable api that you can use.
low_level_polyline = polyline.fg_geom
low_level_point = point.fg_geom

# Now invoke the low-level libgeos calls.
# This first method, "project", gives you the distance "along" the linestring
# where it comes closest to the given point.
dist = low_level_polyline.project(low_level_point)
# This second method, "interpolate", takes a distance "along" the linestring,
# and returns the actual point on the linestring.
low_level_closest_point = low_level_polyline.interpolate(dist)

# Finally, wrap the low-level result in an RGeo point object
closest_point = factory.wrap_fg_geom(low_level_closest_point)

You probably already understand the issues with the other approaches you mentioned. In the first case, if you iterate over the vertices in the linestring, you'll miss cases where the closest point is in the middle of one of the segments rather than on one of the vertices. In the second case, well, the issues are pretty plain.

Daniel

[Yarin Kessler]

The ffi interface also gives you the nearest_points method, which you can on any two geometries.