How can I check if 2 segments intersect?
I've the following data:
Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]
I need to write a small algorithm in Python to detect if the 2 lines are intersecting.
How can I check if two segments intersect?
Viewed 192779
24 Answers
User @i_4_got points to this page with a very efficent solution in Python. I reproduce it here for convenience (since it would have made me happy to have it here):
def ccw(A,B,C):
return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)
# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
Checking if line segments intersect is very easy with Shapely library using intersects method:
from shapely.geometry import LineString
line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True
line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False
Here's a solution using dot products:
# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
dx0 = s0[1][0]-s0[0][0]
dx1 = s1[1][0]-s1[0][0]
dy0 = s0[1][1]-s0[0][1]
dy1 = s1[1][1]-s1[0][1]
p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
return (p0*p1<=0) & (p2*p3<=0)
Here's a visualization in Desmos: Line Segment Intersection
This is my way of checking for line crossing and where the intersection occurs. Lets use x1 through x4 and y1 through y4
Segment1 = ((X1, Y1), (X2, Y2))
Segment2 = ((X3, Y3), (X4, Y4))
Then we need some vectors to represent them
dx1 = X2 - X1
dx2 = X4 - X3
dy1 = Y2 - Y1
dy2 = Y4 - Y3
Now we look at the determinant
det = dx1 * dy2 - dx2 * dy1
If the determinant is 0.0, then the line segments are parallel. This could mean they overlap. If they overlap just at endpoints, then there is one intersection solution. Otherwise there will be infinite solutions. With infinitely many solutions, what do say is your point of intersection? So it's an interesting special case. If you know ahead of time that the lines can't overlap then you can just check if det == 0.0 and if so just say they don't intersect and be done. Otherwise, lets continue on
dx3 = X1 - X3
dy3 = Y1 - Y3
det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2
Now, if det, det1 and det2 are all zero, then your lines are co-linear and could overlap. If det is zero but either det1 or det2 are not, then they are not co-linear, but are parallel, so there is no intersection. So what's left now if det is zero is a 1D problem instead of 2D. We will need to check one of two ways, depending if dx1 is zero or not (so we can avoid division by zero). If dx1 is zero then just do the same logic with y values rather than x below.
s = X3 / dx1
t = X4 / dx1
This computes two scalers, such that if we scale the vector (dx1, dy1) by s we get point (x3, y3), and by t we get (x4, y4). So if either s or t is between 0.0 and 1.0, then point 3 or 4 lies on our first line. Negative would mean the point is behind the start of our vector, while > 1.0 means it is further ahead of the end of our vector. 0.0 means it is at (x1, y1) and 1.0 means it is at (x2, y2). If both s and t are < 0.0 or both are > 1.0, then they don't intersect. And that handles the parallel lines special case.
Now, if det != 0.0 then
s = det1 / det
t = det2 / det
if s < 0.0 or s > 1.0 or t < 0.0 or t > 1.0:
return false # no intersect
This is similar to what we were doing above really. Now if we pass the above test, then our line segments intersect, and we can calculate the intersection quite easily like so:
Ix = X1 + t * dx1
Iy = Y1 + t * dy1
If you want to dig deeper into what the math is doing, look into Cramer's Rule.
Edit: I've fixed two errors that were present so it should be correct now. I've learned enough python now to write actual code for this now. It works except for some special cases, though it does handle some special cases correctly. Special cases get really hard to deal with and I've spend enough time on it and want to move on. If someone requires better then they have a good starting point at least to try and improve it.
import math
def line_intersection(line1, line2):
x1, x2, x3, x4 = line1[0][0], line1[1][0], line2[0][0], line2[1][0]
y1, y2, y3, y4 = line1[0][1], line1[1][1], line2[0][1], line2[1][1]
dx1 = x2 - x1
dx2 = x4 - x3
dy1 = y2 - y1
dy2 = y4 - y3
dx3 = x1 - x3
dy3 = y1 - y3
det = dx1 * dy2 - dx2 * dy1
det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2
if det == 0.0: # lines are parallel
if det1 != 0.0 or det2 != 0.0: # lines are not co-linear
return None # so no solution
if dx1:
if x1 < x3 < x2 or x1 > x3 > x2:
return math.inf # infinitely many solutions
else:
if y1 < y3 < y2 or y1 > y3 > y2:
return math.inf # infinitely many solutions
if line1[0] == line2[0] or line1[1] == line2[0]:
return line2[0]
elif line1[0] == line2[1] or line1[1] == line2[1]:
return line2[1]
return None # no intersection
s = det1 / det
t = det2 / det
if 0.0 < s < 1.0 and 0.0 < t < 1.0:
return x1 + t * dx1, y1 + t * dy1
print("one intersection")
print(line_intersection(((0.0,0.0), (6.0,6.0)),((0.0,9.0), (9.0,0.0))))
print(line_intersection(((-2, -2), (2, 2)), ((2, -2), (-2, 2))))
print(line_intersection(((0.5, 0.5), (1.5, 0.5)), ((1.0, 0.0), (1.0, 2.0))))
print(line_intersection(((0, -1), (0, 0)), ((0, 0), (0, 1))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (1, 0))))
print()
print("no intersection")
print(line_intersection(((-1, -1), (0, 0)), ((2, -4), (2, 4))))
print(line_intersection(((0.0,0.0), (0.0,9.0)),((9.0,0.0), (9.0,99.0))))
print(line_intersection(((0, 0), (1, 1)), ((1, 0), (2, 1))))
print(line_intersection(((-1, 1), (0, 1)), ((0, 0), (1, 0))))
print(line_intersection(((1, -1), (1, 0)), ((0, 0), (0, -1))))
print()
print("infinite intersection")
print(line_intersection(((-1, -1), (1, 1)), ((0, 0), (2, 2))))
print(line_intersection(((-1, 0), (1, 0)), ((0, 0), (2, 0))))
print(line_intersection(((0, -1), (0, 1)), ((0, 0), (0, 2))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (-1, 0))))
print(line_intersection(((1, 0), (0, 0)), ((0, 0), (1, 0))))
Here is another python code to check whether closed segments intersect. It is the rewritten version of the C++ code in http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/. This implementation covers all special cases (e.g. all points colinear).
def on_segment(p, q, r):
'''Given three colinear points p, q, r, the function checks if
point q lies on line segment "pr"
'''
if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])):
return True
return False
def orientation(p, q, r):
'''Find orientation of ordered triplet (p, q, r).
The function returns following values
0 --> p, q and r are colinear
1 --> Clockwise
2 --> Counterclockwise
'''
val = ((q[1] - p[1]) * (r[0] - q[0]) -
(q[0] - p[0]) * (r[1] - q[1]))
if val == 0:
return 0 # colinear
elif val > 0:
return 1 # clockwise
else:
return 2 # counter-clockwise
def do_intersect(p1, q1, p2, q2):
'''Main function to check whether the closed line segments p1 - q1 and p2
- q2 intersect'''
o1 = orientation(p1, q1, p2)
o2 = orientation(p1, q1, q2)
o3 = orientation(p2, q2, p1)
o4 = orientation(p2, q2, q1)
# General case
if (o1 != o2 and o3 != o4):
return True
# Special Cases
# p1, q1 and p2 are colinear and p2 lies on segment p1q1
if (o1 == 0 and on_segment(p1, p2, q1)):
return True
# p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 and on_segment(p1, q2, q1)):
return True
# p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 and on_segment(p2, p1, q2)):
return True
# p2, q2 and q1 are colinear and q1 lies on segment p2q2
if (o4 == 0 and on_segment(p2, q1, q2)):
return True
return False # Doesn't fall in any of the above cases
Below is a test function to verify that it works.
import matplotlib.pyplot as plt
def test_intersect_func():
p1 = (1, 1)
q1 = (10, 1)
p2 = (1, 2)
q2 = (10, 2)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
p1 = (10, 0)
q1 = (0, 10)
p2 = (0, 0)
q2 = (10, 10)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
p1 = (-5, -5)
q1 = (0, 0)
p2 = (1, 1)
q2 = (10, 10)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
p1 = (0, 0)
q1 = (1, 1)
p2 = (1, 1)
q2 = (10, 10)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
The answer by Georgy is the cleanest to implement, by far. Had to chase this down, since the brycboe example, while simple as well, had issues with colinearity.
Code for testing:
#!/usr/bin/python
#
# Notes on intersection:
#
# https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
#
# https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect
from shapely.geometry import LineString
class Point:
def __init__(self,x,y):
self.x = x
self.y = y
def ccw(A,B,C):
return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
def ShapelyIntersect(A,B,C,D):
return LineString([(A.x,A.y),(B.x,B.y)]).intersects(LineString([(C.x,C.y),(D.x,D.y)]))
a = Point(0,0)
b = Point(0,1)
c = Point(1,1)
d = Point(1,0)
'''
Test points:
b(0,1) c(1,1)
a(0,0) d(1,0)
'''
# F
print(intersect(a,b,c,d))
# T
print(intersect(a,c,b,d))
print(intersect(b,d,a,c))
print(intersect(d,b,a,c))
# F
print(intersect(a,d,b,c))
# same end point cases:
print("same end points")
# F - not intersected
print(intersect(a,b,a,d))
# T - This shows as intersected
print(intersect(b,a,a,d))
# F - this does not
print(intersect(b,a,d,a))
# F - this does not
print(intersect(a,b,d,a))
print("same end points, using shapely")
# T
print(ShapelyIntersect(a,b,a,d))
# T
print(ShapelyIntersect(b,a,a,d))
# T
print(ShapelyIntersect(b,a,d,a))
# T
print(ShapelyIntersect(a,b,d,a))
We can also solve this utilizing vectors.
Let's define the segments as [start, end]. Given two such segments [A, B] and [C, D] that both have non-zero length, we can choose one of the endpoints to be used as a reference point so that we get three vectors:
x = 0
y = 1
p = A-C = [C[x]-A[x], C[y]-A[y]]
q = B-A = [B[x]-A[x], B[y]-A[y]]
r = D-C = [D[x]-C[x], D[y]-C[y]]
From there, we can look for an intersection by calculating t and u in p + t*r = u*q. After playing around with the equation a little, we get:
t = (q[y]*p[x] - q[x]*p[y])/(q[x]*r[y] - q[y]*r[x])
u = (p[x] + t*r[x])/q[x]
Thus, the function is:
def intersects(a, b):
p = [b[0][0]-a[0][0], b[0][1]-a[0][1]]
q = [a[1][0]-a[0][0], a[1][1]-a[0][1]]
r = [b[1][0]-b[0][0], b[1][1]-b[0][1]]
t = (q[1]*p[0] - q[0]*p[1])/(q[0]*r[1] - q[1]*r[0]) \
if (q[0]*r[1] - q[1]*r[0]) != 0 \
else (q[1]*p[0] - q[0]*p[1])
u = (p[0] + t*r[0])/q[0] \
if q[0] != 0 \
else (p[1] + t*r[1])/q[1]
return t >= 0 and t <= 1 and u >= 0 and u <= 1
One of the solutions above worked so well I decided to write a complete demonstration program using wxPython. You should be able to run this program like this: python "your file name"
# Click on the window to draw a line.
# The program will tell you if this and the other line intersect.
import wx
class Point:
def __init__(self, newX, newY):
self.x = newX
self.y = newY
app = wx.App()
frame = wx.Frame(None, wx.ID_ANY, "Main")
p1 = Point(90,200)
p2 = Point(150,80)
mp = Point(0,0) # mouse point
highestX = 0
def ccw(A,B,C):
return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)
# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
def is_intersection(p1, p2, p3, p4):
return intersect(p1, p2, p3, p4)
def drawIntersection(pc):
mp2 = Point(highestX, mp.y)
if is_intersection(p1, p2, mp, mp2):
pc.DrawText("intersection", 10, 10)
else:
pc.DrawText("no intersection", 10, 10)
def do_paint(evt):
pc = wx.PaintDC(frame)
pc.DrawLine(p1.x, p1.y, p2.x, p2.y)
pc.DrawLine(mp.x, mp.y, highestX, mp.y)
drawIntersection(pc)
def do_left_mouse(evt):
global mp, highestX
point = evt.GetPosition()
mp = Point(point[0], point[1])
highestX = frame.Size[0]
frame.Refresh()
frame.Bind(wx.EVT_PAINT, do_paint)
frame.Bind(wx.EVT_LEFT_DOWN, do_left_mouse)
frame.Show()
app.MainLoop()
Using OMG_Peanuts solution, I translated to SQL. (HANA Scalar Function)
Thanks OMG_Peanuts, it works great. I am using round earth, but distances are small, so I figure its okay.
FUNCTION GA_INTERSECT" ( IN LAT_A1 DOUBLE,
IN LONG_A1 DOUBLE,
IN LAT_A2 DOUBLE,
IN LONG_A2 DOUBLE,
IN LAT_B1 DOUBLE,
IN LONG_B1 DOUBLE,
IN LAT_B2 DOUBLE,
IN LONG_B2 DOUBLE)
RETURNS RET_DOESINTERSECT DOUBLE
LANGUAGE SQLSCRIPT
SQL SECURITY INVOKER AS
BEGIN
DECLARE MA DOUBLE;
DECLARE MB DOUBLE;
DECLARE BA DOUBLE;
DECLARE BB DOUBLE;
DECLARE XA DOUBLE;
DECLARE MAX_MIN_X DOUBLE;
DECLARE MIN_MAX_X DOUBLE;
DECLARE DOESINTERSECT INTEGER;
SELECT 1 INTO DOESINTERSECT FROM DUMMY;
IF LAT_A2-LAT_A1 != 0 AND LAT_B2-LAT_B1 != 0 THEN
SELECT (LONG_A2 - LONG_A1)/(LAT_A2 - LAT_A1) INTO MA FROM DUMMY;
SELECT (LONG_B2 - LONG_B1)/(LAT_B2 - LAT_B1) INTO MB FROM DUMMY;
IF MA = MB THEN
SELECT 0 INTO DOESINTERSECT FROM DUMMY;
END IF;
END IF;
SELECT LONG_A1-MA*LAT_A1 INTO BA FROM DUMMY;
SELECT LONG_B1-MB*LAT_B1 INTO BB FROM DUMMY;
SELECT (BB - BA) / (MA - MB) INTO XA FROM DUMMY;
-- Max of Mins
IF LAT_A1 < LAT_A2 THEN -- MIN(LAT_A1, LAT_A2) = LAT_A1
IF LAT_B1 < LAT_B2 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A1 > LAT_B1 THEN -- MAX(LAT_A1, LAT_B1) = LAT_A1
SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A1, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 < LAT_B1 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A1 > LAT_B2 THEN -- MAX(LAT_A1, LAT_B2) = LAT_A1
SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A1, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
END IF;
END IF;
ELSEIF LAT_A2 < LAT_A1 THEN -- MIN(LAT_A1, LAT_A2) = LAT_A2
IF LAT_B1 < LAT_B2 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A2 > LAT_B1 THEN -- MAX(LAT_A2, LAT_B1) = LAT_A2
SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A2, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 < LAT_B1 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A2 > LAT_B2 THEN -- MAX(LAT_A2, LAT_B2) = LAT_A2
SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A2, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
END IF;
END IF;
END IF;
-- Min of Max
IF LAT_A1 > LAT_A2 THEN -- MAX(LAT_A1, LAT_A2) = LAT_A1
IF LAT_B1 > LAT_B2 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A1 < LAT_B1 THEN -- MIN(LAT_A1, LAT_B1) = LAT_A1
SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A1, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 > LAT_B1 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A1 < LAT_B2 THEN -- MIN(LAT_A1, LAT_B2) = LAT_A1
SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A1, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
END IF;
END IF;
ELSEIF LAT_A2 > LAT_A1 THEN -- MAX(LAT_A1, LAT_A2) = LAT_A2
IF LAT_B1 > LAT_B2 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A2 < LAT_B1 THEN -- MIN(LAT_A2, LAT_B1) = LAT_A2
SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A2, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 > LAT_B1 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A2 < LAT_B2 THEN -- MIN(LAT_A2, LAT_B2) = LAT_A2
SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A2, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
END IF;
END IF;
END IF;
IF XA < MAX_MIN_X OR
XA > MIN_MAX_X THEN
SELECT 0 INTO DOESINTERSECT FROM DUMMY;
END IF;
RET_DOESINTERSECT := :DOESINTERSECT;
END;
Digging up an old thread and modifying Grumdrig's code ...
template <typename T>
struct Point {
T x;
T y;
Point(T x_, T y_) : x(x_), y(y_) {};
};
template <typename T>
inline T CrossProduct(const Point<T>& pt1, const Point<T>& pt2, const Point<T>& pt3)
{
// nb: watch out for overflow
return ((pt2.x - pt1.x) * (pt3.y - pt2.y) - (pt2.y - pt1.y) * (pt3.x - pt2.x));
}
template <typename T>
bool SegmentsIntersect(const Point<T>& a, const Point<T>& b,
const Point<T>& c, const Point<T>& d)
{
return
CrossProduct(a, c, d) * CrossProduct(b, c, d) < 0 &&
CrossProduct(c, a, b) * CrossProduct(d, a, b) < 0;
}
if (SegmentsIntersect(Point<int>(50, 0), Point<int>(50, 100),
Point<int>(0, 50), Point<int>(100, 50)))
std::cout << "it works!" << std::endl;
I thought I'd contribute a nice Swift solution:
struct Pt {
var x: Double
var y: Double
}
struct LineSegment {
var p1: Pt
var p2: Pt
}
func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool {
if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1
if (ls2.p2.x-ls2.p1.x == 0) {
//both lines are vertical and parallel
return false
}
let x = ls1.p1.x
let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
let c2 = ls2.p1.y-slope2*ls2.p1.x
let y = x*slope2+c2 // y intersection point
return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1
}
if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2
let x = ls2.p1.x
let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
let c1 = ls1.p1.y-slope1*ls1.p1.x
let y = x*slope1+c1 // y intersection point
return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2
}
let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
if (slope1 == slope2) { //segments are parallel
return false
}
let c1 = ls1.p1.y-slope1*ls1.p1.x
let c2 = ls2.p1.y-slope2*ls2.p1.x
let x = (c2-c1)/(slope1-slope2)
return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) &&
((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x)))
//validate that x is between x1,x2 in both segments
}
Resolved but still why not with python... :)
def islineintersect(line1, line2):
i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
return False
m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
if m1 == m2:
return False
b1 = line1[0][1] - m1 * line1[0][0]
b2 = line2[0][1] - m2 * line2[0][0]
x1 = (b2 - b1) / (m1 - m2)
if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
return False
return True
This:
print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])
Output:
True
And this:
print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])
Output:
False
Related