algorithmtime-complexitydynamic-programming

Function to find largest area of a rectangle possible (NOT neccessarily axis parallel) from a list of points

Input: 2d array of points ((x, y), (x2, y2), ...)
Output: area of largest possible rectangle that has its 4 corners as 4 of the points given.

Note: the rectangle does not have to be parallel to any axis, at least one rectangle is possible to make with the set of points

Example 1:
Input: [[1,2], [2,1], [1,0], [0,1]]
Output: 2
Explanation:
the rectangle looks like this on a 2d plane:

2   x
1 x   x
0   x
  0 1 2

The side lengths are sqrt(2) each and so the area is 2.

Example 2:
Input: [[0,1], [2,1], [1,1], [1,0], [2,0]]
Output: 1

Explanation:
The plane:

2
1 x x x
0   x x
  0 1 2

The only possible rectangle is a square with sides length 1 so the area is 1.

I would appreciate any help on solving this problem, honestly I have no clue how to make it more efficient. Is it even possible?

I tried bruteforcing it, i.e checking all possible combinations of 4 points to see if they make a rectangle, then comparing their areas, but it is wayy too slow for large inputs...

Solution

  • A few algorithms in decreasing order of naiveté.

    Most-naive bruteforce: iterate on quadruplet of points, n^4

    Slightly-less-naive bruteforce: iterate on triplets of points, n^3

    Because your points all have integer coordinates, calculations are exact. Given three points a, b, c, you can calculate directly the coordinates of the only point d such that a,b,c,d is a rectangle, and check whether d is one of the points in the input list of points.

    To check efficiently whether a point is in the list, you should start by building a hashtable from the list, so that this membership check is O(1). In python this is done using set().

    n^2 solution: searching for parallelograms by building a table of vectors

    A quadrilateral a,b,c,d is a parallelogram if and only if the two vectors b-a and d-c are equal, ie if opposite sides ab and dc are parallel and have the same length.

    A parallelogram a,b,c,d is a rectangle if and only if the two vectors c-a and d-b are orthogonal, ie iff the diagonals cross at a right angle.

    This suggests a pseudo-n^2 algorithm: build a hashtable that maps vectors to the list of pairs of points that make this vector. Then iterate over every vector that corresponds to at least two distinct pairs of points, and check whether the corresponding parallelogram is a rectangle.

    from itertools import combinations

class Point(tuple):
    def __add__(self, v):  # point + vector == point
        return Point(x + y for x,y in zip(self, v))
    def __sub__(self, b):  # point - point == vector
        return Vector(x - y for x,y in zip(self, b))
    def __rsub__(self, a): # point - point == vector
        return Point(a).__sub__(self)

class Vector(tuple):
    def __add__(self, v):  # vector + vector == vector
        return Vector(x + y for x,y in zip(self, v))
    def __sub__(self, v):  # vector - vector == vector
        return Vector(x - y for x,y in zip(self, b))
    def __matmul__(self, v):  # dot product: vector @ vector == scalar
        return sum(x * y for x,y in zip(self, v))

def area(a, b, c, d):
    ux, uy = b - a
    vx, vy = d - a
    return abs(ux * vy - vx * uy)  # cross product


def build_vector_table(points):
    table = {}
    for a, b in combinations(points, 2):
        if (b - a)[0] < 0 or (b - a)[0] <= 0 and (b - a)[1] <= 0:
            (a, b) = (b, a)  # Consider only vector ab or ba so that the vector is facing rightwards
        table.setdefault(b - a, []).append((a, b))
    return table

def find_largest_rectangle(points):
    table = build_vector_table(points)
    best_area = 0
    best_rectangle = None
    for v, l in table.items():
        if len(l) >= 2:
            for (a, b), (c, d) in combinations(l, 2):
                if (d - a) @ (c - b) == 0:  # dot product == 0 iff orthogonal
                    if area(a, b, d, c) > best_area:
                        best_area = area(a, b, d, c)
                        best_rectangle = (a, b, d, c)
    return best_area, best_rectangle

examples = [
    [[1,2],[2,1],[1,0],[0,1]],
    [[0,1],[2,1],[1,1],[1,0],[2,0]]
]
examples = [[Point(a) for a in l] for l in examples]

def main():
    for points in examples:
        best_area, best_rectangle = find_largest_rectangle(points)
        print(points)
        # print(build_vector_tables(points))
        print('    best area: ', best_area)
        print('    rectangle: ', best_rectangle)
        print()

if __name__ == '__main__':
    main()

# [(1, 2), (2, 1), (1, 0), (0, 1)]
#     best area:  2
#     rectangle:  ((1, 2), (2, 1), (1, 0), (0, 1))
# 
# [(0, 1), (2, 1), (1, 1), (1, 0), (2, 0)]
#     best area:  1
#     rectangle:  ((1, 1), (2, 1), (2, 0), (1, 0))

    Note that this algorithm is mostly equivalent to the algorithm described in MattTimmermans' answer. However: