Collision Check Algorithm - Seeing if two objects are overlapping

I have been looking around for a bit, and have not been able to find a solution to my problem. I was hoping someone here might know an algorithm for checking if two objects are overlapping.

For example, I have two objects, each with an image. The objects have an x and y, but they have more than just a width and height - they have a shape. I'm not talking about rectangular collision, but actual (reasonably) precise measurements that don't take a huge amount of load or run-time processing.

The best possible solution I could come up with would be to draw a blank object (off-screen, mind you), draw both objects, count up the number of background pixels remaining, and compare that with the total number of background pixels minus the sum of the number of pixels in the two objects.
That should give you an idea of what I am looking for. This method would be faster than some other methods I could think of, but I'm sure there must be a better way. I have seen many programs with something like this, and I would like to know how it could be done in a practical way.

 

 

 

Comment/Reply (w/o sign-up)

Check if any of the points of one object are inside of the other object, if so, you are definitely overlapping.

Check if any of the edges of one object cut across any of the edges/points of the other object. This is a little more difficult. Here are the steps of what you need to do for each edge:
Find the equation for the edge
Plug in the x coordinate in to the equation, then the y coordinate (basically find the points on the line that are on the same plane as the point in question). Figure out which side of the line the point in question is. If the point is "inside" of the object, there is overlap, if not, there is no overlap. Do this with every relevant point (you should be able to figure out which points are relevant depending on the type of shape).
Get the next edge, and repeat.

If your object could be a circle, you can do similar things, but you will only have one edge. Circles have no points, so comparing two circles is a bit challenging. You need to use some calculus-type equations to find the intercepts of the circles. If they have more than one intercept, then there is overlap, otherwise, it is just touching (which isn't technically overlapping) or isn't touching at all. The equations themselves aren't all that difficult, but may be a bit difficult to program. You should split the circles into 4 sections and then find the equations for those sections, and then compare the each equation and if they have any overlaps, then you have two overlapping circles. This is a bit difficult. I haven't done calculus for a while, so I can't supply you with anything useful.

I hope this helps you!!

 

 

 

Comment/Reply (w/o sign-up)

Thanks for the reply.

This seems to be pretty effective. The only thing is that I was speaking of a raster object, not a vector one. I could see though how this could be used anyway (either make vector objects instead of raster or generate a vector from the raster). This would certainly be faster than my solution, because the main thing is calculation instead of iteration, and computers tend to do calculation faster.

Comment/Reply (w/o sign-up)