# Line/Plane intersection : in high dimension

I have 3 points in $R^d$ defining a triangle, and 2 points (still in $R^d$) defining a line. I would like to compute the intersection of this line and the triangle (or at least the plane defined by this triangle). I know for $d=3$, but have no clue in higher dimension since I cannot define a normal vector.

Thanks!

-

As Henning says, they most likely won't intersect. The co-dimension of a $2$-d plane in $\mathbb{R}^d$ is $d-2$ and the co-dimension of a $1$-d line is $d-1$. The typical intersection adds the co-dimensions, so the intersection has co-dimension $2d-3$. In $\mathbb{R}^3$, the typical intersection (without everything lying in a lower dimension subspace) would have co-dimension $3$, that is a point.

Consider two $2$-d planes in $\mathbb{R}^4$. Both have co-dimension $2$ and so their typical intersection would have co-dimension $4$, that is a point. If two planes intersect in a point, it is easy to believe that a plane and a line usually don't intersect.

To check if the plane and the line happen to lie in the same $3$ dimensional subspace, take one of the $5$ points, $P$, and subtract it from the other $4$ to get $4$ vectors. Create a $4{\times}\mathrm{d}$ matrix, $R_4$, with these vectors as rows and compute the determinant of the $4{\times}4$ matrix $R_4R_4^T$. If that determinant is not $0$, the line and triangle do not lie in the same $3$-d subspace and so they don't intersect. If the determinant is $0$, then take $3$ of the $4$ vectors and create a $3{\times}\mathrm{d}$ matrix, $R_3$, with these vectors as rows. If $\det(R_3R_3^T)=0$, pick another $3$. If all choices give a $0$ determinant, then all $5$ points live in a $2$-dimensional subspace and that can be handled in a similar fashion. To find a point of intersection,

1. map all points to $\mathbb{R}^3$ with $x\mapsto R(x-P)$
2. find the intersection as usual in $\mathbb{R}^3$
3. map the intersection back to $\mathbb{R}^d$ with $x\mapsto R^T(RR^T)^{-1}x+P$
-
Thanks. As I commented above, I have in fact a whole triangulated surface for which I'd like to check for self intersections (hence I compute triangle/triangle intersections, involving triangle/edge intersections). My surface is originally embedded in $R^3$, but I compute a transformation which takes the vertices of the triangulation from $R^3$ to $R^d$. The original surface in $R^3$ may self-intersect (or not), and I'd like to check whether it is the case in $R^d$. I guess it is unlikely that it happens, but I'd like to be sure. –  WhitAngl Aug 31 '11 at 23:53
@WhitAngl: I have appended a method for determining if the intersection is possible and then finding the intersection. –  robjohn Sep 1 '11 at 2:30
great, thank you very much! –  WhitAngl Sep 1 '11 at 11:00

In higher dimensions the line and the plane only intersect at all if you're lucky enough that the five original points lie in a common 3-dimensional hyperplane. In the general case they will simply miss each other, like two skew lines in $\mathbb R^3$.

-
Thanks for the answer! In fact I have a whole surface that I have triangulated and ultimately check for self intersections. I'd like to really check whether my 2d-mesh-in-Nd self intersects, even if it is unlikely. –  WhitAngl Aug 31 '11 at 23:23

If your triangle is $ABC$, the plane it is in is $A+b(B-A)+c(C-A)$. Similarly if the line segment is $DE$, the line is $D+e(E-D)$. You can write these out componentwise and you have $d$ equations in $3$ unknowns. If there is a solution, you can check whether it is within the finite figures by $0\le e \le 1, 0 \le b \le 1, 0 \le c \le 1-b$

-