Line Intersection

This is a discussion on Line Intersection within the C++ Programming forums, part of the General Programming Boards category; How would one go about finding if two 2D line segments intersect? I know how to do it on paper, ...

  1. #1
    The Reel Thing
    Join Date
    Jun 2005
    Posts
    44

    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?
    Last edited by Highland Laddie; 10-13-2005 at 02:31 PM.
    Bagpipes – putting the fun back in funeral.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Two lines of code can't intersect, it would drive the compiler nuts.
    My best code is written with the delete key.

  3. #3
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    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.
    Sent from my iPad®

  4. #4
    The Reel Thing
    Join Date
    Jun 2005
    Posts
    44
    Yeah, I guess it would. I totally ran into that one.
    Bagpipes – putting the fun back in funeral.

  5. #5
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    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.
    Sent from my iPad®

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  7. #7
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    Yeah, I figured that much from his reply.
    Sent from my iPad®

  8. #8
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by Highland Laddie
    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
    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

  9. #9
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    By standard, the variables in slope-intercept is Y = mX + B.
    Sent from my iPad®

  10. #10
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    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).

    This code has been reformatted to fit your web browser
    Programming Your Mom. http://www.dandongs.com/

  11. #11
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by SlyMaelstrom
    By standard, the variables in slope-intercept is Y = mX + B.
    true, but I think it might still work

  12. #12
    Devil's Advocate SlyMaelstrom's Avatar
    Join Date
    May 2004
    Location
    Out of scope
    Posts
    4,066
    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
    This code has been reformatted to fit your web browser
    It doesn't fit mine.

    Be sure to use your right margin, it's a magical thing.
    Last edited by SlyMaelstrom; 10-13-2005 at 03:53 PM.
    Sent from my iPad®

  13. #13
    The Reel Thing
    Join Date
    Jun 2005
    Posts
    44
    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;
       }
    Bagpipes – putting the fun back in funeral.

  14. #14
    semi-colon generator ChaosEngine's Avatar
    Join Date
    Sep 2005
    Location
    Chch, NZ
    Posts
    597
    Quote Originally Posted by Highland Laddie

    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;
    // snip
       
       // Calculate the intersection point
       double intersectionX = (yInt2 - yInt1) / (slope1 - slope2);
    you need to check these lines for division by zero
    "I saw a sign that said 'Drink Canada Dry', so I started"
    -- Brendan Behan

    Free Compiler: Visual C++ 2005 Express
    If you program in C++, you need Boost. You should also know how to use the Standard Library (STL). Want to make games? After reading this, I don't like WxWidgets anymore. Want to add some scripting to your App?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pointer and Polymorphism help.
    By Skyy in forum C++ Programming
    Replies: 29
    Last Post: 12-18-2008, 08:17 PM
  2. Printing Length of Input and the Limited Input
    By dnguyen1022 in forum C Programming
    Replies: 33
    Last Post: 11-29-2008, 03:13 PM
  3. adding line numbers and concatenating a filename
    By durrty in forum C Programming
    Replies: 25
    Last Post: 06-28-2008, 03:36 AM
  4. Finding carriage returns (\c) in a line
    By JizJizJiz in forum C++ Programming
    Replies: 37
    Last Post: 07-19-2006, 05:44 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21