Hacker News Reader

Rust is great but isn’t the core problem here using the wrong algorithm? It looks like this is ideally suited for a quad tree instead of a naive for loop. I would expect that to pulverise any current benchmark.

View on HN

I guess you also need to take the time into account to create the quad tree from an unsorted 'polygon soup' first, and in terms of coding effort, a brute force conversion from python to a compiled tight loop over unsorted arrays provides a lot of bang for the buck (and a speedup of 100x for relatively little effort might be 'good enough' for quite a while until the input data grows big enough to require the next optimization effort).

(e.g. it doesn't need to be "as fast as possible", just fast enough to no longer be a workflow bottleneck)

Im assuming the polygons dont change to often so you can amortize the construction of the quadtree. Depending on your world view the implementation is trivial since Shapely, a dependency they already likely have, has an implementation of it.

Author here: actually, in this analogy (as this is just a demo library), the polygons change each time so we couldn't use this type of optimization (at least not in a straightforward way).

Reply on news.ycombinator.com