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
–counterclockwise
–clockwise
–colinear
The following diagram shows different possible orientations of (a, b, c)
orientation1
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:
GeneralCaseExamples
examplesGeneralCase21
Examples of Special Case:
examplesSpecialCase
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
// http://www.dcs.gla.ac.uk/~pat/52233/slides/Geometry1x1.pdf
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;
}
Output:
No
Yes
No
@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.
displayMode(FULLSCREEN)
supportedOrientations(LANDSCAPE_ANY)
function setup()
x1=300
y1=100
x2=700
y2=500
x3=200
y3=300
x4=600
y4=250
uaxy()
end
function draw()
background(0)
stroke(255)
strokeWidth(2)
line(x1,y1,x2,y2)
line(x3,y3,x4,y4)
fill(255)
ellipse(x,y,15)
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)
text(str,WIDTH/2,HEIGHT-150)
else
str=string.format("imaginary intersection point is %d %d",x,y)
text(str,WIDTH/2,HEIGHT-200)
end
end
function uaxy()
ua1=(x4-x3)*(y1-y3)-(y4-y3)*(x1-x3)
ub1=(x2-x1)*(y1-y3)-(y2-y1)*(x1-x3)
u2=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1)
ua=ua1/u2
ub=ub1/u2
x=x1+ua*(x2-x1)
y=y1+ua*(y2-y1)
end
function touched(t)
if t.state==BEGAN then
x4=t.x
y4=t.y
uaxy()
end
end
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
end
-- 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
end
return false
end
@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
end
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
end
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)
end
return 1,px,py -- intersect out of bounds of line
end
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)
end
means that the line endpoints are also included - although in my requirements I don’t need that.