4 ms·
The second algorithm you are thinking of is probably what is known as "sort-and-sweep". Basically each object takes up an interval along each axis, so a necessa
by dharmon 6y ago
The second algorithm you are thinking of is probably what is known as "sort-and-sweep". Basically each object takes up an interval along each axis, so a necessary condition for collisions between two objects is that the intersection of the intervals along each axis are non-empty. (which means if there is no overlap of intervals along any axis, you can guarantee they are not colliding).
You compute the bounds along each axis in linear time. The sorting of these bounds can be done in linear time, then you take a pass over each axis looking at the marked intervals, which is also linear.
- jansan 6y agoI agree, that sounds a lot like "sort-and-sweep" or "sweep-and-prune" (I prefer the first name). This is an awesome algorithm and really simple. I once reimplemented an algorithm with sort and sweep to improve performance of a certain test case that took 45 seconds to compute. With sort-and-sweep it only needed about 100ms.