Detect if a line segment crosses a square

Question

Does anyone have a simple algorithm for this? No need for rotation or anything else. Just find if a line segment made of two points crosses a square

Answer 1

This code should do the trick. It checks where the line crosses the sides, and then checks to see if it is within the width of the square. The number of queries 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 be incorrect since it has not been tested

Answer 2

You can do this by setting the vector and counting the number of edges crossed.

If the edges that intersect are even, they are outside the object, if the intersecting edges are odd, it is inside.

This works for all closed polygons.

Answer 3

Here is the way:
- sort the vertex points of a square using x-ord - sort the endpoint of a line using x-ord

- calculate the angle from minX of the end of the line to each of the two square (in x-coordinate) square vertices
- calculate the angle of the line
- if the angle of the line is within the range of possible angles, all you have to do is check the length, this is maxX end of line> minX vertex of the square

This will probably break if the square directly faces the line, in which case I would just make it a special case by checking the first edge of the square.