What does the algorithm for finding the intersection of 1000 objects look like?

Question

JavaScript

How to handle the intersection check of 100-1000 objects (circles in my case).
There is an area on which circles randomly appear and move in all directions, then crash, how to check the intersections of these circles. And it turned out that I do O (n ^ 2) check operations, every 1 second.
We need an efficient algorithm. Or at least in words, the procedure.
I read about the method of dividing planes but did not understand how the projection plane is located there.

Answer 1

There was the same problem in the game there were a lot of ships and shells. And it was necessary to find all the intersections of the shells with all the ships. The algorithm with a simple enumeration was terribly slow. Therefore, we did this:
Divide the space into virtual squares with size size
To do this, we create a map and for each circle we look for its key .

key = Math.floor(circle.x / size) + "_" + Math.floor(circle.y / size)
if(!map[key]) map[key] = [];
map[key].push(circle);

Next, we simply iterate over the keys of the map and check the intersections of the circles inside the square. It turns out that there are much fewer checks due to the grouping of circles into squares.
You can also optimize the check for circle intersections. For a circle, we need to know its radius.

function isCollided(circle0, circle1)
{
      var maxDistanceSquared = circle0.radius + circle1.radius;
      maxDistanceSquared *= maxDistanceSquared;
      
      var dx = circle0.x - circle1.x;
      var dy = circle0.y - circle1.y;
      
      var currentDistanceSquared = dx * dx + dy * dy;
      
      return currentDistanceSquared < maxDistanceSquared;
}

Answer 2

There are actually a lot of options.
But I will suggest this. Divide the plane where they move into squares. The size of the square is equal to the radius of the largest circle (well, or with a margin, as you wish). And then it is enough for you to check not the intersections of all with all, but the intersection of each with the circles that are in this and in neighboring squares.
Naturally, you need to update the contents of the squares every step, but this is not the most expensive operation.
Well, to check intersections, use not distance, but squares of distances / radii - it will be faster (although it will not affect the complexity of the algorithm)

Answer 3

Option 1:
It is necessary that each circle checks its own state and informs the listener.
As soon as a circle is created, hang a collision event handler on it.
Watch the centers of all circles to control the collision.
Collision (tangency): when the distance between two circle centers is equal to the sum of the radii of the circles around those centers. And, accordingly, check for intersection: the distance is less than or equal.
Check - iterative:
1. After the first check - sort all pairs of centers with gaps between the circles from the closest to the farthest.
2. At the second - we check, starting with the closest one and immediately calculate the speed and displacement vector. Now, add speed: sort from maximum speed with minimum gap to minimum speed with maximum gap.
3. In the subsequent steps, we use the information from the previous step to determine the threshold for the "tail clipping" zone when checking against the sorted list: threshold.
That is, if we see that the acceleration or linear speed for a given time will not allow them to intersect on this frame, then we simply do not check them and put a label: after how many iterations we will check each of them (reserve them for elimination on several subsequent iterative checks).
Thus, we save "empty" cycles when calculating collisions.

Answer 4

Have a look at the r-tree/r-tree++ algorithms, but I'm not entirely sure what that would be in terms of speed. There is an implementation for Java in mvstore, I just use it, but I mostly have statics and millions of objects. You probably need to build a tree for all movements www.h2database.com/html/mvstore.html
And yet, only in memory https://github.com/davidmoten/rtree
https://github.com/conversant/rtree

Answer 5

https://github.com/w8r/martinez
turfjs.org/docs#intersect
https://github.com/Turfjs/turf/tree/master/package...

Answer 6

Quadtree