3
$\begingroup$

Math gurus...

I am looking for a way to tell if a line passes through a triangle as shown in the diagram below - the line described by the points p0 and p1 pass through the triangle described by the vertices v0, v1, v2:

enter image description here

I will readily admit, I don't have a clue -- so any help is appreciated as always!

$\endgroup$
13
  • 2
    $\begingroup$ You can evaluate the points $v_1,v_2,v_3$ on $f(x,y)=ax_by_c$, where $ax+by+c=0$ is the equation of the line. If there is at least one change of sign (the values of $f$ are some negative and some positive) then True, else False. $\endgroup$ – Peyton Aug 1 '17 at 2:16
  • 3
    $\begingroup$ @Peyton: Please post an answer! See this for some reasons why: math.meta.stackexchange.com/questions/1559/… $\endgroup$ – Aryabhata Aug 1 '17 at 2:20
  • $\begingroup$ Thanks guys -- its a start... and I'll do my part, but I do not have a Phd in computational-geometry, so if someone wants to show step by step calculations for a complete newbie such as myself, that would be great - as the mathematical notation (which is English to you) is greek to me!! -- but I still appreciate those that can at least kick me in the right direction ! $\endgroup$ – bdcoder Aug 1 '17 at 2:31
  • $\begingroup$ If $p_1=(x_1,y_1)$ and $p_2=(x_2,y_2)$, then the equation of the line is $(x_2-x_1)(Y-y_1)-(y_2-y_1)(X-x_1)=0$. We only care about the expression on the left-hand side. Assume that $v_1=(a_1,a_2)$, $v_2=(b_1,b_2)$, and $v_3=(c_1,c_2)$. Then plug $a_1$ where $X$ is and $a_2$ where $Y$ is. Record the sign. Do the same for $v_2, v_3$. If the results contained positive and negative values, then the line passed through the interior of the triangle. If there was a $0$ and all others were of the same sign, it passes through a vertex. $\endgroup$ – Peyton Aug 1 '17 at 2:38
  • $\begingroup$ You appear to be working in 3-D. Question 1: are you really? Question 2: If so, are all of the points known to be coplanar, or do you have an arbitrary triangle and line segment? $\endgroup$ – amd Aug 1 '17 at 6:41
3
$\begingroup$

The triangle $\Delta(v_0,v_1,v_2)$ defines a plane $\Pi$. If the line $\ell$ is not parallel to $\Pi$ it will intersect the plane in exactly one point $p$. Then we can apply three determinants $det(p,v_0,v_1)$, $det(p,v_1,v_2)$, and $det(p,v_2,v_0)$ determine the orientation (sign) and know if $p$ lies inside of $\Delta$, if so then $\ell$ intersects $\Delta$.

To calculate $p$ we can use the parametric form (Wikipedia):

$\Pi$: $v_0 + (v_1 - v_0)u + (v_2-v_0)w$

Assuming $\ell$ is defined by two points $p_0$ and $p_1$. Then we can write the point of intersection as:

$p_0 + (p_1-p_0)t = v_0 + (v_1 - v_0)u + (v_2-v_0)w$

$\Leftrightarrow p_0 - v_0 = (p_0 - p_1)t + (v_1 - v_0)u + (v_2-v_0)w$

Three equations (one for each $x$, $y$, and $z$) three unknown variables ($t$, $u$, and $w$) gives us an exact solution.

Then $p$ lies in the plane $\Pi$ and we can see the problem as $2D$ point location problem where we have to find out if $p$ lies inside of $\Delta$. Here we apply the three determines as explained above.


EDIT: Coplanarity was given later and only in the comments.

In case all points a coplanar we can simply calculate $det(p_0,p_1,v_0)$, $det(p_0,p_1,v_1)$, and $det(p_0,p_1,v_2)$. If one sign is different the line passes trough $\Delta$ otherwise it does not. (This variant was already described by another answer but as it seems it was deleted.)

$\endgroup$
7
  • $\begingroup$ Thanks, I adapted the answer. $\endgroup$ – gue Aug 2 '17 at 6:23
  • $\begingroup$ Thank-you very much for your answer (coplanar points), I ran several tests and everything seems to work. In the case where the intersection contains an edge of the triangle, it seems two of the determinants will be zero -- is that correct? I tested 5 scenarios: 1 - No intersection, 2 - Intersection at vertex, 3 - Intersection through 2 edges, 4 - Intersection contains edge, 5 - Intersection through 1 vertex and edge. $\endgroup$ – bdcoder Aug 3 '17 at 3:28
  • $\begingroup$ Yes that is correct. (The $det()$ gives the signed area (volume) which is zero in that case.) I think that are all cases that you need. $\endgroup$ – gue Aug 3 '17 at 5:30
  • $\begingroup$ while testing the case of the line through a vertex and an edge, the results contain positive, negative and a zero value. Is this another case in addition to what Peyton mentioned, ie: "If there was a 0 and all others were of the same sign, it passes through a vertex"? Looking to build a truth table with regard to the returned results (positive, negative and zero values) in order to build the logic that returns true if the line passes through the triangle or not. $\endgroup$ – bdcoder Aug 3 '17 at 16:38
  • $\begingroup$ If all determinants are strictly larger zero there is no intersection. The same for strictly smaller than zero. Otherwise, an intersection exists. Do you need to know an intersection type? $\endgroup$ – gue Aug 3 '17 at 16:52
0
$\begingroup$

Ingredients:

1) Equation of a plane determined by three points in the space.

2) Parametric equation of the line T passing through $p_0,p_1$, and of the three lines bordure of the triangle.

3) Put line T coordinates obtained in the plane equation.

4)Put you triangle inside a parallepipede L $(x_{min},x_{max})\times (y_{min},y_{max})$

The line passes through the plane if in 3) we get equation verified for any point of T.

The line T intersectes the triangle if the point of intersections of T with line bordures when they exist are in L.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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