我有一堆段（我拥有的数据是构成段 [x1,y1] 和 [x2, y2] 的 2 个点），并且想根据它们的位置对它们进行分类。如果一个片段与另一个片段足够接近，那么我想将它们放在一起。如果我必须用一句话来描述它：我想找到距线段任何点 5px 距离的所有相邻线段。
With rules similar to the drawn picture:
我正在研究不同的算法，但大多数算法都处理交叉点并预测线条是否会相交。这对我来说并不起作用，因为我不想将线条无限延伸，我只想知道它们是否彼此相距 5 像素以内。
有谁知道我如何解决这个问题（并且相对较快）？您知道有什么可以提供帮助的框架吗？ （我正在查看最近的邻居，但我找不到任何处理几何而不是点的框架）。
Thanks!
（我修改了之前的答案。这个答案有一些缺点。我认为我的新答案显示了一个更简单、更强大的解决方案。）
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.
对于线段 S，您可以得到方向向量 Δs, 段长度s和归一化方向向量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
在这个变换中，线段 S 的点是：
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 代码如下。我也更新了我的JSFiddle https://jsfiddle.net/fe348pkn/.
Notes:
纵向变量a和距离d在我的旧答案中，实际上与此处的 x′ 和 y′ 相同。我觉得转型比较简单。
该解决方案仅测试 (1) T 的点是否在距离r根据 S，(2) 直线是否相交以及 (3) S 的点是否在距离r来自 T。共线线段的情况由测试（1）和（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代码：
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