0
$\begingroup$

In a 3D cartesian domain I have four points $A=(x_1,y_1,z_1)$, $B=(x_2,y_2,z_2)$, $C=(x_3,y_3,z_3)$, $D=(x_4,y_4,z_4)$, and they form a plane $ABCD$. I want to find out, if an arbitrary point $P(x,y,z)$ lies within the plane $ABCD$.

$\endgroup$
  • 2
    $\begingroup$ There are many ways to do this. Do you only want to do this for one point or will you be testing many points against a fixed quadrilateral? $\endgroup$ – amd Aug 9 '18 at 4:21
  • $\begingroup$ What will be the equation of a plane when four points are given?can you find it?If a given point lies in the plane then what will happen if you plug its co-ordinates in the equation of the plane?.....It should satisfy the equation of the plane..... $\endgroup$ – naveen dankal Aug 9 '18 at 6:58
0
$\begingroup$

Let's say you have a convex, non-self-intersecting quadrilateral defined by its vertices $\vec{q}_i = ( x_i , y_i , z_i )$, $i = 1, 2, 3, 4$.

The first three vertices $\vec{q}_1$, $\vec{q}_2$, and $\vec{q}_3$ are on a plane with normal $\vec{q}$, $$\vec{n} = \left( \vec{q}_2 - \vec{q}_1 \right) \times \left( \vec{q}_3 - \vec{q}_1 \right) \tag{1}\label{NA1}$$ at signed distance $d$ from origin (in units of $\lVert\vec{n}\rVert$), $$d = \vec{n} \cdot \vec{q}_1 = \vec{n} \cdot \vec{q}_2 = \vec{n} \cdot \vec{q}_3 \tag{2}\label{NA2}$$ If the fourth vertex $\vec{q}_4$ is coplanar with the first three points, then $\vec{n} \cdot \vec{q}_4 = d$ too. For this question to make sense, let's assume so.

If we have an arbitrary point $\vec{p} = (x , y , z)$, it lies in the plane if and only if $$\vec{n} \cdot \vec{p} = d \tag{3}\label{NA3}$$ This is the test you need to do for each arbitrary point $\vec{p}$. If it fails, the answer is "No, point $\vec{p}$ is not on the plane", and no further testing is done.

Let's say $\vec{p}$ does lie on the plane, but we want to find out whether it is inside the quadrilateral. There are many ways to do this.

We'll obviously want to do that in 2D. To do so, we could project the points to the plane, but here's the trick: we can just drop one of the three coordinates, the one with the largest magnitude in $\vec{n}$. (This way, we actually project to $yz$, $xz$, or $xy$ plane, whichever is most perpendicular to $\vec{n}$.)

(Mathematically, we can do that by multiplying the vectors by matrices $\left[\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}\right]$, $\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}\right]$, or $\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}\right]$, depending on which component of $\vec{n}$ is the largest in magnitude. In practice, we just drop the $x$, $y$, or $z$ coordinates, respectively, from all 3D vectors to transform them to 2D.)

Let's say the projected 2D coordinates are $\overline{q}_1 = ( u_1 , v_1 )$, $\overline{q}_2 = ( u_2 , v_2 )$, $\overline{q}_3 = ( u_3 , v_3 )$, $\overline{q}_4 = ( u_4 , v_4 )$, and $\overline{p} = ( u_0 , v_0 )$. If $\overline{p}$ is within the quadrilateral, it is on the same side of all four edges.

In 2D, if we have a line through $\overline{q}_1$ and $\overline{q}_2$, we can use the 2D analog of vector cross product ($(x_A , y_A)\times(x_B , y_B) = x_A y_B - y_A x_B$) to find the side $\overline{p}$ is on, based on the sign of $$(\overline{q}_2 - \overline{q}_1)\times(\overline{p} - \overline{q}_1) \tag{4}\label{NA4}$$ Note that if $\overline{p}$ is on the line, the above is zero.

Essentially, we only need to calculate $$\left\lbrace \; \begin{aligned} s_1 &= (\overline{q}_2 - \overline{q}_1)\times(\overline{p} - \overline{q}_1) = (v_1 - v_2) u_0 + (u_2 - u_1) v_0 + v_2 u_1 - u_2 v_1 \\ s_2 &= (\overline{q}_3 - \overline{q}_2)\times(\overline{p} - \overline{q}_2) = (v_2 - v_3) u_0 + (u_3 - u_2) v_0 + v_3 u_2 - u_3 v_2 \\ s_3 &= (\overline{q}_4 - \overline{q}_3)\times(\overline{p} - \overline{q}_3) = (v_3 - v_4) u_0 + (u_4 - u_3) v_0 + v_4 u_3 - u_4 v_3 \\ s_4 &= (\overline{q}_1 - \overline{q}_4)\times(\overline{p} - \overline{q}_4) = (v_4 - v_1) u_0 + (u_1 - u_4) v_0 + v_1 u_4 - u_1 v_4 \\ \end{aligned}\right. \tag{5}\label{NA5}$$ Then, if ($s_1 \le 0$, $s_2 \le 0$, $s_3 \le 0$, and $s_4 \le 0$) or ($s_1 \ge 0$, $s_2 \ge 0$, $s_3 \ge 0$, and $s_4 \ge 0$), point $\vec{p}$ is inside the quadrilateral on the plane; otherwise it is outside it.

In a computer program, you can precalculate and store the 12 quadrilateral constants ($(v_1 - v_2)$, $(v_2 - v_3)$, $(v_3 - v_4)$, $(v_4 - v_1)$, $(u_2 - u_1)$, $(u_3 - u_2)$, $(u_4 - u_3)$, $(u_1 - u_4)$, $(v_2 u_1 - u_2 v_1)$, $(v_3 u_2 - u_3 v_2)$, $(v_4 u_3 - u_4 v_3)$, and $(v_1 u_4 - u_1 v_4)$), so that you need at most 11 multiplications and 10 additions for each test with that quadrilateral (not including the 8 multiplications and 12 subtractions in the one-time precalculation). In practice, the conditional jumps (if clauses) needed tend to take more time than the calculation. In some languages like C you can rewrite the sets of four tests as counts (of how many values are less than zero, and how many greater than zero), so that only three conditional jumps get generated.

If the quadrilateral is not convex, you can use any point in polygon test for the projected point $\overline{p}$ in projected polygon $\overline{q}_i$ test.

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