What is an efficient algorithm for determining when the mouse pointer is within certain bounds? (original) (raw)

Hi all,

So I have this matplotlib/tkinter program that plots the moving average convergence/divergence of bitcoin closing prices for every day in 2023, as well as the closing prices themselves. The user can click and drag any vertex on the closing prices line to manipulate the value for the corresponding day/period, and for each change the program recalculates the MACD values for that period, and any subsequent periods.

currently each vertex has a small, circular, yellow marker with a red outline attached to it. Ideally when the mouse cursor is rolled over a marker, it should expand in size somewhat. The problem as I see it is that there are 365 markers, and checking whether the mouse is over one in response to every mouse movement event seems pretty inefficient.

The only thing I could think of (this is back of envelope stuff) is for the first mouse motion event, check how many pixels in distance there is to the nearest marker(s). Then, after that number of motion events, check whether the cursor is inside that marker (or one of those markers), if not, repeat the process - ad infinitum. This would only work if an event is reliably generated for each pixel the mouse moves, I have no idea if this is the case.

Anyway, does anyone have any ideas, input, or is there a standard way of doing this? Any help is appreciated as always.

Rosuav (Chris Angelico) March 12, 2024, 9:50pm 2

There are a lot of strategies for optimizing this, but the first question is: How costly IS it? Try implementing the naive search: for every marker, test whether x1 <= mousex <= x2 and y1 <= mousey <= y2, and see how long it actually takes to calculate this.

My strategy for testing this, actually, would be independent of the GUI itself. Write your naive code, wrap it up in a function, and then use the timeit module to try calling it repeatedly. That’ll give you a time (in milliseconds or nanoseconds or thereabouts) per iteration. The reciprocal of that is the number of mouse motion events you can process every second. Is that a reasonable limit? For a somewhat extreme example, if you find out that it takes 25 nanoseconds to calculate whether the mouse is over any marker, you can do forty million of those checks every second, and that’d tell you that there’s no need to optimize whatsoever. Or for an example at the other extreme, if it takes 250 milliseconds per iteration, you can only do four checks per second, which would mean your app would feel sluggish and non-responsive.

Once you figure that part out, then it’s time to think about what - if any - optimization to do. One option that comes to my mind is binary space partitioning, or perhaps a modified form of it. It’s cheap to traverse, although it can be expensive to update for mobile nodes, so maybe it’d be best to tweak the algorithm a bit in favour of that. But first, the question of need.

Thanks! I’ll try it out using timeit and see how it goes. This PC is well provisioned so it runs fine for me, but I’m always conscious I might be writing hot garbage that would clog up a more modest machine. Also I find the idea of it being efficient more pleasing so I’ll look into BSP 🙂

Rosuav (Chris Angelico) March 13, 2024, 2:00am 4

That’s always a good way to think :slight_smile: Hopefully timeit will be informative even on a hot system. If not, you can always take your code and run it on a borrowed potato, just to get that sense of scale.

Now now, be honest… isn’t it more that you find the idea of implementing BSP to be really cool and fun, and therefore you’ll look into it? :smiley: Which it is. It’s a neat way to achieve a binary search based on arbitrary shapes in space. And it’s so important that video game engines since Quake have used it as a fundamental part of the map format - games built on the Quake or Source engines use files called de_dust2.bsp because they’re a gigantic binary space partitioning structure.

And if that’s not enough reason to want to implement something, I don’t know what is :smiley:

TeamSpen210 (Spencer Brown) March 13, 2024, 6:06am 5

For this sort of situation where you’re adding/removing elements, a quadtree might be a better approach. There’s algorithms for those that can handle both adding/removing elements, adjusting the tree structure to remain mostly balanced.

Alternatively, are the circles elements of a Tk canvas? If so it looks like you can use the find method to have Tk do the search. It’ll probably be just looping over them, but the code will be written in C so it should be quite fast.

Rosuav (Chris Angelico) March 13, 2024, 7:04am 6

By the way, here for perspective is something I wrote in JavaScript a while ago with the exact same problem.

https://sikorsky.rosuav.com/channels/demo/commands#hypetrain/graphical
Source: StilleBot/httpstatic/command_gui.js at 54a2cc06f6c46ae9b1d12e42d2fbbf506bb176fb · Rosuav/StilleBot · GitHub

As you can see from the TODO, I had the same thought. This is both simpler than your situation, and more complex; simpler in that there usually won’t be more than a few dozen items to pick from, but more complex as the elements aren’t simple rectangles. And every mouse move, it scans to see whether the cursor’s over an element (even if you aren’t currently dragging - some elements signal a change of pointer).

That code’s been there for a year, running in people’s web browsers, and it hasn’t been laggy. So unfortunately for the coolness of implementing more elaborate data structures, this probably isn’t enough to justify it.

@Rosuav I’m so sorry that I never came back to you on this! Judging by the date, it was around the time I had to move out of my house to make way for some extensive building work; typically these kind of disruptions precipitate my disengagement with the online world :smiling_face_with_tear:

Anyway, it’s probably not a bad thing as my DSA knowledge has come on a bit since I was last here so I’m more prepared for the task. I don’t actually know why I didn’t mention it before (perhaps it came later) but my naive solution ended up treating the distance from the mouse cursor to the centre of a vertex as the hypotenuse of a right angled triangle.

Knowing the cursor X/Y and the X/Y of the vertex centre meant I could compute length of the adjacent/opposite sides and then use the Pythagorean theorem to work out the length of the hypotenuse, which happens to be the distance to the vertex centre. If that distance was less than the vertex marker radius, the mouse cursor was ‘in’.

At the time I was quite proud of it, but in the grand scheme it’s still pretty rubbish. I was still iterating over all the marker coordinates after all. Given what I now know, I should at least have implemented some sort of binary search in order to quickly identify the coordinates of vertices that were actually close to the current mouse position :open_mouth:

Anyway, as a challenge I’ll see if I can cobble something together and also look into BSP. Then I’ll time them both and report back!

Rosuav (Chris Angelico) May 5, 2025, 1:27pm 8

Pythagorean distance and a numeric threshold. Simple and effective.

You could, if it’s a problem. One good trick to use is to first hit-test against a square, and then if it’s within that, test the circle. (More generally, hit-test against an Axis-Aligned Bounding Box, which can be done in three dimensions too.) Say you want a radius of 10px - if the cursor’s closer than 10px, it’s a hit. Well, if the X coordinate is more than 10px away from the cursor, there’s no way that it’s within the circle, so you can move on to the next one! Same with the Y coordinate. So your code would look something like this (pseudocode):

mousex, mousey = mouse_position()
radius = 10
distance_squared = radius ** 2
for x, y in markers:
     if (mousex < x - 10 or mousey > x + 10
        or mousey < y - 10 or mousey > y + 10):
            continue
    d2 = (mousex - x) ** 2 + (mousey - y) ** 2
    if d2 <= distance_squared:
        print("You're over this marker!")

Note that there’s another VERY common trick that I’ve used here: define your distances in square units. Pythagorean distance is defined to be the square root of the sum of the coordinate differences, but in order to determine whether you’re inside or outside a predetermined radius, keeping it squared works beautifully. The mathematics will be equivalent (inequalities on the squares of distances will be equivalent to inequalities on the distances themselves), and the square root operation is a slow one. Combining these two techniques, you have a fairly efficient search that only slows down for the ones that it’s actually close to.