Collision detection algorithm

Question

I have a problem with an algorithm I'm trying to solve, i have a list of points I'm trying to check for collision, I have the general idea probably using some pytagoras, however my main problem is the efficiencie of the algorithm, cause I need to check if to rect intersect only in one axis, lets say I have a rect in point (0,100), and other in point (300, 100), both are in y=100, so for my app I decide they collide, now how I can check if any of the rects collide with any of the rest?

My first attempt was to have a loop the check for each rect I add if the new rect collide with the rest, but I think is wrong, cause if i have 100 rects, i will need to check of the first collide with the other 99, and each of them if they collide with the rest.

I'm pretty sure the loop will increase exponentially wich is bad, so can someone please point me in the right direction of how will be the best efficiencie way of checking, thanks!

EDIT 22-oct-13 using @John Phu Nguyen function

var events = [ {start: 30, end: 150}, {start: 540, end: 600}, {start: 560, end: 620}, {start: 610, end: 670} ];
//each start and end props are y coordinates, basically where the rect start and ends
function layOutDay(events) {
    //console.log(events);

    var events_container = document.querySelector('.events-col');
    var frag = document.createDocumentFragment();
    for(var i=0; i<events.length; i++){
        //console.log(events[i].start);
        var top = events[i].start;
        var bottom = events[i].end-events[i].start;

        var event = createEventDOM();
        var gutter = event.querySelector('.gutter');

        event.style.top = top + 'px';
        event.style.height = gutter.style.height = bottom + 'px';

        if(y_coords.indexOf(top) === -1 && y_coords.indexOf(bottom) === -1){
            y_coords.push(top);
            y_coords.push(bottom);

            y_coords.sort();

            event.style.left = '10px';
            console.log('NO collision', top, bottom);
        }else{
            console.log('collision', top, bottom);
            event.style.width = '250px';
            event.style.left = '220px';
        }

        frag.appendChild(event);
    }

    events_container.appendChild(frag);
}

so running the function I got 2 rects collisioning, but there are 3 not 2, I need to know who is collisioning with who to move the rects next each other in the x axis!

Here is a screenshot of what I'm trying to do

probably is a tweak but I can't found it, any help is much appreciated, thanks!!!

If you have a set of points, then how can they "collide"? Being in the same place seems like the most obvious way for me when I think of a point collision. However, it seems you are drawing rectangles to detect collisions? Can you explain in more depth how a collision is determined in your situation, and what constitutes a collision? — Travis J
– Travis J, Commented Oct 21, 2013 at 17:40
Unless all of the rectangles are moving all of the time, you just need to check those that did move. — Boris B.
– Boris B., Commented Oct 21, 2013 at 17:54
first of all, thanks to all for the reply, I appreciate everybody is taking the time to help!, I will leave some comments of what of those solutions works best for me, but all make totally sense — goseta
– goseta, Commented Oct 21, 2013 at 21:07
Are all the rects at the same y or was it just your example and they can be at any y and have any aria? — taigi tanaka
– taigi tanaka, Commented Oct 22, 2013 at 16:00
yes they can be in any y, basically I need to know who is in the same range of y, I can do this using a for loop, but I want to check each of them is not efficiency — goseta
– goseta, Commented Oct 22, 2013 at 19:50

6502 · Accepted Answer · 2013-10-21 17:50:45Z

2

The loop will not increase exponentially but quadratically, which can be still bad.

There are several solutions, depending for example on how many rectangles are moving and how many of them are fixed.

A solution very simple to code is

build a grid of NxN cells where each cell can contain a list of rectangles touching the cell
loop over the rectangles and for each of them put the rectangle in the list of every cell they touch. While doing so you can also check if the rectangle is colliding with others that are in the same list of a cell.

This grid data structure is very easy to maintain updated when you move a rectangle: simply remove it from the current lists and insert it in the lists of the new position.

What is the optimal N really depends on the application.

answered Oct 21, 2013 at 17:50

6502

115k17 gold badges177 silver badges277 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

John Phu Nguyen · Accepted Answer · 2013-10-22 21:05:43Z

1

If you are just looking to check individual points along axes, a sorted list would work well.

In Javascript:

//Existing points:
var x_coords = [0, 20, 310, 400];
var y_coords = [0, 50, 100, 500];

//New point
x_new = 300;
y_new = 100;

//Check for collision
if(x_cords.indexOf(300) == -1 && y_cords.indexOf(100) == -1) 
{
    //No collision, add to list
    //Add another point
    x_coords.push(300);
    x_coords.push(100);

    //Sort list, complexity should be low if sorted after every insert
    x_coords.sort();
    y_coords.sort();
}

If you are looking for collision within a range,

x_cords.indexOf( 100 )
x_cords.indexOf( 200 )

will give you the index of the values 100 and 200. Anything within that range will occur between those two indices in a sorted list.

Additional information:

'bottom' is currently the element height, not the bottom. The if statement should be:

if(y_coords.indexOf(top) === -1 && y_coords.indexOf(end) === -1)

However, this will still yield nothing because the indexOf() function looks specifically for a value, not if there are values between certain values.

To do this, you can use list comprehension:

elements_between_y100_and_y300 = [i for i in y_cords if (i >= 100 && i <=300)]

If the list returns empty, then there is no collision.

In order to find out which elements collided, you will most likely have to keep a seperate list such as: element_at[200] = 2

edited Oct 22, 2013 at 21:05

answered Oct 21, 2013 at 18:06

John Phu Nguyen

3191 silver badge9 bronze badges

3 Comments

goseta Over a year ago

Hi, thanks for the help, I'm trying to understand this approach, but I have some doubts in this function, please check the edit to my question to see what I got so far, thanks again

John Phu Nguyen Over a year ago

Hi, please see the appendage to the answer under "Additional information:". I'm sorry if the syntax is not completely correct, it's been a while since I've used Javascript

goseta Over a year ago

not a problem, u just gimme a clue, thanks the for help, I think I doing it very similar to what u just mention, so I think this could be the correct answer to my question, thanks! one think, I thought list comprehension is only in python, well anyways still valid thanks!

Collectives™ on Stack Overflow

Collision detection algorithm

2 Answers 2

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related