# Line Intersection

• 10-13-2005
Line Intersection
How would one go about finding if two 2D line segments intersect? I know how to do it on paper, but I'm totally baffled how to do it in code. Any suggestions?
• 10-13-2005
Prelude
Two lines of code can't intersect, it would drive the compiler nuts.
• 10-13-2005
SlyMaelstrom
Are you talking about graphical programming or are you just asking how to code the equation to see if two lines intersect?

If you're talking about the latter, then simply write a program that accepts ( or figures out ) the slopes of both lines, and if they aren't parallel and they are both straight, then they intersect.
• 10-13-2005
Yeah, I guess it would. I totally ran into that one.
• 10-13-2005
SlyMaelstrom
Quote:

Originally Posted by Prelude
Two lines of code can't intersect, it would drive the compiler nuts.

If this isn't a joke that I don't understand then I'd say you don't understand his question.

He's asking how to write code to figure out if two lines on a Cartesian plane intersect.

... atleast I think that's what he's asking.
• 10-13-2005
Prelude
>If this isn't a joke that I don't understand then I'd say you don't understand his question.
I guess it's a joke that you don't understand then. ;)
• 10-13-2005
SlyMaelstrom
Yeah, I figured that much from his reply. ;)
• 10-13-2005
ChaosEngine
Quote:

How would one go about finding if two 2D line segments intersect? I know how to do it on paper, but I'm totally baffled how to do it in code. Any suggestions?

Morally, I should tell you to get off your lazy ass and do some research, but since your a fellow celt and I'm feeling lazy myself this morning so here ya go :D
Code:

```        // need to calc line functions for both lines         // line func : y = a * x + b         // so for line (x1, y1) (x2, y2)         //    (y2 - y1)          (y2 - y1)         // a = ---------  b = y1 - --------- * x1         //    (x2 - x1)          (x2 - x1)         // calc vals for line from centre to joystick pos         int denominator = x2- x1;         if (0 == denominator)         {                 // oops divide by zero                 // should happen for the target line                 return;         }         float joyA = (float)((y2 - y1) / (float)denominator);         float joyB = y1 - joyA * x1;                 // calc vals for poly lines         int lineDenominator = x2 - x1;         if (0 != lineDenominator)         {                 float lineA = (float)((y2 - y1) /                         (float)lineDenominator);                 float lineB = y1 - lineA * (float)x1;                 // intersection point is calculated as                 //      (b2 - b1)              (b2 - b1)                 // xi = ---------    yi = a1 * --------- + b1                 //      (a1 - a2)              (a1 - a2)                 float solvedDenominator = joyA - lineA;                 if (0.0001f < std::fabs(solvedDenominator))                 {                         float flSolvedX = (lineB - joyB) / solvedDenominator;                         int solvedX = (int)flSolvedX;                         int solvedY = (int)(joyA * flSolvedX + joyB);                         if (solvedX > min(x1, x2) &&                                 solvedX < max(x1, x2) &&                                 solvedY > min(y1, y2) &&                                 solvedY < max(y1, y2))                         {                                 int interX = solvedX;                                 int interY = solvedY;                         }                 }         }```
it's slightly bastardised from existing code so you'll need to make it work properly (i.e. put it in a fucntion or something), but it should get you started
• 10-13-2005
SlyMaelstrom
By standard, the variables in slope-intercept is Y = mX + B. :)
• 10-13-2005
CrazyNorman
I stumbled upon another way a while back. Its a good deal simpler, and it does indeed work.
Code:

```struct vertex {           float x,z; }; bool intersect (vertex v1, vertex v2, vertex p1, vertex p2); bool counter_clockwise(vertex p1, vertex p2, vertex p3); /*Call this function with your four points  *v1,v2 are vertices of one line  *p1,p2 are vertices of the other  */ bool intersect (vertex v1, vertex v2, vertex p1, vertex p2) {   if (counter_clockwise(p1,p2,v1)!=counter_clockwise(p1,p2,v2) && counter_clockwise(v1,v2,p1)!=counter_clockwise(v1,v2,p2))   {     return 1; //The lines of collided   }   else   {     return 0;   } } bool counter_clockwise(vertex p1,vertex p2,vertex p3) {   return ((p2.z-p1.z)*(p3.x-p2.x)<(p3.z-p2.z)*(p2.x-p1.x)); }```
I've modified this so that it is not dependent on my game.
It should work, and does compile correctly (assuming no Copy/Paste errors).

• 10-13-2005
ChaosEngine
Quote:

Originally Posted by SlyMaelstrom
By standard, the variables in slope-intercept is Y = mX + B. :)

true, but I think it might still work :p
• 10-13-2005
SlyMaelstrom
Maybe not. As you know, simple inproper uses of variables, be it used in comments, code, or what have you, have a tendency to drive obviously highly intelligent things like home PCs to insanity. Which is the reason that so many PCs have been murdering their end users in thie sleep, lately.

Quote:

Originally Posted by CrazyNorman

It doesn't fit mine. :)

Be sure to use your right margin, it's a magical thing. :)
• 10-13-2005
Well, I think I got something figured out. I have yet to test it and debug it, but I'll get around to it later. Anyways, heres the code.

Code:

```  // Get the slope of the lines   double slope1 = End.Y - Start.Y / End.X - Start.X;   double slope2 = otherLine.End.Y - otherLine.Start.Y / otherLine.End.X - otherLine.Start.X;     // Get the Y - intercepts of the line   double yInt1 = slope1 * Start.X - Start.Y;   double yInt2 = slope2 * otherLine.Start.X - otherLine.Start.Y;     // Return false if the lines are paralell   if (slope1 == slope2)   {       return false;   }     // Calculate the intersection point   double intersectionX = (yInt2 - yInt1) / (slope1 - slope2);   double intersectionY = slope1 * intersectionX + yInt1;     // Check if the two line segments intersect   if (intersectionX < Start.X || intersectionY > Start.Y || intersectionX > End.X || intersectionY < End.Y)   {       return false;    }   else   {       return true;   }```
• 10-13-2005
ChaosEngine
Quote:

```  // Get the slope of the lines   double slope1 = End.Y - Start.Y / End.X - Start.X;   double slope2 = otherLine.End.Y - otherLine.Start.Y / otherLine.End.X - otherLine.Start.X; // snip     // Calculate the intersection point   double intersectionX = (yInt2 - yInt1) / (slope1 - slope2);```