Faster spatial queries in Tile38

Search complex geospatial data in an instant

Josh Baker
Oct 15, 2018 · 2 min read

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.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store