Feature request: Add STRtree.nearest function

[FuriousRococo]

Note

Since Shapely support no more than GEOS 3.4.0 right now, it will be great to add other functions like GEOSSTRtree_nearest in GEOS 3.6.0. So I was trying to add this function by myself and meet some problems.

Problems

GEOS source code is like:

const GEOSGeometry *
GEOSSTRtree_nearest (geos::index::strtree::STRtree *tree,
                     const geos::geom::Geometry *g)
{
    return GEOSSTRtree_nearest_r( handle, tree, g);
}

const void* GEOSSTRtree_nearest_generic(GEOSSTRtree *tree,
                                        const void* item,
                                        const GEOSGeometry* itemEnvelope,
                                        GEOSDistanceCallback distancefn,
                                        void* userdata)
{
    return GEOSSTRtree_nearest_generic_r( handle, tree, item, itemEnvelope, distancefn, userdata);
}

Then I added code in strtree.py, ctypes_declarations.py and test.py and tried to run the test but got the error Segmentation fault: 11
strtree.py

from shapely.geometry.base import geom_factory
class STRtree:
    def nearest(self, geom):
        if self._n_geoms == 0:
            return None

        return geom_factory(lgeos.GEOSSTRtree_nearest(self._tree_handle, geom._geom))

ctypes_declarations.py

def prototype(lgeos, geos_version):
    if geos_version >= (3, 6, 0):
        lgeos.GEOSSTRtree_nearest.argtypes = [c_void_p, c_void_p]
        lgeos.GEOSSTRtree_nearest.restype = c_void_p

test.py

from shapely.geometry import Point, Polygon
from shapely.strtree import STRtree

a = []
a.append(Polygon([(1,0),(2,0),(2,1),(1,1)]))
a.append(Polygon([(0,2),(1,2),(1,3),(0,3)]))
a.append(Polygon([(-1.5,0),(-2.5,0),(-2.5,-1),(-1.5,-1)]))
tree = STRtree(a)
tree.nearest(Point(0,0))

I thought my problem is about data processing between the ctypes and geometry, so I tried to reimplement to shared_path function but still got something wrong.

from shapely.geometry import LineString
from shapely.geometry.base import geom_factory
from ctypes import CDLL, c_void_p

dll = CDLL('/Users/*****/anaconda3/lib/python3.7/site-packages/shapely/.dylibs/libgeos_c.1.dylib')
shared_path = dll.GEOSSharedPaths
shared_path.restype = c_void_p
shared_path.argtypes = [c_void_p, c_void_p]
g1 = LineString([((0, 0), (1, 1)), ((-1, 0), (1, 0))])
g2 = LineString([((0, 0), (1, 1)), ((-2, 0), (1, 5))])
geom_factory(shared_path(g1._geom, g2._geom))

Could you help me figure this out, thx!

[sgillies]

Hi @FuriousRococo , I'm not familiar with using the nearest neighbor search functions, but it looks like you're approximately on the right track. However, at https://github.com/libgeos/geos/blob/master/capi/geos_c.h.in#L1824, I see a sign that we need to use the generic method because the items in our tree are Python objects. I think you will need to give https://github.com/libgeos/geos/blob/master/capi/geos_c.h.in#L1850 a try .

[FuriousRococo]

Thanks for the advice @sgillies , I think it's working now.
strtree.py

class STRtree:
    def nearest(self, geom):
        if self._n_geoms == 0:
            return None
        
        envelope = geom.envelope

        def callback(item1, item2, distance, userdata):
            try:
                geom1 = ctypes.cast(item1, ctypes.py_object).value
                geom2 = ctypes.cast(item2, ctypes.py_object).value
                dist = ctypes.cast(distance, ctypes.POINTER(ctypes.c_double))
                lgeos.GEOSDistance(geom1._geom, geom2._geom, dist)
                return 1
            except:
                return 0 
        
        item = lgeos.GEOSSTRtree_nearest_generic(self._tree_handle, ctypes.py_object(geom), envelope._geom, \
            lgeos.GEOSDistanceCallback(callback), None)
        geom = ctypes.cast(item, ctypes.py_object).value
        
        return geom

ctypes_declarations.py

def prototype(lgeos, geos_version):
    if geos_version >= (3, 6, 0):
        lgeos.GEOSDistanceCallback = CFUNCTYPE(c_int, c_void_p, c_void_p, c_void_p, c_void_p)

        lgeos.GEOSSTRtree_nearest_generic.argtypes = [
            c_void_p, py_object, c_void_p, lgeos.GEOSDistanceCallback, py_object]
        lgeos.GEOSSTRtree_nearest_generic.restype = c_void_p

test.py

from shapely.geometry import Point, Polygon
from shapely.strtree import STRtree

a = []
a.append(Polygon([(1,0),(2,0),(2,1),(1,1)]))
a.append(Polygon([(0,2),(1,2),(1,3),(0,3)]))
a.append(Polygon([(-1.5,0),(-2.5,0),(-2.5,-1),(-1.5,-1)]))
a.append(Point(0,0.5))
tree = STRtree(a)
pt = tree.nearest(Point(0,0))
print(pt.wkt)

Output
POINT (0 0.5)

[snorfalorpagus]

@FuriousRococo Do you want to submit a pull requests with this new feature?

[asif-rehan]

Thanks for adding the feature @FuriousRococo. A question while trying to understand this nearest function. Say I am trying to find nearest road for a point. So the STR tree is a tree of MultiLineString roads. So in this case, is the nearest road given using the distance projected distance from the point to the MultiLineStrings? Or is it based on the smallest distance to the centroids of the MultiLineStrings representing the roads? Thank you!

[FuriousRococo]

I've wrote a test and I think the nearest function check every line in MultiLineString to see if the nearest line is inside MultiLineString. Here is my script @asif-rehan
test.py

from shapely.strtree import STRtree
from shapely.geometry import Point, LineString, MultiLineString

tree_list = [LineString([[0,1],[1,1]])]
tree_list.append(MultiLineString([LineString([[0,0],[1,0]]),LineString([[0,3],[1,3]])]))
tree = STRtree(tree_list)

tree.nearest(Point(0.5,0.25)).wkt

Output
MULTILINESTRING ((0 0, 1 0), (0 3, 1 3))