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.


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 that you have read and understand our privacy policy and code of conduct.

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