How to detect the area of a given place in a map in c++?

Question

I'm developing a project where I need to detect wether a given area is covered by a certain place. For example:

Suppose that image is my map, and there are 2 places with a given area the one with yellow color and the other with green color, so if I ask my app: "Which places cover the area from 1 to 3 and from A to F?" It should tell me both places, and so on.

I was thinking on using a matrix, but I need to load 5 maps, each one different, for example, the second map starts at H and ends in M and starts in 10 and ends in 30. So I'm not sure what else to use, any ideas?

Answer 1

Typically finding 2-dimensional regions which overlap or intersect some other region is a job for the data structure known as an R-Tree. Places are entered into the R-Tree. Then you query the rtree to see which ones are hit by the query region. You could either use a C++ R-Tree library and put the places into the in-memory R-Tree Or you could put your places in database that supports R-Trees, like sqite. You would save the places to the database and then bring in them in to memory by querying the database. Sqlite is a in-process database. You would not need to setup a separate server for this.