Algorithm to find if a triangle (with given vertices) contains a point $P$

Question

I came up with the following algorithm to find weather a given triangle contains origin or not. Applying on $1000$ test cases, I got $232$ while the correct answer is $228$. Please verify if the algorithm is mathematically valid or not.

$1$)Name the vertices $A,B,C$
$2$)Find Angle of line from origin to the point with positive $x$-Axis. Name them $\angle a,\angle b, \angle c$. This is done via $\arctan(\left|{y\over x}\right|)$.
If First quadrent, no change required.
If second quadrent, $180-\arctan(\left|{y\over x}\right|)$.
If third quadrent $270-\arctan(\left|{y\over x}\right|)$.
If fourth, then $360-\arctan(\left|{y\over x}\right|)$
$3$)Find Angle between the lines $OA,OB,OC$.
which would be min$\left(|\angle a-\angle b|,360-|\angle a-\angle b|\right)$ for $OA$ and $OB$ and so on.
$4$) If the sum of these differences is $360$, then the triangle contains origin.

The test cases do NOT contain any point on origin or the $x$ or $y$ axis.

Answer 1

you might like to try an alternative method that may be more transparent and robust.

supposing Q lies within ABC. a test probe P moving from A towards B should initially observe a decrease in the distance $PQ = r_{\lambda}$. if we parameterize the position of the probe as $$ P_{\lambda} = \lambda A + (1-\lambda) B $$

then for an internal point $Q$ we should have:

$$ \frac{d|P_\lambda Q|^2}{d\lambda}\bigg|_{\lambda= 0} \lt 0 $$

if $A = (x_1,y_1), B= (x_2, y_2), C=(x_3,y_3)$, and $Q=(x_0, y_0)$ then this test computes as:

$$ (a_2-a_1)(a_1-a_0) +(b_2-b_1)(b_1-b_0) \lt 0 $$

with similar tests for the other two sides, BC and CA, obtained by cyclic permutation.

Answer 2

Your method is totally inefficient and involves $\arctan$ function which is expensive from the computation point of view.

It's better to check angle orientations:

If the origin is in the triangle, angles $\angle AOB$, $\angle BOC$, $\angle COA$ have the same orientation.

If the origin is outside of the triangle, angles $\angle AOB$, $\angle BOC$, $\angle COA$ do not have the same orientation.

Angle orientation between vectors is reflected in the cross product. In this particular case:

$$\vec{OA}\times\vec{OB}=(x_Ay_B-x_By_A)\vec k$$ $$\vec{OB}\times\vec{OC}=(x_By_C-x_Cy_B)\vec k$$ $$\vec{OC}\times\vec{OA}=(x_Cy_A-x_Ay_C)\vec k$$

If the value between brackets is positive, the cross product is pointing upwards and the angle has counterclockwise orientation. It's exactly the opposite if the value in brackets is negative.

The algorithm would look like this:

1) Calclulate the following values:

$$z_1=x_Ay_B-x_By_A$$ $$z_2=x_By_C-x_Cy_B$$ $$z_3=x_Cy_A-x_Ay_C$$

2) If $z_1=0$ or $z_2=0$ or $z_3=0$, the origin lies on some triangle edge

3) If $z_1,z_2,z_3$ are all of the same sign, the origin is inside the triangle, outside of it otherwise.

You can probably fix your method and force it to work, but it's still too complicated, totally inefficient and hard to follow.

Also functions like $\arctan$ are for mathematicians. If you have to compute the value of it in your computer code, you should use something like atan2(). That function takes two arguments ($x$ and $y$ values) and takes care of the quadrant in question.

Answer 3

If the point is in the $3^{rd}$ quadrant, the angle it makes with the $x$ axis in the anti-clockwise direction is $180+\arctan(\Big|\frac yx\Big|)$