How to quickly find a group of objects in an array that fall into the selected zone by coordinates Left-Top-Right-Bottom?

Question

C++ / C#

There is an array of classes, each of which is an object on the plane.
All objects are rectangles. In addition to XY coordinates and WH height-width, classes can return LTRB side coordinates. An array can contain from 3000 to 40000 or more objects in total.
Task: organize a quick search for a group of elements that fall into the zone according to the Left-Top-Right-Bottom coordinates, which is necessary for collision detection and selection of elements for rendering.

• Many objects are static, but some of them can move freely (usually 400 to 10000, but can be more).
• Sometimes movement of static objects is also possible:
  
  • if their group is "attached" to a dynamic object (full repetition of its movements)
  • linear movement with given X/Y speeds.

By default, the elements in the array are randomly placed, but if necessary, I can easily sort them all by XY coordinates

Answer 1

Finding collisions quickly is not a trivial task. But, fortunately, it has already been studied.
gamedevelopment.tutsplus.com/tutorials/quick-tip-u...
en.wikipedia.org/wiki/Quadtree
en.wikipedia.org/wiki/Collision_detection
www.java-gaming.org/index.php?topic=29244.0
staticvoidgames .com/tutorials/intermediateConcepts...
Depending on the behavior of your objects, it's possible to come up with something more efficient (more narrow-minded). Usually this is either tracking in the area of ​​​​a single point, or caching the results.

Answer 2

I usually use the grid to optimize the search. Simple and effective.
That is, build a two-dimensional array, each element of which contains a list of all objects that fall into this cell.
When an object is moved, its position in the grid must also be updated.
Accordingly, for the search, it is enough to check all the cells in which the object falls, collect a list of potential candidates for the intersection and check each of them.
If the space is strongly non-homogeneous (that is, there are many heaps of objects broken far away), then the regular grid becomes very inefficient in terms of memory consumption, then it is better to build a sort tree (kd, Quad, Binary).