Parallelogram contains Point

Question

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

Answer 1

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.

Answer 2

The y coordinate is simplest, so start with that. If the y coordinate of the point is between the top and bottom of the shape, go on to the x coordinate. Calculate the x coordinate of the left and right sides of the shape at the y coordinate of the point, and check if the x coordinate of the point is between them.

Edit:

Given the four coordinates of the top left, top right, bottom right and bottom left corners:

if (y >= y1 && y <= y3) {
   var k = (x4 - x1) / (y4 - y1);
   var m = x1 - k * y1;
   if (x >= k * y + m) {
     k = (x3 - x2) / (y3 - y2);
     m = x2 - k * y2;
     if (x <= k * y + m) {
       // inside
     }
   }
}

Answer 3

See my answer to this question, which is very similar. There, I give what I think is a pretty easy test in the case that the parallelogram has one of its corners at (0,0) because it makes the explanation easier to look at, but it's not very hard to modify it to work in general.

EDIT: Since the question owner is familiar with vectors, I'll basically rewrite my answer in that language. Suppose the parallelogram is spanned by vectors PQ and PR, where P, Q, and R are corners. The symbol * will denote dot product. Pick a point q such that PQ is perpendicular to Pq (i.e. Pq*PQ=0) and PR*Pq>0 (for example, you could get q by rotating Q around P by 90 degrees). Also pick a point r such that PR*Pr=0 and PQ*Pr>0. Then a point A is in the interior if and only if (0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR).

Answer 4

My first observation about this problem is that the a rectangle (aligned with the axes) is a simple degenerate case. If two corners of that rectangle are: (x1,y1) and (x2,y2) then you simply test, given a point (x3,y3), that min(x1,x2) < x3 < max(x1,x2) and min(y1,y2) < y3 < max(y1, y3).

This might also be a useful optimization. If we find axis-aligned bounding rectangle of our parallelogram then we can start with a quick test of any given point against that.

If our parallels have non-zero slope then we compute the axis intersections of our bounding lines and the intersection of the lines that would pass through the point in question at those slopes. If both of our point's intersections (defined by both slopes) lies between our the intersections of our bounding lines then we're in. If either of this is out of those ranges then we're not.

I don't have time to code up an example but computing these slopes and intersections are first year algebra.

[Addenda]

I see now that the first post (regarding ray from the point to be tested and extending along any arbitrary slope) is a reference to the general solution to this problem for any closed planar polygon ... or, in fact, for any closed planar curve. It can also be extended to three dimensions for closed surfaces.

There is, however, one caveat that would apply to parallelograms nor to rhomboids. In the case of a concave polygon (or some other curves) if the ray hits any apex (corner) then it's possible that the test return an even number of "line" crossings. In other words any part of the "curve" which is simultaneously included in multiple "sides" of the polygon could return a false positive.

Two solutions of this would be: explicitly test for intersections at line segment limits (corner/apexes) or treat each line segment as bounded on one end by (point + epsilon) (so that our computations won't find any point in common between any two sides).

My idea of finding a bounding rectangle is still a useful quick test and does extend generally to all polygons. We find the min() and max() x to find the left and right bounding sides and the min() and and max() y to find the bottom and top bounds. This also can be extended to three dimensions ... and a friend tells me that standard graphics libraries use this extensively for collision detection in most virtual reality and MMORPGs, etc. When the find collisions in bounding boxes then they do more fine-grained computations on the polygons that are contained therein.

Answer 5

The standard equation of a line is given as ax+bx+c=0 .. but interestingly, if you take that expression ax+bx+c, and evaluate points x,y given the a,b,c for your particular line, you will find that the expression partitions the plane into two halves, one half where the expression is greater than zero, the other half where it is less.

Now, if you take the four points of your parallelogram, and compute the a,b,c coefficients for each line that makes up a side of the parallelogram, you can evaluate each expression for the x,y in question and find out which side of each line that point is on. The inside of the parallelogram will be a logical AND of particular sides.

I.e., once you have the a,b,c's for each of the four lines, you can make a test something like

if ( ((a1*x+b1*y+c1)>0) && ((a2*x+b2*y+c2)<0) && 
        ((a3*x+b3*y+c3)<0) && ((a4*x+b4*y+c4)>0) {
    // it's in!
}

.. the only remaining trick being that you have to determine the 'polarity' of each sign test, i.e., greater or less than zero. The easy way to do this is to evaluate 0,0, and see if that is on the side you want, which amounts to saying that the sign of 'c' tells you which way to test.

Admittedly, it's kind of a brute force way to do it, but it can be extended to work for any convex polygon .. or, remove a point and it works for triangles, too.

Answer 6

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 7

This paper describes a method to determine where a ray and quadrilateral intersect. It can be simplified further if the quadrilateral is a parallelogram.

If you have a parallelogram with adjacent sides described by vectors AB and AC. Any point in the plane of the parallelogram can be described by the following vector

T(a, b) = A + a * AB + b * AC

Any ray can be described as an origin O and direction D

R(t) = O + t * D

The intersection of the 2 is when T(a, b) == R(t)

O + t * D = A + a * AB + b * AC

Solve this for a and b and check that they are both between 0 and 1. See the pseudocode at the end of the paper for how to implement this.

Answer 8

If the parallelogram is convex (and given the definition of parallelogram it must be xD), then any algorithm to test if it's in its boundaries should do, you can improve efficiency unrolling the loop, because you know there are just 4 vertices, for example.

Here is a simple algorithm that tests the point being on the same side of all segments, based on the right hand rule of the vectorial product (you can optimize it also by replacing the division to normalize the vector with a simple sign test):

http://stackoverflow.com/questions/1119627/how-to-test-if-a-point-is-inside-of-a-convex-polygon-in-2d-integer-coordinates/1119673#1119673

Another option, if you're going to do lots of comparisons against the same parallelogram is to normalize it to a square, obtain the matrix that does the transformation and each time you get a point to test, multiply it by the matrix and then check if the transformed point is inside the normalized square (which should be much easier).