🔒 Locked

Does anyone know how to prove this algorithm for Collision Detection

Started by legionalways Dec 20, 2011 at 7:51 AM 8 replies 2.6k views

Original Post

Dec 20, 2011 at 7:51 AM

There are two convex polygons(A and B) on a 2-D plane, each with M and N edges.
To test whether the two polygons collide, do as what follows:

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.

Project polygon A onto this vector, using dot product to get the projection range ,lets say (minA, maxA)
For polygon B ,you get (minB, maxB)

Now you test whether the two ranges intersect.

[color="#ff0000"]Edited:
[color="#ff0000"]IF in one test , you find that the two projections don't overlap, you know there is a separating axis and polygon A and B don't collide.
[color="#ff0000"]IF you go through all the tests, and the projections always intersect, then polygon A and B overlap.

So my Question is : How can I get the Mathematical proof?

Ashaman73

Dec 20, 2011 at 8:00 AM

There are two convex polygons(A and B) on a 2-D plane, each with M and N edges.
To test whether the two polygons collide, do as what follows:

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.

Project polygon A onto this vector, using dot product to get the projection range ,lets say (minA, maxA)
For polygon B ,you get (minB, maxB)

Now you test whether the two ranges intersect.

So there will be M+N tests. If in one test, you find that the two ranges intersect, you know that polyon A and B collides .

if you go through all the tests but don't find two intersected ranges,it's sure that polygon A and B does not collide.

So my Question is : How can I get the Mathematical proof?

Why do you need a proof other than for homework ?

legionalways

Dec 20, 2011 at 8:04 AM

I am just curious...

jjd

Dec 20, 2011 at 11:33 AM

There are two convex polygons(A and B) on a 2-D plane, each with M and N edges.
To test whether the two polygons collide, do as what follows:

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.

Project polygon A onto this vector, using dot product to get the projection range ,lets say (minA, maxA)
For polygon B ,you get (minB, maxB)

Now you test whether the two ranges intersect.

So there will be M+N tests. If in one test, you find that the two ranges intersect, you know that polyon A and B collides .

if you go through all the tests but don't find two intersected ranges,it's sure that polygon A and B does not collide.

So my Question is : How can I get the Mathematical proof?

I don't think you'll find a proof because this technique does not work. (hint: try to think of an example where the projections overlap but the polygons do not intersect).

Note, if you're trying to describe a separating axis approach this is not it and your description is confusing/wrong.

-Josh

japro

Dec 20, 2011 at 1:36 PM

So there will be M+N tests. If in one test, you find that the two ranges intersect, you know that polyon A and B collides .

if you go through all the tests but don't find two intersected ranges,it's sure that polygon A and B does not collide.

These are wrong. You can conclude the polygons dont intersect as soon as you find one edge for which the polygons don't intersect (that is the "separating axis"). They do intersect if the ranges intersect for ALL edges.

The proof would be something along the lines that you consider the projection along axis S a function proj_s(x). Now for two sets A and B if proj_s(A) and proj_s(B) are disjoint then the preimages A* and B* cannot intersect either and since A subset A* and B subset B* it follows A and B are also disjoint. Now the proof that you can conclude they do intersect if you check all edges is a different story (which means, I don't know the proof off the top of my head)

legionalways

Dec 21, 2011 at 1:06 AM

[quote name='legionalways' timestamp='1324367518' post='4895621']

jjd

Dec 21, 2011 at 1:57 AM

Yeah, I put it wrong. I have corrected it. What about now?

Yes, it is a bit better now, although if you want a proof of the separating axis theorem it would be simpler to just state that. As for how to prove it, japro has suggested an approach you could try. Failing that the wikipedia article on the SAT is also pretty suggestive.

-Josh

legionalways

Dec 21, 2011 at 2:35 AM

I LIKE YOU GUYS' POSTS AND HAVE RATED THEM

quasar3d

Dec 21, 2011 at 9:51 AM

[s][color="#1C2837"]

[color="#1C2837"]

For an arbitrary edge of one of the polygons, find a vector which is perpendicular to the edge.

[color="#1C2837"]

[/quote]

[color="#1C2837"]

Do you mean any vector that's perpendicular to the edge? Then your algorithm is still wrong. After all, the normal of a polygon is also perpendicular to all of its edge, and so it should be enough to just do two tests: one with the normal of your first polygon, and one with the normal of your second polygon.

[color="#1C2837"]

[/s][color="#1C2837"]

[s]Clearly this doesn't work though, since it's not so hard to think of two non intersection polygons, whose projections onto the subspace generated by their normals gives two intersecting lines.[/s]

Ignore this. I thought you were talking about 3D.

Christer Ericson

Dec 30, 2011 at 5:32 AM

So my Question is : How can I get the Mathematical proof?

You prove the separating axis test by a) looking at how many ways the two convex objects can come into contact, and then b) making sure you have tested for separating for all those possibilities. If, after you have performed all those tests, you have not found the objects separated, you must conclude they are intersecting.

For two convex polygons in 2D, you will find that the polygons can come into contact with their vertices and along their edges, and that it is sufficient to test separation with planes that are parallel to the edges of the polygons (or, equivalently, along axes that are parallel with the edge normals). This means you perform at most M + N separating axis tests for a 2D intersection test of a convex M-gon and a convex N-gon.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.