How to keep track of thousands of painted shapes in Windows C++ CLR

I want to have potentially thousands of painted shapes on a panel and be able to identify them when I mouseover or click on them. What is the best way to do this?

My guess is I have to have开发者_JAVA百科 some shape regions in a table. And have some clever way of looking up matches when I hover across page. Seems computationally intensive. Are there methods out there that can help?

When you paint into your panel, also paint the shapes into a bitmap that isn't displayed and use the shape ID as the color. When you need to look up a shape, just check the pixel at the appropriate coordinates in your bitmap. Make sure you turn off any line smoothing or antialiasing when drawing the bitmap!

What you want is something like a Quad Tree or Binary Space Partitioning(BSP).

Quad Tree is fairly simple. BSP's are insanely fast, but do not handle moving shapes and are difficult to build.

A Spatial Hash is really easy to code and builds itself at runtime. Its primary disadvantage is its worse case look up time degenerates O(n) (if most of the shapes in horizontal or vertical line).

Box2D uses it own breed of space partitioning. I'm not really sure what the underlying algorithm is and whether it's novel or derived. But Erin wrote Box2D's broadphase so that it can be used outside of the physics engine. The code is zlib licenced, so you can just copy out the few files you need.