Jak sprawdzić, czy punkt leży wewnątrz trójkąta?

Dany jest trójkąt o wierzchołkach P = (x_P, y_P), Q = (x_Q, y_Q), R = (x_R, y_R). Jak sprawdzić, czy punkt (a, b) leży wewnątrz tego trójkąta? Trójkąt jest częścią wspólną trzech półpłaszczyzn: tych stron prostych, zawierających jego boki (czyli dwa wierzchołki), do których należy trzeci wierzchołek. Odpowiedz można uznać za algorytm...

Według wzoru na prostą przechodzącą przez dwa punty (podanego wyżej) piszemy równania prostych, zawierających boki trójkata:

A_Px + B_Py + C_P = 0 - prosta QR,

A_Qx + B_Qy + C_Q = 0 - prosta PR,

A_Rx + B_Ry + C_R = 0 - prosta PQ.

Dla każdego wierzchołka P, Q, R obliczamy znak wyrażenia:

(A_Px + B_Py + C_P)(A_Pa + B_Pb + C_P),

(A_Qx + B_Qy + C_Q)(A_Qa + B_Qb + C_Q),

(A_Rx + B_Ry + C_R)(A_Ra + B_Rb + C_R).

• Jeśli wszystkie te trzy wyrażenia są dodatnie, to (a, b) leży wewnątrz trójkąta PQR.
• Jeśli jedno z tych trzech wyrażeń jest równe 0, to albo trókąt jest odcinkiem, albo (a, b) leży na odpowiednim boku trójkąta.
• Jeśli żadne z tych wyrażen nie jest zerem, ale choć jedno jest ujemne, to (a, b) leży na zewnątrz PQR.