Finding the intersection of line segment and a cluster of p points I have $p (>2)$ points $x_1, x_2,\ldots,x_p \in \mathbb{R}^N$ and $y_1,y_2 \in \mathbb{R}^N$. How to test whether the line segment connecting $y_1,y_2$ pass through the cluster formed by the $p$ points $x_1,x_2,\ldots,x_p$?
 A: Given your clarifications, a procedure for $N=3$ would be:

*

*Find the center $y_0$ and radius $R$ of the cluster sphere in the manner you describe.


*Check if one or both endpoints of the line segment is within the sphere. I.e. check if $|y_1-y_0|\le R$ or $|y_2-y_0|\le R$. If this is the case, you have a "pass through". Otherwise both endpoints are outside the sphere and furher checks are needed.


*Check if the shortest distance from $y_0$ to the line through $y_1$ and $y_2$ is $\le R$. This distance is given by the formula (see here):   $$d=\frac{|(y_0-y_1)\times (y_0-y_2)|}{|y_2-y_1|}$$
If $d \le R$ then you may have a "pass through", otherwise you don't.


*Though the line through $y_1$ and $y_2$ passes through the sphere it may be that no part of the line segment connecting $y_1$ and $y_2$ is within the sphere. It is therefore necessary to check if the point on the line with the shortest distance, calculated above, is on the line segment. This can be done using the formula (see link above): $$t=-\frac{(y_1-y_0) \cdot (y_2-y_1)}{|y_2-y_1|^2}$$
where $t$ is used in the parameterization of the line through $y_1$ and $y_2$. If $0 \lt t \lt 1$ then you have a pass through, otherwise you don't.
Hope this helps.
