0
$\begingroup$

I have three points (A, B, C) in a 3d space that define an angle like this:

I need a fast way to know if another point D (that I already know is coplanar with the plane ABC) lies within the angle formed by <ABC.

$\endgroup$
1
$\begingroup$

You can express vector AD as a linear combination of AB and AC. If the coefficients of the linear combination are both positive, then D is inside the angle.

So basically, you are solving the system of equations (3 equations, 2 unknowns):

$ \left[\begin{array}{rr|r} b_x-a_x & c_x-a_x& d_x-a_x \\ b_y-a_y & c_y-a_y& d_y-a_y \\ b_z-a_z & c_z-a_z& d_z-a_z \\ \end{array}\right] $

which represent the following equations:

$ (b_x-a_x) \times I + (c_x-a_x) \times J = d_x-a_x \\ (b_y-a_y) \times I + (c_y-a_y) \times J = d_y-a_y \\ (b_z-a_z) \times I + (c_z-a_z) \times J = d_z-a_z \\ $

and if your solution vector has positive components ($I>0, J>0$), then D is inside that angle. If there is no solution, then D is not in the ABC plane.

$\endgroup$
  • $\begingroup$ Shouldn't that be $d_y-a_y$ and $d_z-a_z$ on the right side? $\endgroup$ – almosnow Oct 8 '15 at 18:57
  • $\begingroup$ Yeah, my bad. I've fixed the typo, thanks! $\endgroup$ – jh314 Oct 8 '15 at 19:00
  • $\begingroup$ I really don't know how to solve that... shame... I know D is in the plane, so there exists a solution, but how would I arrive to that, IDK... I'm not used to that notation. $\endgroup$ – almosnow Oct 8 '15 at 19:01
  • $\begingroup$ I've added the 3 basic equations, now you just have to solve for I and J. $\endgroup$ – jh314 Oct 8 '15 at 19:23
  • $\begingroup$ Oh ok, now I see, thanks! $\endgroup$ – almosnow Oct 8 '15 at 19:25
2
$\begingroup$

Precompute $v = C - A$, and let $w = (-v_y, v_x)$. Then $D$ is on the right side of $AC$ if and only iff $(D - A) \cdot w > 0$. A similar construction tells you whether $D$ is on the upper side of $AB$. So in that case, you need to check $(D-A) \cdot w' < 0$. If you pass both those tests, then $D$ is in the wedge.

(This assumes that $B$ is on the 'right side" of $AC$, i.e., $(B- A) \cdot w > 0$. If that's not the case, you need to swap $B$ and $C$.).

$\endgroup$
  • $\begingroup$ How would you do that in 3D? I'm curious because of $w = (-v_y, v_x)$ $\endgroup$ – almosnow Oct 8 '15 at 18:47
  • 1
    $\begingroup$ Ah...we're in 3-space. Then let $n = (C - A) \times (B - A)$, and let $w = n \times (C - A)$ and $w' = n \times (B - A)$. Then, if you're applying this to many points $D$, you have only two dot products to compute, rather than trying to solve a degenerate $3 \times 3$ system of equations as you need to do in @jh314's solution. $\endgroup$ – John Hughes Oct 9 '15 at 0:06
  • $\begingroup$ Thank you @John Hughes. I will try out this method as it would be faster and easier to implement. $\endgroup$ – almosnow Oct 11 '15 at 3:32
1
$\begingroup$

Project the points onto one of the coordinate planes and test $$ AC \times AD > 0 \text{ and } AD \times AB > 0 $$ (use the projected points here; $\times$ is the 2D cross product, a number)

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