Parallelogram contains Point

Question

What way is the fastest of deciding whether a point is inside a parallelogram/rhomboid?

Answer 1

Hi again and thanks for all your answers. In the meantime I myself have come up with something that I think would be rather fast:

Imagine we have a parallelogram that is spanned by PQ and PR, where PQ and PR are vectors (P, Q and R are corners). Furthermore we have the point we want to check called A.

We know that the Vector PA can be split into two vectors parallel to PQ and PR:

PA=n*PQ+m*PR

Now we know that n and m MUST be in the interval [0; 1], we solve n and m:

n = -det(PA, PQ)/det(PQ, PR)
m = det(PA, PR)/det(PQ, PR)

Where det(PA, PQ) is the determinant of the vectors PA and PQ:

det(PA, PQ) = PA.x*PQ.y-PQ.x*PA.y

If the point A is inside the parallelogram then 0<=n<=1 and 0<=m<=1, this gives us the pseudocode:

var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
    //inside
}
else
{
    //outside
}