How to check if a point is inside a rectangle

A rectangle

I’ve just found this interesting question on StackExchange:

If you have a rectangle ABCD and point P. Is P inside ABCD?

The idea

The idea how to solve this problem is simply beautiful.

If the point is in the rectangle, it divides it into four rectangles:

Divided rectangle

If P is not inside of ABCD, you end up with somethink like this:

Point is outside of rectangle

You might note that the area of the four triangles in is bigger than the area of the rectangle. So if the area is bigger, you know that the point is outside of the rectangle.

Formulae

If you know the coordinates of the points, you can calculate the area of the rectangle like this:

$$A_\text{rectangle} = \frac{1}{2} \left| (y_{A}-y_{C})\cdot(x_{D}-x_{B}) + (y_{B}-y_{D})\cdot(x_{A}-x_{C})\right|$$

The area of a triangle is:
$$A_\text{triangle} = \frac{1}{2} (x_1(y_2-y_3) + x_2(y_3-y_1) + x_3(y_1-y_2))$$

Python

Please look at Jans comment. There is an error in my Python code, but I don’t have the time to correct it.
def isPinRectangle(r, P):
"""
r: A list of four points, each has a x- and a y- coordinate
P: A point
"""

areaRectangle = 0.5*abs(
#                 y_A      y_C      x_D      x_B
(r[0][1]-r[2][1])*(r[3][0]-r[1][0])
#                  y_B     y_D       x_A     x_C
+ (r[1][1]-r[3][1])*(r[0][0]-r[2][0])
)

ABP = 0.5*(
r[0][0]*(r[1][1]-r[2][1])
+r[1][0]*(r[2][1]-r[0][1])
+r[2][0]*(r[0][1]-r[1][1])
)
BCP = 0.5*(
r[1][0]*(r[2][1]-r[3][1])
+r[2][0]*(r[3][1]-r[1][1])
+r[3][0]*(r[1][1]-r[2][1])
)
CDP = 0.5*(
r[2][0]*(r[3][1]-r[0][1])
+r[3][0]*(r[0][1]-r[2][1])
+r[0][0]*(r[2][1]-r[3][1])
)
DAP = 0.5*(
r[3][0]*(r[0][1]-r[1][1])
+r[0][0]*(r[1][1]-r[3][1])
+r[1][0]*(r[3][1]-r[0][1])
)
return areaRectangle == (ABP+BCP+CDP+DAP)

Triangle

The same idea can easily be adopted to triangles:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class Point:
"""Represents a two dimensional point."""

def __init__(self, x, y):
self.x = x
self.y = y

def __get__(self, obj, cls=None):
return obj

def __repr__(self):
return "P(%.2lf|%.2lf)" % (self.x, self.y)

def __str__(self):
return repr(self)

class Triangle:
"""Represents a triangle in R^2."""

epsilon = 0.001

def __init__(self, a, b, c):
assert isinstance(a, Point)
assert isinstance(b, Point)
assert isinstance(c, Point)
self.a = a
self.b = b
self.c = c

def getArea(self):
"""Get area of this triangle.
>>> Triangle(Point(0.,0.), Point(10.,0.), Point(10.,10.)).getArea()
50.0
>>> Triangle(Point(-10.,0.), Point(10.,0.), Point(10.,10.)).getArea()
100.0
"""
a, b, c = self.a, self.b, self.c
return abs(a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y))/2

def isInside(self, p):
"""Check if p is inside this triangle."""
assert isinstance(p, Point)
currentArea = self.getArea()
pab = Triangle(p,self.a, self.b)
pac = Triangle(p,self.a, self.c)
pbc = Triangle(p,self.b, self.c)
newArea = pab.getArea()+pac.getArea()+pbc.getArea()
return (abs(currentArea - newArea) < Triangle.epsilon)

if __name__ == "__main__":
import doctest
doctest.testmod()


One Response to “How to check if a point is inside a rectangle”

1. Jan says:

Thanks for sharing your code, but I think it does not work. Examples:

>>> isPinRectangle([[0,0], [10,0], [10,10], [0,10]], [5,5])
False
>>> isPinRectangle([[0,0], [10,0], [10,10], [0,10]], [11, 11])
False

It cannot work since you do not consider the point P in your area calculation of the triangles. Here is a working implementation of the link you have posted:

import numpy as np

def areaTri(A, B, C):
#Heron’s formula
a = np.linalg.norm((B-C))
b = np.linalg.norm((C-A))
c = np.linalg.norm((A-B))
s = (a + b + c) / 2.0
return np.sqrt(s * (s-a) * (s-b) * (s-c))

def isPinRect(D, w, h, P):
#D is a list containing the x,y coordinate of the lower left corner of the rectangle
#w, h are the width and height of the rectangle
#P is a list containing the x,y coordinate of the point
A = np.array([D[0], D[1] + h])
B = np.array([D[0] + w, D[1] + h])
C = np.array([D[0] + w, D[1]])
D = np.array(D)
P = np.array(P)

areaRectangle = np.linalg.norm((A-B)) * np.linalg.norm((A-D))
areaTriangles = areaTri(A, P, D) + areaTri(D, P, C) + areaTri(C, P, B) + areaTri(P, B, A)

return (np.abs(areaRectangle – areaTriangles) >> isPinRect([0,0], 10, 10, [5, 5])
True
>>> isPinRect([0,0], 10, 10, [11, 11])
False

cheers,
jan