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.

Cases of determinants

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.

• 200_success: I think that the algorithm should work for any polygon.
• Jan Korous: @200_success You mean in principle or the code presented here?
• Lasoloz: Thank you! The constness was my fault, first I wanted to make the collision resovable, but then I thought, I don't need it, and I forgot to add constness. I created a editable and testable JS. Thank you for the other ideas too.
• Lasoloz: @200_success You mean, that the mathematical method I used, should work on every kind of segment-polygon collision detection?
• 200_success: Yes, I mean that there is nothing special about rectangles; the same idea could work for any polygon.

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.

• Lasoloz: Thank you! Any ideas about my mathematical method?
• JS1: @Lasoloz I updated my answer to review your mathematical method.
• Lasoloz: And does this update mean, that the way I detect collisions seems correct?
• JS1: @Lasoloz Hi, I updated my answer again.
• Lasoloz: Thank you again. :) This was actually the main reason I put my question here - I didn't know if I'm right in the math part. I will check this out, making the points collinear at start. Actually, if it intersects at the corner, but it's not going through the rectangle, it's not a problem; but if the first, top-left determinant is zero, I can get error.