Thread: Collision Test - 2D

So, the counterclockwise function tells whether points A, B, and C are in counterclockwise order. IE, if you graphed the XY coordinates of times on a lock, the points found at 11, 5, and 3 would be counterclockwise, while the points found at 11, 3, and 5 would not.

Based off the ordering of points relative to eachother, you can tell if lines intersect.

To be honest, I found this algorithm on a mailing list posting or something years ago, and haven't thought about it too much since (aside from the fact that it works). It kind of hurts my brain a little.

> If the asteroid is within the box, then it does circle collision test.
If you're going for the full accuracy test as well, then I'd think I'd skip the circle test.

The amount of space which is inside the bounding box isn't going to be that great. The amount of space which is inside the circle, but outside the polygon is going to be even less.

Hmm, Thanks Norman, I'll work on it.

Originally Posted by Salem

> If the asteroid is within the box, then it does circle collision test.
If you're going for the full accuracy test as well, then I'd think I'd skip the circle test.

The amount of space which is inside the bounding box isn't going to be that great. The amount of space which is inside the circle, but outside the polygon is going to be even less.

Yeah, the point of that was to avoid the distance formula as much as possible. Now though, I'm thinking maybe just do the box, then if the asteroid is within the box do line by line. No circle test at all. That's what you were thinking, right?

EDIT: Didn't see the line directly under the quote =P. Thanks though

> Why omit the circle test and not omit the box test?
For roughly the same amount of geometric space, the box test is far more efficient (each comparison eliminates ~25% of possible objects). After just 4 comparisons, there isn't much left to deal with.

Besides, if your box is rectangular, there's no difference in performance, but if you were to implement a true elliptical test, then that gets much more interesting in a hurry.

> in which you do 8 additions/subtractions, 4 comparisions, and 3 logical operations.
In any reasonable implementation, the bounding box of the ship would be calculated just once.

Plus, as you should know, the logical operations will short-circuit, so there is less than 4 compares and 3 logical ops per test on average.

Since you can re-use the bounding box of an asteroid to work out say whether to bother drawing it at all, even that may be a freebie as well, in which case the amount of work boils down to a couple of compares on average.

So you also think that circle test is quicker.
>> A box normally can contain the object much better than a circle.
But this guy is testing collisions between asteroids and a triangle, and circles are more accurate for that, if you look at his program.

Originally Posted by Salem

In any reasonable implementation, the bounding box of the ship would be calculated just once.

As the x and y change every frame, the bounding box must also be recalculated, as the above code does.
Also, those asteroids are closer to circles than to rectangles.

Originally Posted by Salem

Plus, as you should know, the logical operations will short-circuit, so there is less than 4 compares and 3 logical ops per test on average.

Sorry, I never heard about this.

Edit: I think I know what you mean, I just didn't recognize the word "short-circuit".