Rectangle-segment collision detection

I am working with C++ and SDL, hoping to create a game later. I am implementing the collision detection between rectangles and segments.

I found this (NateS user's solution) about line-rectangle collision detection on Stack Overflow. I'm working in C++ and not in Java; and though it isn't that hard to reimplement in C++ (I have to check Infinity cases), I decided to work with my own method. It works fine (so far) however I'm not sure if my method is right, because I haven't proved it mathematically (yet).

So, there are three questions:

-
Is my method correct mathematically?

-
Is there a better algorithm?

-
What could I make better in my code?

About my method:

I calculate a determinant of the three points. Lets take the equation of the line which holds the segment:
$$\begin{vmatrix}
x & y & 1 \\
x_1 & y_1 & 1 \\
x_2 & y_2 & 1 \\
\end{vmatrix}
=x(y_1 - y_2)+y(x_2 - x_1)+x_1y_2-x_2y_1=0$$

So, if the point is above the line, y will be greater, and so the the determinant value will be greater than 0 (except when the line is vertical). If is under the line, the determinant will be negative. This applies for x too. We use this for detecting sign differences between determinants, where we use the rectangle points four times respectively for checking the coordinate with the line points. If there is a difference between sign, that means the line is going through the rectangle.

Actually, before this we check if the ends of the segment are on the same side, else we will check the collision with line and not with segment.

As I said it before, I'm not 100% percent sure, if this works perfectly. Here is the actual code (where Vector2 is used for represent points).

Determinant calculation:

```
//This function return the determinant of a main point with coordinates
//pmainx, pmainy and another two points: p1, p2
template
inline double determinant(const T pmainx, const T pmainy,
const Vector2& p1, const Vector2& p2)
{
return pmain

Checking for sign difference

The current code is hard to read:

//check for sign difference
    if (!((maindelta >= 0) ^ (checkdelta < 0)))

I think the simplest way to express what you are checking is like this:

//check for sign difference
    if ((maindelta >= 0) != (checkdelta >= 0))

More efficient computation

The determinant formula you wrote in your description:

\$x(y_1 - y_2)+y(x_2 - x_1)+x_1y_2-x_2y_1\$

is more efficient than the one you used in your code:

template 
inline double determinant(const T pmainx, const T pmainy,
                          const Vector2& p1, const Vector2& p2)
{
    return pmainx * p1.y + p1.x * p2.y + p2.x * pmainy - p2.x * p1.y -
           pmainx * p2.y - p1.x * pmainy;
}

Notice there are 6 multiplies and 5 adds/subtracts. If you changed your code to match your formula:

template 
inline double determinant(const T pmainx, const T pmainy,
                          const Vector2& p1, const Vector2& p2)
{
    return pmainx * (p1.y - p2.y) + pmainy * (p2.x - p1.x) +
            p1.x * p2.y + - p2.x * p1.y;
}

there are now only 4 multiplies and 5 adds/subtracts, so you saved 2 multiplies.

Collision detection correctness

I see a possible flaw in the collision detection. If your line intersects the rectangle at exactly one corner, your determinant for that corner will be 0. If the rest of the rectangle is above that corner, your function will return "no collision". This is because all of the other determinants will be greater than 0, so the signs will all match. However, if the rest of the rectangle is below that corner, your function will return "collision", because the other determinants will be less than 0, and the signs will not match.

To fix this, you should also check if any of the determinants exactly equals 0. If so, then that means the line intersected the rectangle at a corner and you should return true.

StackExchange Code Review Q#132642, answer score: 3