(I have revised my previous answer. That answer hat some shortcomings. I think my new answer shows a simpler and more robust solution.)
You have two segments, S with points S0 and S1 and T with poins T0 and T1. A collision is detected when these segments are less than a distance of r apart at one point.
For the segment S, you get the direction vector Δs, the segment length s and the normalized direction vector u.
Δs = S1 − S0
s = |Δs|
u = Δs / s
The unit vector u and the point S0 can describe a transformation of any point P to a point P′:
P′x = (Px − S0x) · ux + (Py − S0y) · uy
P′y = − (Px − S0x) · uy + (Py − S0y) · ux
In this transformation the points of the segment S are:
S′0 = (0, 0)
S′1 = (s, 0)
For the transformed points T′0 and T′1, the y components can be interpreted as signed distance to S. Now several tests can be performed:
The first test is whether T′0 or T′1 are within a distance of r of the segment S or within a radius of r of either S0′ or S1′. If so, we have a hit.
The next test is whether the two lines intersect. That can only happen if the signs of T′0y or T′1y are different. If so, we have a hit.
For the last test, we reverse the first test by transforming S to S′′ in a system where T is aligned to the x-axis. Then test whether one of the transformed points S′′0 or S′′1 are within r of T′′. If so, we have a hit, otherwise it's a miss.
Python code is below. I've also updated my JS Fiddle.
Notes:
The longitudinal variable a and the distance d in my old answer were in effect the same as the x′ and y′ here. I think the transformation is simpler.
This solution tests only (1) whether the points of T are within a distance of r from S, (2) whether the lines intersect and (3) whether the points of S are within a distance of r from T. The case of collinear line segments is caught by the tests (1) and (3).
The code below does not handle zero-length segments (S0 = S1 or T0 = T1) explicitly, but returning a non-null vector as norm of a null vector seems to do the trick – tests (1) and (3) catch these cases.
Python code:
import math
class Point:
""" A point P(x, y) in 2D space
"""
def __init__(self, x, y):
self.x = float(x)
self.y = float(y)
class Vector:
""" A vector v(x, y) in 2D space
"""
def __init__(self, x, y):
self.x = x
self.y = y
def mag(self):
""" magnitude of the vector
"""
return math.hypot(self.x, self.y)
def norm(self):
""" return the normalized vector or (0, 0)
"""
a = self.mag()
if a*a < 1.0e-16:
return Vector(1, 0)
return Vector(self.x / a, self.y / a)
def diff(p, q):
""" difference vector (q - p)
"""
return Vector(q.x - p.x, q.y - p.y)
def within(p, dx, r):
""" Is p within r of point (dx, 0)?
"""
x = p.x - dx
y = p.y
return x*x + y*y <= r*r
def rot(p, u):
""" Rotate point p to a coordinate system aligned with u.
"""
return Point(p.x * u.x + p.y * u.y,
-p.x * u.y + p.y * u.x)
def collision(s, t, r):
""" Do the line segments s and t collide with a radius r
"""
ds = diff(s[0], s[1])
ss = ds.mag()
u = ds.norm()
a0 = rot(diff(s[0], t[0]), u)
a1 = rot(diff(s[0], t[1]), u)
# Test T0 and T1 against S
if -r <= a0.y <= r and -r <= a0.x <= ss + r:
if a0.x < 0: return within(a0, 0, r)
if a0.x > ss: return within(a0, ss, r)
return True
if -r <= a1.y <= r and -r <= a1.x <= ss + r:
if a1.x < 0: return within(a1, 0, r)
if a1.x > ss: return within(a1, ss, r)
return True
# Test intersection
if a0.y * a1.y < -0.9 * r * r:
a = -a0.y * (a1.x - a0.x) / (a1.y - a0.y) + a0.x
if 0 <= a <= ss: return True
# Test S0 and S1 against T
dt = diff(t[0], t[1])
tt = dt.mag()
v = dt.norm()
b0 = rot(diff(t[0], s[0]), v)
b1 = rot(diff(t[0], s[1]), v)
if 0 <= b0.x <= tt and -r <= b0.y <= r: return True
if 0 <= b1.x <= tt and -r <= b1.y <= r: return True
return False
