Computational Geometry: Algorithms and Applications

Author: Mark de Berg
This Month Stack Overflow 1


by anonymous   2017-08-20

I would create a Sprite per Scene and add the belonging Object to them. So the display list could look like this:


and so on. This way you just need to toggle the current scenes' visibility. But as I see, you are sorting the objects based on intersection with a »scene rect« and that is costly process if you have that many Objects to check. If you cannot add a data structure to associate Objects to Scenes, than you can try to cache the result and run the search only if something changes…

Last but not least you could implement an improved searching algorithm based on space partition, so that you decrease the number of intersection test as much as possible. But that depends on strongly on your application, if everything is moving a lot and you need to update the partition tree very often, that might not be an improvement.


One possible algorithm for an efficient lookup of the objects in an area could be orthogonal range searching. An explanation would go too far here and is not the subject of the question.

A book including a nice description is this and a result of a quick and dirty googling is here.

The algorithm is based in a binary tree which contains the coordinates of the objects. If the objects do not move that is perfect for your application, because then the tree just needs to be initialized once and following range queries are quite fast. To be exact, their speed depends on the size of the area to query. So the improvement will be bigger, the smaller the size of the queried area is compared to the size of the overall world.

Good luck!


I once had a similar thing to handle, that was one dimensional (x-axis only), but as far as I know, it should not be too complicated to make this work in two dimensions (Got that from the book, linked above). You can have a look at the question here.