Faster spatial queries in Tile38

Search complex geospatial data in an instant

The most common request from Tile38 users is for faster spatial queries. Specifically the point-in-polygon operation.

I pushed an update to the master branch over the weekend that includes faster point-in-polygon and geometry intersect operations. The performance increase comes from indexing complex polygon segments into discrete R-trees and ray casting the point as a rect with infinite X extents.

Here’s an example of the performance increase.

Indexing the segments

First take all of the polygon’s segments and bulk load them into an R-tree. This makes searching for segments very fast.

For simple polygons, less than 64 points, there’s no need to index.

Search for segment candidates

With an indexed polygon, finding the segments for ray casting is super fast. You just make a rectangle with the min-y and max-y coordinates equal to the target point and the min-x and max-x equal to -infinity and +infinity. Then search for the r-tree for overlapping rectangles.

From there you perform the Ray casting algorithm on the segments.

You can find this update in Tile38’s master branch today.