How to check if a 3D point is inside a cylinder

Question

Given two 3d points and another list of 3d points, I want to check which one is inside the cylinder defined as the 3d line between the two points with a radius of r. I've implemented a numeric solution for that, which isn't accurate and too slow:

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]

I'm sure there is a better solution for that...

***** Edit *****

I speed up this function a little bit by replacing the listcomp (where the line is declared) with matrices multiplication:

line = (pt1.reshape(3, 1) + elc_ori.reshape(3, 1) @ np.linspace(0, dist, N).reshape(1, N)).T

Answer 1

(To my understanding) You are creating a discrete (and quite large) list of uniformly spaced points inside the cylinder on its axis, then checking if the minimum distance of the test point to an axial point is within the radius of the cylinder.

---

This is slow because each of these tests has complexity O(N), when it can be done in O(1) (see later). But most importantly:

It is inaccurate because the region of space which you are testing against does not fill the entire cylinder!

The diagram below illustrates why (please forgive the bad quality):

As you can see the white spaces near the surface of the cylinder give false negatives in the tests. To reduce this inaccuracy you would need to increase N, which would in turn make the algorithm less efficient.

[Even if you were to use a (theoretically) infinite number of points, the test region would still converge to a capsule, not the entire cylinder.]

---

An O(1) method would be:

• Given a test point q, check that:

  

  This will confirm that q lies between the planes of the two circular facets of the cylinder.

• Next check that:

  

  This will confirm that q lies inside the curved surface of the cylinder.

---

EDIT: an attempt at implementing in numpy (please let me know if there is an error)

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)