Effectively determine which rectangle a point is in 2d space

Question

I have a large set of rectangles that are drawn on html5 canvas.

I would like to be able to interact with this image using mouse tracking (I cannot use SVG because it does not scale to 10-100k rectangles). Is there any / algo data structure that, given the x, y coordinates of the mouse, will be able to tell you which window the mouse ended in (using calculated rectangle locations)? I thought something like a kd tree, but was not sure.

Answer 1

If your data is always displayed on the form, I think you should be better than the spatial tree data structure.

Since the data is structured in y , you should be able to calculate which “strip” of rectangles the points are based on based on offsets in O(1) time.

If you store the individual rectangles in each strip in sorted order (using xmax say), you should then find the specific rectangle inside the strip using binary search (in O(log(n)) ).

Hope this helps.

Answer 2

A naive solution would be to loop over all the rectangles and check if you are in it. Checking for one rectangle is simple (if you want, I will write it explicitly).

If you have a lot of rectangles and care about performance, you can easily speed up the process by placing the rectangles in the data structure, which will look faster. Looking at the image you sent, one obvious property of your data is that there is a limited number of vertical positions (“rows”) there. This means that if you check which line you are on, you only need to check the rectangles inside that line. Finally, to choose which row you are in or inside the row, select which rectangle, save the sorted data structure (for example, some search tree).

Thus, your data structure may be something like a search tree for a row, where each node contains a rectangle search tree along the row.

Answer 3

R-tree is suitable for providing such spatial access.

But some questions:

Is your rectangle set to static or dynamic?

How many point queries do you expect from a set of rectangles?

Edit:

Since the set of rectangles is static: There is a method used in traditional graphics with bitmaps (I don’t know if this applies to html5 canvas or not):

Make an additional raster picture the same size as the main picture. Draw each rectangle with the same coordinates, but fill it with a unique color (for example, color = rectangle index). Then check the color under the mouse point => get the index of the rectangle in O (1)