Coding Challenge — Rectangle Rotation: a geometrical approach

Tautvydas Strioga
4 min readJan 3, 2021

--

A few days ago I found a coding challenge called Rectangle Rotation. Here I would like to share my approach to solving this challenge. Of course, one could solve it using a different method, but I believe that my method is great for those who like geometry and its implementation using Python.

Challenge description

A rectangle with sides equal to even integers a and b is drawn on the Cartesian plane. Its center (the intersection point of its diagonals) coincides with the point (0, 0), but the sides of the rectangle are not parallel to the axes; instead, they are forming 45 degree angles with the axes.

How many points with integer coordinates are located inside the given rectangle (including on its sides)?

Example

For a = 6 and b = 4, the output should be
rectangleRotation(a, b) = 23.

The following picture illustrates the example, and the 23 points are marked green.

Rectangle rotation. Source CodeSignal.
Rotated rectangle. Source CodeSignal.

My solution using Python

My approach to solving this challenge is plain geometrical. To begin with, I took an initial rectangle centered at the point (0, 0) and coordinates of its vertices.

# initial rectangleA = (-a / 2, b / 2)
B = (a / 2, b / 2)
C = (a / 2, -b / 2)
D = (-a / 2, -b / 2)
rectangle = [A, B, C, D]

Then I performed a rotation in Euclidean space using a rotation matrix:

Rotation matrix.

And made a rotation by 45 degrees counterclockwise by calculating vertices of the rotated rectangle:

Rectangle rotation on a plane with standard coordinates x, y, angle θ with respect to the x-axis about the origin of a two-dimensional Cartesian coordinate system.
Rectangle rotation example.
# rotate rectangle by 45 degreecos = sin = 2 ** (1 / 2) / 2
rectangleRot = []
for r in rectangle:
rt = (r[0] * cos - r[1] * sin, r[0] * sin + r[1] * cos)
rectangleRot.append(rt)

After I made the rotation I found vertices of the outer rectangle that encompasses both initial and rotated rectangles. These values of x and y of the outer rectangle will be my coordinate ranges for points to check if it is inside my rotated rectangle.

# vertices of outer rectanglexA = rectangleRot[0][0]
yB = rectangleRot[1][1]
xC = rectangleRot[2][0]
yD = rectangleRot[3][1]

To check if a point is inside a rectangle I choose the method of calculating the sum of areas as described in this example:

To calculate the area of a triangle given the coordinates of the three vertices I used this formula:

Area of the triangle where Ax and Ay are the x and y coordinates of the point A etc.

In Python this method would be like this:

def calculateRectangleArea(A, B, C):
s = (A[0] * (B[1] - C[1]) + B[0] * (C[1] - A[1]) + C[0] * (A[1] - B[1])) / 2
return abs(s)

Then we check if the sum of the areas of triangles connecting point of interest (x, y) is equal to the area of the rectangle a*b. If so, we add it to the variable count :

# iterate over outer rectangle pointsfor x in range(round(xA), round(xC) + 1):
for y in range(round(yD), round(yB) + 1):
# calculate areas of rectangles with each point area1 = calculateRectangleArea(rectangleRot[0], rectangleRot[1], (x, y))
area2 = calculateRectangleArea(rectangleRot[1], rectangleRot[2], (x, y))
area3 = calculateRectangleArea(rectangleRot[2], rectangleRot[3], (x, y))
area4 = calculateRectangleArea(rectangleRot[3], rectangleRot[0], (x, y))
# inside if areas are equal
if abs(sum([area1, area2, area3, area4]) - a * b) < 1e-10:
count += 1

Finally, here is the full code:

Conclusion

This was my approach to solving this challenge. I took a geometrical approch mainly because I prefer to apply geometrical thinking for geometrical objects. And I was quite surprised by how it nicely implements using Python.

Finally, I agree that this is not the best solution for this challenge but I was inspired to present my approach to this problem by reading Shaw's article here:

--

--

No responses yet