Rectangle-segment collision detection

Question

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:

1. Is my method correct mathematically?

2. Is there a better algorithm?

3. 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_1*y_2-x_2*y_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 <typename T>
inline double determinant(const T pmainx, const T pmainy,
                          const Vector2<T>& p1, const Vector2<T>& p2)
{
    return pmainx * p1.y + p1.x * p2.y + p2.x * pmainy - p2.x * p1.y -
           pmainx * p2.y - p1.x * pmainy;
}

Rectangle-segment collision detection function:

bool Mask::collision(Vector2double& lp1, Vector2double& lp2)
{
    if (this->type == TypeRectangle)
    {
        //rect left side
        double rleft   = this->position.x - this->origin.x;
        //rect right side
        double rright  = rleft + this->collsize.x;
        //rect top side
        double rtop    = this->position.y - this->origin.y;
        //rect bottom side
        double rbottom = rtop + this->collsize.y;


        //if the points are on the same side of the rectangle
        if ((lp1.x < rleft   && lp2.x < rleft)  ||
            (lp1.x > rright  && lp2.x > rright) ||
            (lp1.y < rtop    && lp2.y < rtop)   ||
            (lp1.y > rbottom && lp2.y > rbottom)
           )
        {
            return false;
        }


        //get determinant (this is the first determinant)
        //with top-left point of rectangle
        double maindelta = determinant(rleft, rtop, lp1, lp2);

        //get determinant
        //with top-right point of rectangle
        double checkdelta = determinant(rright, rtop, lp1, lp2);
        //check for sign difference
        if (!((maindelta >= 0) ^ (checkdelta < 0)))
        {
            return true;
        }

        //get determinant
        //bottom-right
        checkdelta = determinant(rright, rbottom, lp1, lp2);
        //check for sign difference
        if (!((maindelta >= 0) ^ (checkdelta < 0)))
        {
            return true;
        }

        //get determinant
        //bottom-left
        checkdelta = determinant(rleft, rbottom, lp1, lp2);
        //check for sign difference
        if (!((maindelta >= 0) ^ (checkdelta < 0)))
        {
            return true;
        }


        //else no sign differences
        return false;
    }
    //there are other cases for other meshes, not the part of this problem
}

Here is a test version in JavaScript. (Unfortunately it's not dynamic, I don't have time to develop it further).

Answer 1

I am going to comment on code only.

const

I recommend using const whenever appropriate.

It looks like you are not modifying lp1 and lp2:

bool Mask::collision(const Vector2double& lp1, const Vector2double& lp2)
{

You probably are not going to recalculated rleft and the likes:

    const double rleft   = this->position.x - this->origin.x;
    const double rright  = rleft + this->collsize.x;
    const double rtop    = this->position.y - this->origin.y;
    const double rbottom = rtop + this->collsize.y;

You are calculating maindelta only once:

    const double maindelta = determinant(rleft, rtop, lp1, lp2);

naming

Self documenting code is much better than code with low value comments. I would suggest naming variable like this and deleting those comments:

    const double rect_left_side   = this->position.x - this->origin.x;
    const double rect_right_side  = rleft + this->collsize.x;
    const double rect_top_side    = this->position.y - this->origin.y;
    const double rect_bottom_side = rtop + this->collsize.y;

tricky variables

Using one variable for different purposes (double checkdelta) leads to worse readability, comprehensibility and is a potential source of bugs. In this case you might skip it completely. I would recommend rewrite this

    checkdelta = determinant(rright, rbottom, lp1, lp2);
    //check for sign difference
    if (!((maindelta >= 0) ^ (checkdelta < 0)))
    {
        return true;
    }

to this

    //check for sign difference
    if (!((maindelta >= 0) ^ (determinant(rright, rbottom, lp1, lp2) < 0)))
    {
        return true;
    }

sign difference

I would certainly go in the direction JS1 recommended. I would possibly go as far as creating an inline function to explicitly state the intent:

inline bool have_different_signs(const double& a, const double& b) {
    return (a >= 0) != (b >= 0);
}

using this

Although it is no error there is usually no need to explicitly use this pointer in method definitions.

total

inline bool have_different_signs(const double& a, const double& b) {
    return (a >= 0) != (b >= 0);
}

bool Mask::collision(const Vector2double& lp1, const Vector2double& lp2)
{
    if (type == TypeRectangle)
    {
        const double rect_left_side   = position.x - origin.x;
        const double rect_right_side  = rect_left_side + collsize.x;
        const double rect_top_side    = position.y - origin.y;
        const double rect_bottom_side = rect_top_side + collsize.y;

        //if the points are on the same side of the rectangle
        if ((lp1.x < rect_left_side   && lp2.x < rect_left_side)  ||
            (lp1.x > rect_right_side  && lp2.x > rect_right_side) ||
            (lp1.y < rect_top_side    && lp2.y < rect_top_side)   ||
            (lp1.y > rect_bottom_side && lp2.y > rect_bottom_side)
           )
        {
            return false;
        }

        //get determinant with top-left point of rectangle (this is the first determinant) 
        const double maindelta = determinant(rect_left_side, rect_top_side, lp1, lp2);

        //get determinant with top-right point of rectangle
        if ( have_different_signs(maindelta, determinant(rect_right_side, rect_top_side, lp1, lp2) ) 
        {
            return true;
        }

        //get determinant with bottom-right point of rectangle
        if ( have_different_signs(maindelta, determinant(rect_right_side, rect_bottom_side, lp1, lp2)) )
        {
            return true;
        }

        //get determinant with bottom-left point of rectangle
        if ( have_different_signs(maindelta, determinant(rect_left_side, rect_bottom_side, lp1, lp2)) )
        {
            return true;
        }

        //else no sign differences
        return false;
    }
    //there are other cases for other meshes, not the part of this problem
}

one last idea

This is a wild guess but from

if (this->type == TypeRectangle)

and

//there are other cases for other meshes, not the part of this problem

I have an impression that you might want to detect collisions of different shapes in the future. If that is the case than Double dispatch in C++ might be interesting for you.

Answer 2

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_1*y_2-x_2*y_1\$

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

template <typename T>
inline double determinant(const T pmainx, const T pmainy,
                          const Vector2<T>& p1, const Vector2<T>& 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 <typename T>
inline double determinant(const T pmainx, const T pmainy,
                          const Vector2<T>& p1, const Vector2<T>& 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.