查找段是否在另一个段的距离内 [英] Find if segment comes within distance of another one
问题描述
我有一堆细分市场(我拥有的数据是构成细分市场[x1，y1]和[x2，y2]的2个点)，并希望根据其位置对其进行分类.如果一个片段与另一个片段足够接近，那么我想将它们放在一起.如果我必须用句子来描述它:我想找到所有与该段的任意点相距5px的相邻段.
使用与绘制图片相似的规则:
我当时在研究不同的算法，但是大多数算法处理交点并预测线是否会相交.这对我来说真的不起作用，因为我不想将线继续延伸到无穷大，我只想知道它们是否在彼此之间的5像素之内.
有人知道我该如何解决这个问题(并且相对较快)?您知道有什么框架可以帮助您吗?(我在看最近的邻居，但是找不到任何处理几何而不是点的框架.)
谢谢！
(我修改了以前的答案.该答案有一些缺点.我认为我的新答案显示了更简单，更可靠的解决方案.)
您有两个线段，S的点为S 0 和S 1 ，T的点为T 0 和T 1 .当这些线段在某一点之间的距离小于 r 时，就会检测到碰撞.
对于线段S，您将获得方向矢量Δ s ，线段长度 s 和归一化方向矢量 u .
Δ s = S 1 -S 0
s = |Δ s |
u =Δ s / s
单位矢量 u 和点S 0 可以描述任意点P到点P'的变换:
P′ x =(P x -S 0x )·u x +(P y -S 0y )·u y
P′ y = −(P x -S 0x )·u y +(P y-S 0y )·u x
在此变换中，段S的点为:
S' 0 =(0，0)
S′ 1 =( s ，0)
对于变换后的点T' 0 和T' 1 ，y分量可以解释为到S的有符号距离.现在可以执行以下测试:
-
第一个测试是T' 0 或T' 1 在段S的 r 范围内还是在S 0 '或S 1 '的 r 半径内.如果是这样，我们很受欢迎.
-
下一个测试是两条线是否相交.仅当T' 0y 或T' 1y 的符号不同时，才会发生这种情况.如果是这样，我们很受欢迎.
-
对于最后一个测试，我们通过在T与x轴对齐的系统中将S转换为S''来反转第一个测试.然后测试转换点S'' 0 或S'' 1 之一是否在T''的 r 之内.如果是这样，我们很成功，否则就是错过.
Python代码在下面.我还更新了 JS小提琴.
注意:
-
我的旧答案中的纵向变量 a 和距离 d 实际上与此处的x'和y'相同.我认为转换更简单.
-
此解决方案仅测试(1)T点是否在距S的 r 范围内；(2)直线是否相交；以及(3)S点是否距T的距离为 r .共线线段的情况由测试(1)和(3)捕获.
-
下面的代码不处理零长度段(S 0 = S 1 或T 0 = T 1 )，但是返回非空向量作为空向量的范数似乎可以解决问题–测试(1)和(3)可以捕获这些情况.
Python代码:
导入数学上课要点:"二维空间中的点P(x，y)"def __init __(self，x，y):self.x =浮点数(x)self.y = float(y)类向量:"二维空间中的向量v(x，y)"def __init __(self，x，y):self.x = xself.y = ydef mag(self):"向量的大小"返回math.hypot(self.x，self.y)def规范(自己):"返回归一化向量或(0，0)"一个= self.mag()如果a * a<1.0e-16:返回Vector(1，0)返回Vector(self.x/a，self.y/a)def diff(p，q):"差向量(q-p)"返回向量(q.x-p.x，q.y-p.y)在(p，dx，r)内定义:"p在点(dx，0)的r内吗?"x = p.x-dxy = p.y返回x * x + y * y< = r * rdef rot(p，u):"将点p旋转到与u对齐的坐标系."返回点(p.x * u.x + p.y * u.y，-p.x * u.y + p.y * u.x)def碰撞(s，t，r):"线段s和t是否与半径r碰撞"ds = diff(s [0]，s [1])ss = ds.mag()u = ds.norm()a0 =腐烂(diff(s [0]，t [0])，u)a1 =腐烂(diff(s [0]，t [1])，u)#针对S测试T0和T1如果-r< = a0.y< = r和-r< = a0.x< = ss + r:如果a0.x<0:返回范围内(a0，0，r)如果a0.x>ss:在(a0，ss，r)之内返回返回True如果-r< = a1.y< = r和-r< = a1.x< = ss + r:如果a1.x<0:在(a1，0，r)之内返回如果a1.x>ss:在(a1，ss，r)之内返回返回True#测试路口如果a0.y * a1.y<-0.9 * r * r:a = -a0.y *(a1.x-a0.x)/(a1.y-a0.y)+ a0.x如果0< = a< = ss:返回True#针对T测试S0和S1dt = diff(t [0]，t [1])tt = dt.mag()v = dt.norm()b0 =腐烂(diff(t [0]，s [0])，v)b1 =腐烂(diff(t [0]，s [1])，v)如果0< = b0.x< = tt和-r< = b0.y< = r:返回True如果0< = b1.x< = tt和-r< = b1.y< = r:返回True返回False I have a bunch of segments (the data I have are the 2 points that makes the segment [x1,y1] and [x2, y2]) and would like to categorize them according to their position. If a segment is close enough to another one, then I want to put them together. If I had to describe it in sentence: I would like to find all neighbor segments with a distance of 5px away from any point of the segment.
With rules similar to the drawn picture:
I was looking at different algorithms but most of them deal with intersections and predict whether the lines will intersect. That does not really work for me as I don't want to continue the lines to infinity, I just want to know if they come within 5px of each other.
Does anyone knows how I can approach this problem (and relatively fast)? Do you know any frameworks that could help? (I was looking at the nearest neighbors but I cannot find any framework that deals with geometry instead of points).
Thanks!
(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
这篇关于查找段是否在另一个段的距离内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
