Line Segment Intersection

Hello. I’ve struggled for a while now to make a function thats takes in two line segments and returns a boolean on wether or not they intersect. From the plethora of leatures on the web about this, it seems to be a classic problem although I’ve found non of them very helpful. Any help on this matter would be greatly appreciated, thanks.

Do a google search. There is code that does exactly what you want.

Here’s something I found.

How to check if two given line segments intersect?

Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.

Before we discuss solution, let us define notion of orientation. Orientation of an ordered triplet of points in the plane can be
The following diagram shows different possible orientations of (a, b, c)


Note the word ‘ordered’ here. Orientation of (a, b, c) may be different from orientation of (c, b, a).

How is Orientation useful here?
Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified

1. General Case:
– (p1, q1, p2) and (p1, q1, q2) have different orientations and
– (p2, q2, p1) and (p2, q2, q1) have different orientations

2. Special Case 
– (p1, q1, p2), (p1, q1, q2), (p2, q2, p1), and (p2, q2, q1) are all collinear and
– the x-projections of (p1, q1) and (p2, q2) intersect
– the y-projections of (p1, q1) and (p2, q2) intersect

Examples of General Case:


Examples of Special Case:

Following is C++ implementation based on above idea.

// A C++ program to check if two given line segments intersect
#include <iostream>
using namespace std;
struct Point
    int x;
    int y;
// Given three colinear points p, q, r, the function checks if
// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;
    return false;
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
    // See 10th slides from following link for derivation of the formula
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;  // colinear
    return (val > 0)? 1: 2; // clock or counterclock wise
// The main function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
    // Find the four orientations needed for general and
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
    // General case
    if (o1 != o2 && o3 != o4)
        return true;
    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
     // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;
    return false; // Doesn't fall in any of the above cases
// Driver program to test above functions
int main()
    struct Point p1 = {1, 1}, q1 = {10, 1};
    struct Point p2 = {1, 2}, q2 = {10, 2};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\
": cout << "No\
    p1 = {10, 0}, q1 = {0, 10};
    p2 = {0, 0}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\
": cout << "No\
    p1 = {-5, -5}, q1 = {0, 0};
    p2 = {1, 1}, q2 = {10, 10};
    doIntersect(p1, q1, p2, q2)? cout << "Yes\
": cout << "No\
    return 0;


@dave1707 I’ve found lua code that claims to do this but there several hundered lines long and implementing it would require me to understand all of the workings of the function which would take days to sort through.

I found that webpage which did help understand how to know if they intersect but I’m still a world away from knowing it well enough to code it so I came here to see what you guys had on the matter.

@Goatboy76 Here’s a version. Tap the screen to create the end point of a new line.


function setup()

function draw()
    text("Tap screen for another end point",WIDTH/2,HEIGHT-50)
    if ua>0 and ua<1 and ub>0 and ub<1 then
        str=string.format("intersection point is %d %d",x,y)
        str=string.format("imaginary intersection point is %d %d",x,y)

function uaxy()

function touched(t)
    if t.state==BEGAN then

@dave1707 Thanks, thats an elegant soultion. I should be fine from here.

This is my code for intersections of line segments. It just returns true or false but could easily be modified to return the intersection point.

-- this is the tolerance at the end points when checking crossings
local epsilon = 0.01
function crossing(a,b,c,d)
    -- rebase at a
    b = b - a
    c = c - a
    d = d - a
    if b:cross(c) * b:cross(d) > 0 then
        -- both c and d lie on the same side of b so no intersection
        return false
    -- if there is an intersection point, this will be it
    a = (b:cross(d) * c - b:cross(c) * d)/(b:cross(d) - b:cross(c))
    -- does the potential intersection point lie on the line
    -- segment?
    local l = a:dot(b)
    if l > epsilon and l < b:dot(b) - epsilon then
        return true
    return false

@LoopSpace - I have a quick question about your code, below is my solution but I have a problem in that I want to detect if two co-planar lines actually overlap.

Does your code detect that?

Once I detect that the lines are coplanar then I though about calculating a bounding box around each line and seeing if they intersect but it doesn’t appear to be working. - UPDATE - Little bit of debugging showed that removing the = from the bboxCheck improves the situation.

-- ---------------------------------------------------------------------
-- Calc the intersection point of the line (return true if it's within the line)
local function bboxCheck(x1,y1,x2,y2, x3,y3,x4,y4)
    local ax1,ay1,ax2,ay2
    local bx1,by1,bx2,by2
    if x1 < x2 then ax1 = x1; ax2 = x2 else ax1 = x2; ax2 = x1 end
    if y1 < y2 then ay1 = y1; ay2 = y2 else ay1 = y2; ay2 = y1 end
    if x3 < x4 then bx1 = x3; bx2 = x4 else bx1 = x4; bx2 = x3 end
    if y3 < y4 then by1 = y3; by2 = y4 else by1 = y4; by2 = y3 end 
    if bx2 < ax1 then return false end  -- was <=
    if bx1 > ax2 then return false end  -- was >= 
    if by2 < ay1 then return false end  -- was <= 
    if by1 > ay2 then return false end  -- was >=
    return true

local function segmentIntersects(x1, y1, x2, y2, x3, y3, x4, y4)
    local d = (y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)
    local Ua_n = ((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3))
    local Ub_n = ((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3))

    if d == 0 then     -- edge cases
        if (Ua_n == 0) and (Ub_n == 0) then 
            -- In the same plane - try and work out if L2 overlaps L1 - if so then retun 4,0,0      
            -- could check this limited subset with a bounding box check
            if bboxCheck(x1,y1,x2,y2, x3,y3,x4,y4) then --print("OVERLAP") 
                return 4,0,0 end
            -- print("CO")    
            return 3,0,0
        else return 2,0,0 end     -- Parallel never intersect
    local Ua = Ua_n / d
    local Ub = Ub_n / d
    local px = x1 + Ua * (x2-x1)
    local py = y1 + Ua * (y2-y1) 
    if Ua > 0 and Ua < 1 and Ub > 0 and Ub < 1 then 
        return 0,px,py         -- intersect within bounds of line (not at endpoint)
   return 1,px,py        -- intersect out of bounds of line

UPDATE 2: Changing the final if statement to

    if Ua >= 0 and Ua <= 1 and Ub >= 0 and Ub <= 1 then 
        return 0,px,py         -- intersect within bounds of line (includes endpoint)

means that the line endpoints are also included - although in my requirements I don’t need that.