How do I identify what region a randomly generated point falls in on a map?

[#1]

I posted this question already on stackoverflow but was pointed to the community since it is more likely to get an answer. There is also a picture representation of what my problem entails.

Essentially, I have a "map" that consists of several rectangular regions. I have access to the coordinates of all the vertices of each rectangular region (their x_min, x_max, y_min, y_max).

I randomly generate a point that lies anywhere on that map. I know the coordinates of that point (x and y). The problem I want to solve is to find out in what region the point lies in.

what I have done, is just go through a big condition statement checking through one by one if the x & y coordinate of the point is between the x_min and x_max and y_min and y_max of every region. However, I feel like there has to be a more scalable, generalizable, and efficient way to do this but I cannot find a way to do so, at least not something that isn't in a library for a different programming language. I thought of maybe doing something where I split the map in half, find out which half the point lies in, count up all the regions in that half, check if there is one region left and if not, split the map in half again and go through the process again. I just don't have a good idea of how that can be implemented and whether that is feasible or better that the current method I have.

[#2]

If I was inventing an algorithm for the tiled rectangular regions, I'd use the KDTable function and load all the corner points into the table. Something like this:

one to four rectangles share each corner

The KDTable will efficiently tell which corner is closest to any queried x-y location. If you keep another table of all the rectangles that share that point, you only need to check up to four. Depending how you order the data, just knowing <x, <y (etc) tells which quadrant, and you might not need to check as much.

The KDTable is pretty much doing what you described, in K dimensions. for x-y data, K==2.

[#3]

Or maybe it is harder.

This will find the wrong corner.

[#4]

How much resolution do you need? If a 10K by 10K bitmap would be good enough, and there are less than 16E6 polygons, you can draw the rectangles into the bitmap with unique colors (2^24 colors is 16 million colors) and query a rounded x-y pixel instantly. I did something like that in JSL BLOB in an ESP32 Clock  for gps lookups in a timezone map. In my case, I took the resolution I could get which was a mile or two near a timezone boundary; I didn't need the speed as much as being able to run-length encode the bitmap to make it fit a tiny computer.

edit: apparently I made a bitmap this big

composition = J( 16000, 30000, 0 );

which either ran out of memory or exceeded a pixel limit if I went bigger...I used 16000 for the +/- 90 degree latitude and 30K (not 32K) for the +/- 180 degree longitude.That's over a GB uncompressed. You'd need a PNG file, NOT a JPG. JPG would not preserve the colors.

[#5]

Likely no larger than 20K by 20K, although I'm not sure. The current map is about ~10K by ~7K.

[#6]

Because the rectangles don't seem to be rotated and are not overlapping:

Four checks/loops and always remove those which do not match:

1. Check for all squares which have x_min smaller than point's x

2. Check from all squares, which are left, which have x_max larger than point's x

3. Check from all squares, which are left, which have y_min smaller than point's y

4. Check from all squares, which are left, which have y_max larger than point's y

And you can stop at any point of these if only one square is left. In case of JMP you could do this with the help of Loc().

Or then loop over all squares min max values and break when you find a match with something like:

:xmin < x < :xmax & :ymin < y < :ymax

Couple of links that might be related and have fancier possible solutions:

https://stackoverflow.com/questions/1897779/test-if-point-is-in-some-rectangle 

https://www.reddit.com/r/programming/comments/80dlc/i_have_a_set_of_rectangles_and_need_to_determine... 

[#7]

I'll take a look at this solution.