CODEWITHSUNDEEP
algorithmdata-structures
garima
garima

Reputation: 5244

Datastructure and algorithm to detect collisions of irregular shaped moving objects

I came across this interview question

Many irregularly shaped objects are moving in random directions. Provide a data structure and algorithm to detect collisions. Remember that the number of objects is in the millions.

I am assuming that every object would have an x and y coordinate. Other assumptions are most welcome. Also a certain kind of tree should be used, I suppose, but I am clueless about the algorithm.

Any suggestions?

Upvotes: 10

Views: 1277

Answers (4)

Cybercartel
Cybercartel

Reputation: 12582

Most likely what you want is to sub-divide the plane with a space-filling-curve like a z-curve or a hilbert-curve and thus reducing the complexity of a 2D problem to a 1D problem. Look for quadtree.

Link: http://dmytry.com/texts/collision_detection_using_z_order_curve_aka_Morton_order.html

Upvotes: 2

knivil
knivil

Reputation: 906

There are many solutions to this problem. First: Use bounding boxes or circles (balls in 3D). If the bounding boxes do not intersect then no further tests are needed. Second: Subdivide your space. You do not have to test every object against all other objects (that is O(n^2)). You can have an average complexity of O(n) with quadtrees.

Upvotes: 1

Hiren
Hiren

Reputation: 341

I guess there should be a loop which takes reference of 1 object find co-ordinates and then checks with rest of all other objects to see if there is any collision. I am not sure how good my solution is for millions of objects. Psuedo-code:

For each irregular shaped object1    

int left1, left2;
int right1, right2;
int top1, top2;
int bottom1, bottom2;
bool bRet = 1; // No collision

left1 = object1->x;
right1 = object1->x + object1->width;
top1 = object1->y;
bottom1 = object1->y + object1->height;

For each irregular shaped object2
{
    left2 = object2->x;
    right2 = object2->x + object2->width;
    top2 = object2->y;
    bottom2 = object2->y + object2->height;

    if (bottom1 < top2) bRet =0;
    if (top1 > bottom2) bRet = 0;

    if (right1 < left2) bRet = 0;
    if (left1 > right2) bRet = 0;
}

return  bRet;

Upvotes: -2

Nico Huysamen
Nico Huysamen

Reputation: 10417

I would have a look at the Plane Sweep Algorithm or the Bently-Ottmann Algorithm. It uses plane sweep to determine in O(n log(n)) time (and O(n) space) the intersection of lines on a euclidian plane.

Upvotes: 3

Related Questions