1
\$\begingroup\$

A while ago I was considering my possibilities for implementing collisions between 2D shapes, and after much googling (which mostly turned up SAT), I came up with this:

let A, B = two shapes
let V = Speed of A relative to B

for a:point in vertices of A
  for b:segment in segments of B
    if segment(a, a+V) intersects b
      return intersection point
return false

Now, I'm far from the smartest person out there, so I am 99.8% sure someone must have come up with that before me and, what's more important, since I didn't find anything describing this method, I assume it's a bad one.

Can anybody identify this algorithm and/or point me towards any literature on it explaining if, when and why it should be used?

I've failed to see any significant problems at first sight; all the complex calculations can be hoisted outside of the loops and then it's just matrix multiplications within both loops, and I couldn't find any algorithm that makes do without any nested loops over two sets of elements (be they vertices, segments or normals)

Feel free to trash-talk my algo all you like, I never expected it to be the second greatest discovery right after general relativity or anything ;)

PS: Sorry for the poor title, but I can hardly explain the entire algo in one line :)

|improve this question
\$\endgroup\$
  • \$\begingroup\$ This algorithm will return false if A is completely within B or vice versa, by the way. \$\endgroup\$ – Philipp Jul 9 at 16:55
  • \$\begingroup\$ @Philipp of course, thanks for pointing that out, but for B to get inside A it must have collided at some point, so for me that's acceptable. It also allows for a shape to be "trapped" within another, like a bottle, for example. \$\endgroup\$ – DarkWiiPlayer Jul 9 at 16:56
  • \$\begingroup\$ You might like to search for "swept" or "continuous" collision detection. \$\endgroup\$ – Jay Jul 14 at 6:33
1
\$\begingroup\$

The reason why this algorithm might not have a name is because there are a lot of cases it isn't able to handle. For example this one:

fail1

The shapes are clearly overlapping, but shape A can move around quite a lot without any of the movement paths of its vertices ever intersecting with any of the edges of B.

It is in fact even able for A to completely pass over object B if B is small enough to fit through the edges of A:

fail2

|improve this answer
\$\endgroup\$
  • \$\begingroup\$ Ah, yes, I had forgotten that; you actually need to do the check in both directions, then it works :) \$\endgroup\$ – DarkWiiPlayer Jul 9 at 19:38
  • \$\begingroup\$ The first example, as I said, is acceptable to me, since the shapes need to spawn already overlapping for that to ever happen. \$\endgroup\$ – DarkWiiPlayer Jul 9 at 19:39
  • \$\begingroup\$ @DarkWiiPlayer No, the shapes in the first example don't need to spawn like that for this to happen. It is possible for shape A to move into that position coming from the left and then back out of the position the way it came. \$\endgroup\$ – Philipp Jul 9 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.