Menu
I have an image, and I want to show tooltips when mouse moves over certain rectangular areas. The rectangular areas can be up to 1000. However, just checking each rectangle if the point is in it, which is O(N), makes the interface unresponsive when moving the mouse.
Is there a way to do it in less than O(N)? I can sort the rectangles beforehand (I'm assuming it would be needed). The rectangles might be (very rarely) overlapping, but no more than 4-5 rectangles can overlap the same area. In that case I might need to get a list of all the rectangles, but even just any of them would still be good enough.
But I'm assuming that this problem has already been solved by window managers, etc.
460
Approach: If we observe carefully, It will be clear that for a point to be lie inside the rectangle, it should be lie inside the x-coordinate (x1, x2) of the rectangle as well as it should also lie inside the y-coordinate (y1, y2) of the rectangle.
We basically add areas of two rectangles. This includes the intersecting part twice, so we subtract the area of intersecting part. Similarly, we can compute area of 2nd rectangle. If the x_distance or y_distance is negative, then the two rectangles do not intersect.
The two given rectangles won't overlap if either of the below conditions is true: One of the two rectangles is above the top edge of the other rectangle. One of the two rectangles is on the left side of the left edge of the other rectangle.
It sounds like you want to be storing your rectangles within an R-Tree and then querying that. There are a few implementations available:
Check out their STRtree classes.
137
A faster and simpler (though less memory efficient) method than a tree for images (and web pages that can be rendered onto reasonably small images) is to use a stencil. i.e. if you have an image of x by y pixels, create a two dimensional array of size x by y and populate it with your tool tip IDs. This has a search speed from pixel position to ID of O(1) (my favourite O)
38
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
