Coding Challenge — Rectangle Rotation: a geometrical approach
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
andb
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 forming45
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
andb = 4
, the output should berectangleRotation(a, b) = 23
.The following picture illustrates the example, and the
23
points are marked green.
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:
And made a rotation by 45 degrees counterclockwise by calculating vertices of the rotated rectangle:
# 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:
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])) / 2return 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: