Fastest point-in-polygon solution with billions of points over thousands of polygons

Question

Problem definition is quite simple: I need to achieve point-in-polygon detection for:

• billions of lat/lon points
• over thousands of polygons

I need to be able, for every point, to determine if it is in one or several of the polygons available (in the thousands). Currently we are using PostGIS with ST_Contains but the whole things needs 3 good entire days (roughly 80 hours) to compute from start to finish.

Is there any solution (free or not) that would offer significant speed improvement for this workload over PostGIS? It can be anything from an analytical database (Exasol is one example that comes to mind, however although hugely faster than Postgres as a database, I'm not sure if it's any faster for geographical computations) to a dedicated C/C++/Rust piece of code.

Answer 1

You need some kind of precomputed index structure.

In this case, a grid might be useful. They are usually not used for general-purpose applications because it would be hard to choose the proper grid cell size, but your polygons should have known characteristics.

First, choose a fixed grid. For each grid cell, store two lists: polygons that completely cover the grid cell, and polygons that partically cover the grid cell. Make the grid cells small enough so that almost all of them are completely inside or outside all polygons.

To check a point, compute the grid cell number from its coordinates, and then read that cell's lists. You need to do raycasting only for partially covered cells (and for complex polygons, it is useful to precompute the intersection with the cell).

You need to write some code yourself, but at least the initial computation of the grid index can be done with PostGIS.