Match housenumbers on buildings (special case of point-in-polygon-test)

Question

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.

Simple solution

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

Problem

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

Idea

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

Question

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.

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.