Algorithm to determine if a point is inside a square with mathematics (no hit test involved)

In the making of a game I am currently developing, I run into the problem of determining whether a point is inside or outside of a square.

And obviously the square can have any size and rotation. This task, which can be solved really quickly if you can rely on hit test, can become a nightmare if you try any other king of approach.

Some of you may suggest to use the ray casting algorithm, but when it comes a situation like “point in a square” it can also be done with some simple mathematics.

Look at this picture:

Given a square ABCD and a point P, we first need to build four triangles: ABP, BCP, CDP and DAP.

Now it’s time to determine the area of each triangle, and this may sound complicate unless you look at this picture:

We start by calculating the area of the rectangle which surrounds the triangle:

Area of Rectangle = (Bx-Ax)*(By-Cy) = BxBy-BxCy-AxBy+AxCy

Now, if we subtract from the area of the rectangle the areas of the three triangles called AB, BC and AC, we will get the area of the main triangle.

Area of triangle AB = (Bx-Ax)*(By-Ay)/2

Area of triangle BC = (Bx-Cx)*(By-Cy)/2

Area of triangle AC = (Cx-Ax)*(Ay-Cy)/2

Probably die hard mathematicians will be a bit upset at this time, because we could get negative areas, and the area of a triangle can’t be negative. That’s why mathematicians shouldn’t code, and you’re about to see why.

Let’s find the sum of the area of the three triangles:

AB+BC+AC = (BxBy-BxAy-AxBy+AxAy+BxBy-BxCy-CxBy+CxCy+CxAy-CxCy-AxAy+AxCy)/2

which can be simplified to:

BxBy+(-BxAy-AxBy-BxCy-CxBy+CxAy+AxCy)/2

Subtracting this area to the area of the rectangle will give us the area of the main triangle

Main triangle area = Area of Rectangle – Area of triangle AB – Area of triangle BC – Area of triangle AC

This means

Main triangle area = BxBy-BxCy-AxBy+AxCy-BxBy-(-BxAy-AxBy-BxCy-CxBy+CxAy+AxCy)/2

which can be simplified to:

(-BxCy-AxBy+AxCy+BxAy+CxBy-CxAy)/2

and also be written this way:

((CxBy-BxCy)-(CxAy-AxCy)+(BxAy-AxBy))/2

This is the final formula we need to calculate each of the four triangles ABP, BCP, CDP and DAP you can see in the first picture.

What’s now?

If the area of one (or more) triangles has a different sign than the other ones, the point is outside the square. If all triangle areas have the same sign, the point is inside the square.

Obviously, you can even omit the division by two, since it does not affect the sign of the area.

If you are able to get square corners in the same direction, such as clockwise or counter-clockwise, you will just have to check if the areas are all respectively negative or positive.

Look at this script:

It applies this logic to calculate triangle area (lines 44-46) and determine if a point is inside a square (lines 47-52).

And this is the result:

Move the mouse and the square will turn red when the pointer is inside of it. Click to generate another random square.

Download the source code.

  • Viktor

    Nice one Emanuele, but I am more interested in finding out if a point is inside a random polygon (convex / concave). Advices?

  • Woah! I would never thought of that, thanks for sharing this, this is gonna be very useful

  • If in a rectangle, you can use built-in functions :

    new Rectangle(0, 0, 100, 100).containsPoint(new Point(-10, -10))

  • Emanuele Feronato

    @Viktor: I am afraid you have to use ray casting

    @y_nk: what if the rectangle rotates?

  • Very cleverly done :) This is probably why programmers should learn more math than they would like to :P Math ftw!

    Thank you for sharing!

  • Ferret

    I imagine you would just rotate the point around the same axis the rectangle was rotated, then pass the new coordinates to the containsPoint() function

  • I think a better and quick way to do this, for any RECTANGLE, is rotate the corners and check the horizontal and vertical sides.

  • @Ferret, @Rogerup rotation would be a lot more expensive then just a few * and some +-.

  • Pingback: ????????????????? | Flash?????()

  • It is a very clever and clear way to go around this.

    Thank you for sharing!

  • @Victor “I am more interested in finding out if a point is inside a random polygon (convex / concave). Advices?”

    How about floodfill the polygon and check if the point changed its color ?

  • Spoky white

    That a very creative way to do the check a point inside the box, Is there a way to check a line form by 2 points touching the box. Example, the 2 points are outside the box but the line cut the through the box? Thanks.

  • David

    How does this compare to raycasting in terms of speed?

  • Ravi

    find the distance of the point from each vertex of the square. if two or more of these distance is greater than the sqaure edge the point is outside..

  • uh

    The math is neat, but this is a more expensive calculation. What problem is being solved by doing this? For fun fine, for making a game, use a raycast and be done with it… and why call it every frame, doubtful need to do that as well.

  • FP

    I find the bayocentric technique better (http://www.blackpawn.com/texts/pointinpoly/default.html)

    just change…

    float u1 = u – 1;
    float v1 = v – 1;
    return ((u >= 0) && (v >= 0) && (u + v < 1)) || ((u1 < 0) && (v1 -1));

  • FP

    return ((u >= 0) && (v >= 0) && (u + v < 1)) || ((u1 < 0) && (v1 < 0) && (u1 + v1 > -1));

    (ate my last part because of <)

  • Basavaraj

    Hi,

    I did not understand drawSquare(…) method constants like 150, 320, 240 etc. Please explain.

  • Pingback: Check whether touched Point lies inside given area or not | BlogoSfera()

  • Pingback: ?Canvas???????????????? - ?????? « ????TV??()

  • Red

    This algorithm even though very easy to implement and also to understand is extremely prone to errors due to rounding errors. You have to compute the surfaces of maximum 4 triangles and sum those together. Based on the size of these triangles you can get not what you’ve expect.