Task with example

I'm working with geodata (country-size) from openstreetmap. Buildings are often polygons without housenumbers and a single point with the housenumber is placed within the polygon of the building. Buildings may have multiple housenumbers.

I want to match the housenumbers to the polygons of the buildings. Example

Simple solution

Foreach housenumber perform a point-in-polygon-test with each building-polygon.


Way too slow for about 50,000,000 buildings and 10,000,000 address-points.


Build and index for the building-polygons to accelerate the search for the surrounding polygon for each housenumber-point.


What index or strategy would you recommend for this polygon-structure? The polygons never overlap and the area is sparsly covered.

This is a duplicate from stackoverflow.com. It was recommended to post the question here.

  • You have the data in Postgres? Commented Oct 30, 2014 at 14:47
  • No, I have the data in memory. I'm programming in C++. Commented Oct 30, 2014 at 15:08
  • 3
    Perhaps you could add the tag. Not very clear from question. Trivial to do with postgres/postgis (and also what osm is natively stored in) which is why I asked. Commented Oct 30, 2014 at 15:16
  • An rtree seems appropriate for this. Boost has a C++ implementation
    – mikewatt
    Commented Jun 22, 2021 at 1:29
  • Cross-posted as stackoverflow.com/q/26650308/820534
    – PolyGeo
    Commented Nov 28, 2021 at 23:52

1 Answer 1


I have the same problem in my mapping software. I am not sure if this is helpful, so forgive me if it doesn't address your actual difficulty, but what I do when searching for addresses is a form of lazy evaluation. I find all the building polygons and address points near a desired street after searching for the street, so there will only be a few hundred, then match up points with polygons.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.