给定两个三维点和另一个三维点列表,我想检查圆柱体中的哪个点定义为半径为r的两个点之间的三维线。
我已经实现了一个数值解决方案,它不准确,速度太慢:
def point_in_cylinder(pt1, pt2, points, r, N=100):
dist = np.linalg.norm(pt1 - pt2)
ori = (pt2 - pt1) / dist
line = np.array([pt1 + ori*t for t in np.linspace(0, dist, N)])
dists = np.min(cdist(line, points), 0)
return np.where(dists <= r)[0]
我相信有更好的解决办法。。。
*****编辑*****
我通过用矩阵乘法替换listcomp(在声明行的地方)稍微加快了这个函数的速度:
line = (pt1.reshape(3, 1) + elc_ori.reshape(3, 1) @ np.linspace(0, dist, N).reshape(1, N)).T
最佳答案
(据我的理解),你正在创建一个离散的(相当大的)圆柱体内部均匀间隔点的列表,然后检查测试点到一个轴向点的最小距离是否在圆柱体的半径内。
这是缓慢的,因为每一个测试都有复杂性O(N)
,当它可以在O(1)
中完成(参见后面)。但最重要的是:
这是不准确的,因为你测试的空间区域没有填满整个气缸!
下图说明了原因(请原谅质量问题):
正如你所看到的,圆柱体表面附近的空白区域在测试中给出了假阴性为了减少这种不精确性,您需要增加N
,这反过来会降低算法的效率。
[即使使用(理论上)无限个点,测试区域仍会收敛到胶囊,而不是整个圆柱体。]O(1)
方法是:
给定测试点q
,检查:
这将确认q
位于圆柱体两个圆形面的平面之间。
下一步检查:
这将确认q
位于圆柱体的曲面内。
编辑:尝试在numpy中实现(如果有错误,请告诉我)
def points_in_cylinder(pt1, pt2, r, q):
vec = pt2 - pt1
const = r * np.linalg.norm(vec)
return np.where(np.dot(q - pt1, vec) >= 0 and np.dot(q - pt2, vec) <= 0 \
and np.linalg.norm(np.cross(q - pt1, vec)) <= const)