What is an efficient algorithm for determining when the mouse pointer is within certain bounds?

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.

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.

1 Like

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 :slightly_smiling_face:

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:

1 Like

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.

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

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.