# Function to see whether two lines intersect

Suppose I have an array of size n, storing information about lines on a grid by storing the (left,top) and (right,bottom) co-ordinates using a RECT structure. How could a function determine whether a line specified by the user intersects any of the lines stored in this array?

The code would look something like the following:
[CODE]RECT rect_array[n];
...
bool DoesLineIntersectAny(RECT line)
{
for(int i = 0; i < n; i++)
if(LineIntersects(rect_array[i], line)
return true;

return false;
}
[/CODE]Unfortunately I cannot find a function such as "LineIntersects" in any standard libraries or API's. Any help would be greatly appreciated.

• You can use a bit of algebra to determine whether 2 lines cross.

First, determine an equation for each line. You can do this easily by working out the gradient of the line (increase in y / increase in x) and the find the constant of the equation, which will be the value of y when x = 0.

So say you have a line made up of 2 points with co-ordinates (10, 10) and (15, 20). The increase in y is 10 and the increase in x is 5, so the gradient is 10 / 5 = 2. When x = 0, y will be 5, so the constant in the equation is 5. This will give equation of the line as
y = 2x + 5

Now do the same for the second line. Assume the gradient is 4 and the constant is 13. This makes the second equation
y = 4x + 13

To find the point of intersection, you just need to find where the 2 equations are equal. Do this by combining the equations like this:

2x + 5
4x + 13

2x + 5 = 4x + 13

Rearrange this to make x on it's own on the left hand side:

2x + 5 = 4x + 13
-2x + 5 = 0x + 13
-2x + 0 = 0x + 8
-2x = 8
x = -4

This result means the 2 lines intersect when x is at -4
You can then substitute this value of x into any of the 2 equations to retrieve the y co-ordinate.

Actually the thing with straight lines is, there will ALWAYS be a point of intersection! The only exception of course is if the 2 lines are parallel, or they have the same gradient. To do a simple check of whether 2 lines will ever cross, check to see if their gradients are equal. I'm just assuming you wanted to know where they intersect.

• That's a great help! Thank you very much :-)
• : You can use a bit of algebra to determine whether 2 lines cross.
:
: First, determine an equation for each line. You can do this easily by working out the gradient of the line (increase in y / increase in x) and the find the constant of the equation, which will be the value of y when x = 0.
:
: So say you have a line made up of 2 points with co-ordinates (10, 10) and (15, 20). The increase in y is 10 and the increase in x is 5, so the gradient is 10 / 5 = 2. When x = 0, y will be 5, so the constant in the equation is 5. This will give equation of the line as
: y = 2x + 5
:
: Now do the same for the second line. Assume the gradient is 4 and the constant is 13. This makes the second equation
: y = 4x + 13
:
: To find the point of intersection, you just need to find where the 2 equations are equal. Do this by combining the equations like this:
:
: 2x + 5
: 4x + 13
:
: 2x + 5 = 4x + 13
:
: Rearrange this to make x on it's own on the left hand side:
:
: 2x + 5 = 4x + 13
: -2x + 5 = 0x + 13
: -2x + 0 = 0x + 8
: -2x = 8
: x = -4
:
: This result means the 2 lines intersect when x is at -4
: You can then substitute this value of x into any of the 2 equations to retrieve the y co-ordinate.
:
: Actually the thing with straight lines is, there will ALWAYS be a point of intersection! The only exception of course is if the 2 lines are parallel, or they have the same gradient. To do a simple check of whether 2 lines will ever cross, check to see if their gradients are equal. I'm just assuming you wanted to know where they intersect.
:
: Hope that solves your problem.

The lines mentioned do not always intersect. They have a start and end point and therefore have a length.
If you find the X for which two lines intersect, you'll have to check if that value does not fall outside of both lines' starting and ending X-values.

Greets,
Eric Goldstein
http://www.gvh-maatwerk.nl

• : : You can use a bit of algebra to determine whether 2 lines cross.
: :
: : First, determine an equation for each line. You can do this easily by working out the gradient of the line (increase in y / increase in x) and the find the constant of the equation, which will be the value of y when x = 0.
: :
: : So say you have a line made up of 2 points with co-ordinates (10, 10) and (15, 20). The increase in y is 10 and the increase in x is 5, so the gradient is 10 / 5 = 2. When x = 0, y will be 5, so the constant in the equation is 5. This will give equation of the line as
: : y = 2x + 5
: :
: : Now do the same for the second line. Assume the gradient is 4 and the constant is 13. This makes the second equation
: : y = 4x + 13
: :
: : To find the point of intersection, you just need to find where the 2 equations are equal. Do this by combining the equations like this:
: :
: : 2x + 5
: : 4x + 13
: :
: : 2x + 5 = 4x + 13
: :
: : Rearrange this to make x on it's own on the left hand side:
: :
: : 2x + 5 = 4x + 13
: : -2x + 5 = 0x + 13
: : -2x + 0 = 0x + 8
: : -2x = 8
: : x = -4
: :
: : This result means the 2 lines intersect when x is at -4
: : You can then substitute this value of x into any of the 2 equations to retrieve the y co-ordinate.
: :
: : Actually the thing with straight lines is, there will ALWAYS be a point of intersection! The only exception of course is if the 2 lines are parallel, or they have the same gradient. To do a simple check of whether 2 lines will ever cross, check to see if their gradients are equal. I'm just assuming you wanted to know where they intersect.
: :
: : Hope that solves your problem.
:
: The lines mentioned do not always intersect. They have a start and end point and therefore have a length.
: If you find the X for which two lines intersect, you'll have to check if that value does not fall outside of both lines' starting and ending X-values.
:
:
: Greets,
: Eric Goldstein
: http://www.gvh-maatwerk.nl
:
:
:
[green]
The domain of line y=mx+b is the set of reals. It's range is the set of all reals, so it could go on to -infinity to +infinity. What you are describing is the distance between two points which is only part of a line or also called a line segment.
[/green]