How would I use numpy to calculate the intersection between two line segments?
In the code I have segment1 = ((x1,y1),(x2,y2)) and segment2 = ((x1,y1),(x2,y2)). Note segment1 does not equal segment2. So in my code I’ve also been calculating the slope and y-intercept, it would be nice if that could be avoided but I don’t know of a way how.
I’ve been using Cramer’s rule with a function I wrote up in Python but I’d like to find a faster way of doing this.
Advertisement
Answer
Stolen directly from https://web.archive.org/web/20111108065352/https://www.cs.mun.ca/~rod/2500/notes/numpy-arrays/numpy-arrays.html
JavaScript
x
39
39
1
#2
# line segment intersection using vectors3
# see Computer Graphics by F.S. Hill4
#5
from numpy import *6
def perp( a ) :7
b = empty_like(a)8
b[0] = -a[1]9
b[1] = a[0]10
return b11
12
# line segment a given by endpoints a1, a213
# line segment b given by endpoints b1, b214
# return 15
def seg_intersect(a1,a2, b1,b2) :16
da = a2-a117
db = b2-b118
dp = a1-b119
dap = perp(da)20
denom = dot( dap, db)21
num = dot( dap, dp )22
return (num / denom.astype(float))*db + b123
24
p1 = array( [0.0, 0.0] )25
p2 = array( [1.0, 0.0] )26
27
p3 = array( [4.0, -5.0] )28
p4 = array( [4.0, 2.0] )29
30
print seg_intersect( p1,p2, p3,p4)31
32
p1 = array( [2.0, 2.0] )33
p2 = array( [4.0, 3.0] )34
35
p3 = array( [6.0, 0.0] )36
p4 = array( [6.0, 3.0] )37
38
print seg_intersect( p1,p2, p3,p4)39