algorithm - O(1) to check if mouse hovering one of array of circles

Question

generally to check if mouse move event x and y is intercepting any polygon inside array of polygons is:

on mousemove (e)->
  for c in circles
     if intercept(e.x, e.y, c)
        ...

just wondering if i can check it without for loop, like:

on mousemove (e)->
  i = calidx(e.x, e.y)
  if intercept(e.x, e.y, circles[i])

seems every mousemove event loop through all array items is not efficient

is it possible to use O(1) complexity to find out which array item is hovering?

Answer 1

Using lookup table makes it amortized O(1) (but painful to setup/update)

One way to do it with amortized O(1) is using a table lookup. This means you'll need to store each pixel coordinate with the circle ID it belongs to like this:

pixel(0,0) --> no circle

pixel(0,1) --> circle#1

pixel(0,2) --> circle#1,circle#2

...

So you can quickly lookup the table with a particular pixel coordinate and retrieve the circles it belongs to. This lookup can be done with amortized O(1).

However, it's a pain in the ass to set the table up / or update it

The algorithm to set the lookup table is painful, highly complex. You'll need to populate all pixel coordinates of each of the circles you have and make the complete table. This is highly complex and updating the new position of the existing circles is even worse. It takes some computation to update the lookup table.

The approach is affordable when:

• Your circles are static. After you setup circles, they won't move or get resized.
• You have a small canvas.

In contrast, this is evil and worse when:

• Your circles are dynamic. They keep moving, resizing, added or removed all the time. This costs the updating phase a grave overhead.
• You have a large canvas.