Detect if line segment intersects square

Question

Anyone have a simple algorithm for this? No need for rotation or anything. Just finding if a line segment made from two points intersects a square

Answer 1

You can do this by casting a vector and counting the number of edges it crosses.

If the edges it crosses are even, it is outside the object, if the edges it crosses are odd, it is inside.

This works for all closed polygons.

Answer 2

This code should do the trick. It checks where the line intersects the sides, then checks if that is within the sidth of the square. The number of intesections is returned.

float CalcY(float xval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return y0 + (xval - x0)*(y1 - y0)/(x1 - x0);
}

float CalcX(float yval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return x0 + (yval - y0)*(y1 - y0)/(x1 - x0);
}

int LineIntersectsSquare(int x0, int y0, int x1, int y1, int left, int top, int right, int bottom)
{
    int intersections = 0;
    if(CalcX(bottom, x0, y0, x1, y1) < right && CalcX(bottom, x0, y0, x1, y1) > left  ) intersections++;
    if(CalcX(top   , x0, y0, x1, y1) < right && CalcX(top   , x0, y0, x1, y1) > left  ) intersections++;
    if(CalcY(left  , x0, y0, x1, y1) < top   && CalcY(left  , x0, y0, x1, y1) > bottom) intersections++;
    if(CalcY(right , x0, y0, x1, y1) < top   && CalcY(right , x0, y0, x1, y1) > bottom) intersections++;
    return intersections;
}

NB: this code is theoretical and may not be correct, as it has not been tested

Answer 3

Here's a way:
- sort the vertex points of the square by x-coord
- sort the endpoint of the line by x-coord
- calculate angle from the minX end of the line to each of the middle two (by x-coord) square vertices
- calculate angle of the line
- if the line's angle is within the possible angles, all you have to do is a length check, is maxX end of the line > minX vertex of the square

This will probably break if the square is directly facing the line, in that case I'd just special-case it by checking the first edge of the square.

Answer 4

I found really interesting the way you thought about it Eric.. But can any body put some explanation on it some kind of comments or at least tell me what every var means, I guessed the x0,x1,y0,y1 are the point's coordinates. then what are xval and yval?? I am quite lost, I wanted to transpose it on Delphi6 but got a bit lost, may somebody help me so that I can put my results up here!