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\$

1 Answer 1

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\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .