Best approach to get clicked objects from a display list (2D)

Question

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.

Answer 1

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:

• How to continuously find all entities within a radius efficiently?

• Documentation on 2D space partitioning

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.