Check if the mouse is over a circle - Java

Question

I have an array with the coordinates of the center of small circles which have the same radius. I know how to find when the mouse is over a circle, but my array is big and I want the fastest way to calculate this operation.

Is there a way of finding if the mouse is over a circle without looping all the array for each movement of the mouse?

Answer 1

What if you check the coordinates that are r(radius) distance from the mouse? Then you could narrow your search down in the array if it is ordered.

Answer 2

Initially, set up some 'zones' for quicker reference:

• Separate the whole surface into a small number of rectangles that don't intersect.
• For each of these rectangles, list all circles that are at least partially contained in it. (A circle may end up listed in multiple rectangles, but that's okay.)

Every time you want to check whether the mouse is over a circle, you won't have to go through the whole array of circles. Instead:

• Figure out which rectangle you're in.
• Check only the circles that are listed under that rectangle.

Answer 3

This looks like a problem of optimizing the boundary check for a large number of items. The approach of going linearly does not scale well for thousands of circles.

This is a good topic to read on the net. But first, without going there, I'll try to explain (as an exercise) what I would explore. I would create a binary tree and partition the space, then instead of using an array I would put the circle points in such a tree. Looking the tree elements that are closer to the actual X,Y location becomes a matter of doing a binary search on the tree. The you have the closest point as a result of that search and can check for collision on it. There is still more to be done to the algorithm, and further optimizations are needed. For example, how to check for more points and not only the final one? Potentially I need a tree for the X coordinate, and another for the Y coordinate, etc... But I would explore these ideas. I will come back to this post and expand my reply with an actual example and a more concrete solution.