4
\$\begingroup\$

I'm implementing a display list to manage my visuals on screen.

I want to know which object is clicked.

My objects already have z-order variable.

With my current knowledge (almost nothing) the only thing which comes to my mind is make a linear search and get all the objects which contains the clicked point. And then select the object with the highest z-order. But I know there are far better approaches.

I think it's something with trees (binary search?). - container display objects and search recursively?

just don't know where to start looking, for this concrete case. Any hint link or concrete solution is welcome.

\$\endgroup\$
4
\$\begingroup\$

You're on the right track. The thing you're looking for is a space partitioning data structure. For a 2D system I'd go ether with a quadtree (if object sizes vary a lot) or a simple grid (if object sizes are similar). I've already written two answers on the subject, so instead of repeating myself I'll just link you to them:

On the other hand you should consider if this is really needed based on the amount of objects you expect to be added to the display list. I pondered the same in my own project and in the end deemed it unnecessary and used the linear approach instead. It's been more than enough for me.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.