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
}

Answer 2

Imagine a ray emanating from your point in one direction. If that ray crosses the lines of your shape an odd number of times, it's inside the shape. If it crosses an even number of times, it's outside the shape.

So in your program you just create an invisible line and see how often it crosses. Actionscript probably has a built in function to do this, I would imagine.

Now, if you've got a ton of objects and the point can only be in one, you can speed things up by using a Binary Space Partition to store the locations of the objects. That way, you don't have to compare your point with every single object, just the ones near it.