1
$\begingroup$

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!

3 Answers 3

2

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$
  • 0
    great, thank you very much!2011-09-01
1

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$.

  • 0
    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.2011-08-31
0

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$