I'm working on a program that determines the closest location from a given point. The point cloud I'm testing against is very big (~800.000). However, this doesn't really explain why my implementation is so slow. This is my approach:
First, I created a spatial index for the point shape
pntshp.ExecuteSQL('CREATE SPATIAL INDEX ON %s' % table_name)
I defined an array of buffer distances to narrow down the search radius. Which of course also means that I have to create a buffer for each point (which might be expensive).
BUFFER_DISTANCES = ( 0.001, 0.005, 0.01, 0.02, 0.05 ) # 100m, 500m, 1km, 2km, 5km
Then, the buffer is used as a spatial filter
If the filter returns
None the buffer distance will be increased.
for buffer_d in BUFFER_DISTANCES: buffr = get_buffer(xy_street,buffer_d) ...
Then I am calculating the distance to the points returned by the spatial filter
p=ogr.Geometry(ogr.wkbPoint) p.AddPoint(xy,xy) for feat in node_lyr: geom = feat.GetGeometryRef() d = p.Distance(geom) dist.append(d)
To get the closest point:
def get_closest_pnt(dist, node, how_close): mrg = zip(dist,node) mrg.sort(key=lambda t: t) try: return mrg[how_close] except IndexError, ierr: print '%s \ndist/node tuple contain %s' % (ierr,mrg)
It all works fine but is really slow. Creating a spatial index didn't show any effect, really. To calculate 100 points this implementations takes ~6,7 seconds. The program needs to be able to calculate the closest location for more than 2000 points as fast as possible. Any ideas on how to improve my approach?
I tried different approaches to see where it gets me. I came across something very astonishing I want to share here.
I implemented a simple lookup algorithm as described here, and one of the solutions that where suggested (the sorted set approach).
The surprising fact is that performance is not only dependent on the implementation but even more so of the OSX. My original ogr/buffer algorithm turns out to be blazing fast on my OSX whereas it is painstaking slow on Linux (hence the question here).
Here are my results (100 runs).
Method | OSX | Linux Ubuntu ogr buffer | 0:00:01.434389 | 0:01:08.384309 sub string | 0:00:19.714432 | 0:00:10.048649 sorted set | 0:00:01.239999 | 0:00:00.600773 Specs Mac OSX Processor 4x2.5 GHz Memory 8 GB 1600 MHz Specs Dell Linux Ubuntu Processor 8x3.4GHz Memory 7.8 GB
If someone can explain why these differences occur, please don't hesitate.