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 :)

\$\endgroup\$
3
  • \$\begingroup\$ This algorithm will return false if A is completely within B or vice versa, by the way. \$\endgroup\$
    – Philipp
    Commented Jul 9, 2019 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\$ Commented Jul 9, 2019 at 16:56
  • \$\begingroup\$ You might like to search for "swept" or "continuous" collision detection. \$\endgroup\$
    – Jay
    Commented Jul 14, 2019 at 6:33

1 Answer 1

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

\$\endgroup\$
3
  • \$\begingroup\$ Ah, yes, I had forgotten that; you actually need to do the check in both directions, then it works :) \$\endgroup\$ Commented Jul 9, 2019 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\$ Commented Jul 9, 2019 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
    Commented Jul 9, 2019 at 22:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .