LÖVE

Wow, that was some explanation!

I'm also impressed.

3.5th solution:
Create the grid, but postprocess it using a Quadtree:
Start with the whole area as the root node of the tree.
Create the nodes recursively:
[*] If the depth of recursion is > N (say 6, experiment on that), stop
[*] If the node covers only one shapre, stop
[*] if the node covers more than one shape, divide into four equally sized rectangles an recurse

This will reduce the amount of required memory to store the pixel->shape association and will still be fast.

vrld wrote:I think Shape:testPoint will do exactly the same: Test if the point is right of every edge in the polygon.

Anyway, for understanding the right-of-test: [...]

Whoa! Thanks for that explanation. I'm going to have to process this for some time before I can even begin to understand it.

Anyway, I went with the Shape:testPoint solution, and it's working great! Thanks for all the help, everyone!

pekka wrote: First of all, making a grid that divides the space is actually a good solution. But you need to have some fancier logic to get the hit testing be pixel perfect inside the grid sections, or at leat reasonably close to pixel perfect anyway. I'll describe that a bit.

vrld wrote: The search [in trapezoidal maps] is performed in O(logn) time, which for a large number of edges will be considerably faster than pekka's solution.

The grid approach is way easier to implement and will even be faster than trapezoidal maps, but it will also require a lot more memory.

I would just like to point out that "my solution" did in fact include the possibility of using a grid, as it says right on the top of my message. I would also appreciate it if you differentiated between the terms asymptotically faster and measurably faster in your future messages. (The latter term can be used after you have taken measurements of how actual working code performs.)

You see, my religion forbids me from believing in other forms of faster.

I did not want to step on your toe, but as my religion forbids to think there is a great difference in the two types of fast (I do not believe in cache effects and other such blasphemous notions of actual physical machines):
A O(logn) solution is measurably faster than a O(n) solution. Additionally, computing intersections between line segments would be slower than walking down a tree, or am I missing something?

Anyway, a fourth (kind of hackish) take on the problem:
As you already have to have your map in memory, you can use it to determine the clicked shape.
Color each shape different. The difference can be very slight, say from #fea104 to #fea103, as the eye won't see it, but the computer will when using ImageData:getPixel to lookup the color of the pixel below the mouse. This is much simpler and also measurably faster than using any other method I suggested.

I wouldn't consider that method a hack. It's actually quite common. If you don't want to color the displayed image you could use a second image to map mouse clicks to areas.

This method also makes it real easy to create new maps or edit existing ones.

I'm happy to report that I now comprehend vrld's method. It only took me 4 months to figure out.

Go me!