Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Function to see whether two lines intersect

zeolitezeolite Member Posts: 78
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.

Comments

  • FazFaz Member Posts: 75
    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.
  • zeolitezeolite Member Posts: 78
    That's a great help! Thank you very much :-)
  • tsagldtsagld Member Posts: 621
    : 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


  • shaolin007shaolin007 Member Posts: 1,018
    : : 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]

Sign In or Register to comment.