Why not test every single edge during collision detection?

Question

I'm a beginner so sorry if this is a stupid question

I'm trying to implement some collision detection and the most common type I see is SAT, which I believe has a time complexity of O((n+m)^2), where and n and m are the amount of vertices on each polygon.

However, why not turn every side into a line segment, and check if any of the segments are intersecting with the segments in the other polygon? The way I see it is there are going to be n*m comparisons, and each comparison can be done in constant time, so it's faster than SAT and would work with concave polygons.

Again, sorry if this is a stupid question and thanks!

Answer 1

The method that you propose does not detect when one polygon is fully inside the other, and so no line segments intersect.

You can solve that with two point-in-polygon tests O(n) if all edge intersections come up negative.

But this proposed method would still be slower because the work needed to check if an edge crosses any of a list of other edges is actually more than the work needed to compare the dot product of that edge's normal against a list of vertices (2 multiplies and an add each, easy to vectorize). They both have the same O(n^2) time complexity for polygons containing n vertices, but the coefficients that big-O hides are smaller for conventional SAT since the inner loop is so dirt cheap.