Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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$
share|improve this answer
    
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$.

share|improve this answer
    
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$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.