← All articles

By ·

The Fastest Point-in-Polygon Join in Python: GeoPandas sjoin vs STRtree vs Prepared Geometries vs H3, Benchmarked to 10 Million Points

Point-in-polygon in Python, benchmarked on 10 million points: from 3.6 seconds to 2 minutes on the same Punjab districts, depending on which side you index.

The fastest point-in-polygon method in Python depends on the shape of your polygons. For a few large polygons, prepared geometries with shapely.contains_xy assigned 10 million points in 2.9 to 3.6 seconds. For thousands of small polygons, geopandas.sjoin or an STRtree took 13 to 18 seconds, and an H3 lookup 9.6 seconds. The biggest trap was building the spatial index on the wrong side: on detailed district boundaries it turned a 13.5-second join into a 2-minute one.

Assigning points to polygons is one of the most common jobs in spatial data work: geocoded customers to sales territories, GPS pings to zones, incidents to fire districts, survey households to union councils. At thousands of points any method works. At millions, the method you pick decides whether the job takes seconds or a coffee break. I benchmarked six approaches on three polygon layers to find out which to use when.

How was the benchmark set up?

Polygon layers, chosen to cover the cases people actually meet:

LayerPolygonsVertices in totalTypical use
Calgary H3 hexagons (resolution 8)1,2058,435Many small zones: grids, neighbourhoods, postcodes
Punjab districts, simplified365,046A few large zones, web-map quality boundaries
Punjab districts, detailed36101,415A few large zones, survey-grade boundaries

The detailed Punjab layer is the simplified one with extra vertices inserted every 0.0015° (about 150 m), so the shapes are identical and only the vertex count changes. That isolates the effect of boundary detail.

Points: 100,000, 1 million and 10 million per layer, in WGS84 longitude and latitude. Calgary points were drawn in proportion to population from the Kontur hexagons with a little random scatter. Punjab points were uniform over the province's bounding box, so a share of them fall outside every district, as real data often does.

Machine and software: a single Python process on a 4-vCPU cloud VM, Python 3.13, GeoPandas 1.2, Shapely 2.2 and h3-py 4.5. Times include building point geometries where a method needs them. Every method was checked against the STRtree result, and all exact methods agreed on 100% of points.

The six methods:

  1. Python loop: for each point, test each polygon with polygon.contains(point) until one matches.
  2. STRtree on polygons: build shapely.STRtree on the polygons and query it with all points, predicate="within".
  3. STRtree on points: build the tree on the points and query it with the polygons, predicate="contains".
  4. GeoPandas sjoin: gpd.sjoin(points, polygons, predicate="within").
  5. Prepared polygons: for each polygon, shapely.prepare, keep points inside its bounding box, then test them with shapely.contains_xy.
  6. H3 lookup: convert each point to an H3 cell with h3.latlng_to_cell and look the cell up in a dictionary built from the polygons.

What were the results?

Bar charts of the time to assign 10 million points to polygons for six methods on three layers. A Python loop takes about 14 minutes on Calgary's hexagons. STRtree built on detailed district polygons takes 2 minutes. Prepared polygons take 2.9 to 3.6 seconds on Punjab's districts. H3 lookup takes 9.6 seconds on Calgary's hexagons

Seconds to assign 10 million points:

MethodCalgary hexagonsPunjab, simplifiedPunjab, detailed
Python loop~853 (est.)~72 (est.)~74 (est.)
STRtree on polygons, within14.916.5142.6
STRtree on points, contains14.713.513.5
geopandas.sjoin17.815.618.1
Prepared + bbox + contains_xy34.22.93.6
H3 lookup (resolution 8)9.6~12 (est.), approximaten/a

Loop times are extrapolated from 100,000 points and the Punjab H3 time from 1 million, because all methods scaled close to linearly. At 1 million points:

MethodCalgary hexagonsPunjab, simplifiedPunjab, detailed
STRtree on polygons1.491.6514.25
STRtree on points1.091.021.06
geopandas.sjoin1.451.251.45
Prepared + bbox + contains_xy2.180.220.30
H3 lookup0.921.24 (res 8)n/a

What do the results mean?

1. Never loop over points in Python

The loop gave the right answer and was the slowest by far: an estimated 14 minutes for 10 million points against 1,205 hexagons, around 90 times slower than an H3 lookup and 50 times slower than sjoin. Every loop iteration creates a Python object and calls into GEOS once. Vectorised Shapely 2 functions do the same work in C, over whole arrays.

2. A few big polygons: prepare them and filter by bounding box

With 36 districts, the prepared approach was 5 times faster than sjoin: 2.9 seconds against 15.6. It loops over polygons, not points, so there are only 36 Python iterations. For each one, a cheap NumPy comparison throws out points outside the district's bounding box, and contains_xy tests the rest without ever building point objects. Preparing the polygon builds an internal index of its edges, which is why adding 20 times more vertices only moved the time from 2.9 to 3.6 seconds.

import numpy as np
import shapely

def assign_points(x, y, polygons):
    """Index of the polygon containing each point, or -1. x, y are NumPy arrays."""
    out = np.full(len(x), -1)
    shapely.prepare(polygons)
    for k, poly in enumerate(polygons):
        xmin, ymin, xmax, ymax = shapely.bounds(poly)
        idx = np.flatnonzero((x >= xmin) & (x <= xmax) & (y >= ymin) & (y <= ymax))
        inside = shapely.contains_xy(poly, x[idx], y[idx])
        out[idx[inside]] = k
    return out

district = assign_points(df.lon.values, df.lat.values, districts.geometry.values)

The same approach was the slowest exact method on Calgary's 1,205 hexagons, at 34 seconds, because each of the 1,205 iterations scans all 10 million coordinates for the bounding-box filter. It is the right tool for tens of polygons, not thousands.

3. Many small polygons: sjoin or an STRtree, built the right way round

With 1,205 hexagons, sjoin and both STRtree variants landed between 14.7 and 17.8 seconds. Here the spatial index does the real work, narrowing each point to one or two candidate hexagons. sjoin is the most convenient, because it keeps attributes and returns a GeoDataFrame:

import geopandas as gpd

pts = gpd.GeoDataFrame(df, geometry=gpd.points_from_xy(df.lon, df.lat), crs=4326)
joined = gpd.sjoin(pts, zones[["zone_id", "geometry"]], how="left", predicate="within")

Two details matter. Build points with points_from_xy, never by applying Point() row by row. And make sure both layers share the same CRS before joining, which GeoPandas warns about but does not enforce.

4. The side you index matters on detailed boundaries

This was the surprise. On the detailed districts, an STRtree built on the polygons and queried with 10 million points took 142.6 seconds. Building the tree on the points and querying with 36 polygons took 13.5 seconds, for exactly the same assignments.

Shapely tests the predicate between each query geometry and its candidate tree geometries. With the tree on polygons, every one of the 10 million point queries runs a point-in-polygon test against a raw polygon of up to several thousand vertices. With the tree on points, there are only 36 query geometries, and each detailed polygon's cost is paid once per polygon rather than once per point. sjoin was not slowed by the detailed boundaries either, at 18.1 seconds, so the convenient option also avoided the trap.

import numpy as np
import shapely

points = shapely.points(x, y)
tree = shapely.STRtree(points)                       # index the many simple geometries
poly_idx, pt_idx = tree.query(polygons, predicate="contains")
zone = np.full(len(points), -1)
zone[pt_idx] = poly_idx

The general rule: index the many simple geometries, and query with the few complex ones.

5. H3 is the fastest when your zones are H3 cells

When the polygons are H3 cells, converting each point to its cell and looking it up in a dictionary is not an approximation. It is the definition. It took 9.6 seconds for 10 million points, the fastest result on that layer, even though h3-py was called one point at a time from Python. It agreed with the geometric join on 99.97% of points. The remaining 0.03% is most likely down to the hexagon outlines in my file, which are rounded to 5 decimal places and so differ by up to about a metre from H3's own cell edges.

For other polygons, H3 gives an approximation. I filled each Punjab district with H3 cells and looked points up the same way:

H3 resolutionAverage cell areaCells for PunjabPoints matched to the right districtPoints left unassigned
75.2 km²36,83398.0%0.4%
80.74 km²257,86499.2%0.15%

Errors sit along district borders, where a cell is assigned to whichever district holds its centre. For a heat map or a dashboard that is fine. For anything with money or legal weight attached, such as tax districts, insurance zones or NG911 emergency service boundaries, use an exact geometric test.

Which method should you use?

Your situationUse
Up to a few hundred thousand points, any polygonsgeopandas.sjoin, for convenience
A few to a few dozen large polygons, millions of pointsPrepared polygons + bounding-box filter + contains_xy
Hundreds to thousands of polygons, millions of pointssjoin, or an STRtree built on the points
Your zones are H3 cellsH3 cell lookup
Approximate counts for a dashboard, any zonesPre-fill zones with H3 cells, then look up
Detailed boundaries and a raw STRtreeBuild the tree on the points, not the polygons
Data that does not fit in memoryA spatial database such as PostGIS, or chunked processing

How can you make it faster still?

What are the limits of this benchmark?

What should you take from this?

Start with geopandas.sjoin: it was never the fastest, but it was never the trap either, landing between 15.6 and 18.1 seconds on every layer. When you need more speed, match the method to your polygons. For a few large zones, prepare them and use contains_xy, which was 5 times faster here. For H3 zones, use H3 lookups. If you work with a raw STRtree, build it on the many simple geometries. And whatever you choose, keep the loop out of Python.

If you have a large geocoding, assignment or spatial join pipeline that needs to run faster or more reliably, email me at mahad.imran29@gmail.com.

Frequently asked questions

What is the fastest way to do point in polygon in Python?

It depends on the polygons. For a few large polygons, such as districts or counties, preparing each polygon with shapely.prepare, filtering points by its bounding box and calling shapely.contains_xy was fastest in my test: 10 million points in 2.9 to 3.6 seconds. For thousands of small polygons, geopandas.sjoin or an STRtree built on the points took 13 to 18 seconds, and an H3 cell lookup took 9.6 seconds when the polygons were H3 cells.

Why is my GeoPandas sjoin slow?

Common causes are building points one at a time in a Python loop, joining in the wrong order, using the wrong predicate, or mixing coordinate systems so the spatial index cannot discard anything. Build point geometries with geopandas.points_from_xy, keep both layers in the same CRS, and use predicate='within' or 'intersects'. In my benchmark sjoin assigned 10 million points to 1,205 polygons in about 18 seconds.

Does the side of the spatial index matter in Shapely STRtree?

Yes, a lot when polygons are detailed. With 36 districts holding 101,415 vertices, building the STRtree on the polygons and querying with 10 million points took 143 seconds. Building the tree on the points and querying with the polygons, predicate='contains', took 13.5 seconds for the same answer.

Can H3 replace point-in-polygon?

Exactly, when the polygons are H3 cells: converting each point to its cell and looking it up gives the same answer as a geometric test. For other polygons, H3 is an approximation. Filling Punjab's districts with resolution 8 cells assigned 99.2% of points to the right district and left 0.15% unassigned. That is fine for heat maps and dashboards, not for billing or legal boundaries.

How long does a spatial join of 10 million points take?

On a single core of a 4-vCPU cloud machine, between 2.9 seconds and about 14 minutes in my test, for the same result. Vectorised approaches took 2.9 to 143 seconds. A plain Python loop over points and polygons was 25 to 90 times slower than the best vectorised method for each layer.

Let's talk.

Best way to reach me is email. I respond to most things.