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? – John Powell Oct 30 '14 at 14:47
  • No, I have the data in memory. I'm programming in C++. – user2033412 Oct 30 '14 at 15:08
  • 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. – John Powell Oct 30 '14 at 15:16

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, privacy policy and cookie policy

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