I am having a for loop with 100,000 iteration - each iteration involving a simple distance calculation of some objects' position. This is all part of a sophisticated collision detection mechanism.
Now too many unnecessary iterations are not efficient and slows down the program. I would like to decrease the calculation time by using sorted vectors.
Therefore alternatively I thought of decreasing the iterations to a minimum by inserting referenced elements into a 2D vector which sorts the positions according to a "grid". Instead of 100,000 iterations, I would only have perhaps 1000 iterations with the same calculation, but involving now only particular "sector". However, the downside is perhaps that the 2D vector needs to be regularly updated with the objects grid or sector position by using push_back and erase, whenever an object changes its position.
My question regards the performance and not the code. Is updating a vectors by using erase and push_back quicker than using a brute force attempt of iteration? I need just a rough estimate if it is worth while pursuing this idea. Thanks.
What you are looking for is binary space partitioning. This way for any given object, finding one colliding object is O(log N), where N is the number of objects. This should cut your collision detection cost from O(N2) to O(N log N).