Find 4 points that form a square from 2D list

user_9500955 0
Viewed 1068

I have a 2D list below:

a = [[3, 10], [7, 11], [7, 12], [8, 11], [8, 12], [12, 8], [12, 9], [13, 8], [13, 9], [14, 6], [14, 7], [15, 8], [17, 6], [18, 6]]

There are 4 points that can form a square:

[7, 11], [7, 12], [8, 11], [8, 12]

or this:

[12, 8], [12, 9], [13, 8], [13, 9]

This is my code:

def find_square(a):
    i = 0
    result = []
    while(i < len(a)):
        if a[i][0] == a[i + 1][0]:
            if a[i][1] == a[i + 2][1]:
                if a[i + 2][0] == a[i + 3][0]:
                    if a[i + 1][1] == a[i + 3][1]:
                        result.append([a[i][0] + 1, a[i][1] + 1])
                    i += 4
                else:
                    i += 3
            else:
                i += 2
        else:
            i += 1
    return result

Output:

[8, 12], [13, 9]

This code will return the last point (bottom right) of the square. I want to check if there are exist 4 points that can form a square with the side of 1 and return the bottom right point. What is a better way to implement this code?

The 2D list is assumed to be sorted in ascending order of x-coordinate.

Update:

I found a case that my code has a problem:

[7, 11], [7, 12], [7, 13], [8, 11], [8, 12]

The point [7, 13] make my code cannot detect the square.

list algorithm python
2 Answers

Well, maybe something like this:

def find_square(a):
    result = []
    for (bl, tl, br, tr) in zip(a, a[1:], a[2:], a[3:]):
        if bl[0] == tl[0] and br[0] == tr[0] and \
           bl[1] == br[1] and tl[1] == tr[1] and \
           br[0] - bl[0] == tl[1] - bl[1]:
           result.append(tr)
    return result

The names of the variables are bl for bottom left, tl for top left, br for bottom right, and tr for top right corner. On the first line of if we check the x coordinates, on the second line - check the y coordinates, on the third line we check that it's a square, not a rectangle.

UPDATED for the new condition

def find_square(a):  
    d = {}
    for p1, p2 in zip(a, a[1:]):
        if p2[0] == p1[0] and p2[1] == p1[1] + 1:
            d.setdefault(p1[1], []).append(p1[0])
    result = []
    for y, xs in d.items():
        for x1, x2 in zip(xs, xs[1:]):
            if x2 == x1 + 1:
                result.append([x2, y + 1])
    return result

Explanation: first we go through the array and look for points, which have another point just above them. If we find such a point, then we add a new value to the dictionary d. The key is a vertical coordinate, and the value will contain list of possible x coordinates. In the next loop we just go through each of these lists of x coordinates and check if the list contains two consecutive x coordinates. If it does, then we have found a square.

user_129521130

A solution that does not require the points to be consecutive, or even the list to be sorted in any way :

a = [[3, 10], [7, 11], [7, 12], [7, 13], [8, 11], [8, 12], [12, 8], [12, 9], [13, 8], [13, 9], [14, 6], [14, 7], [15, 8], [17, 6], [18, 6]]

from itertools import combinations

def is_square(points, square_side=1):
    if len(set(tuple(pt) for pt in points)) != 4:  # Some points are identical
        return False
    x_coords = sorted(set(pt[0] for pt in points))
    y_coords = sorted(set(pt[1] for pt in points))
    if not (len(x_coords) == len(y_coords) == 2):  # Points are not aligned 2 by 2 on x and on y
        return False
    # We now know we have a rectangle
    if not (x_coords[1] - x_coords[0] == y_coords[1] - y_coords[0] == square_side):
        # Not a square, or not the right size
        return False
    return True

def find_square(pts_list, square_side=1):
    result = []
    for pts in combinations(pts_list, 4):
        if is_square(pts, square_side):  # Retrieve the right point
            result.append([max(pt[0] for pt in pts), max(pt[1] for pt in pts)])
    return result

print(find_square(a, 1))

It is however in Theta(N⁴), whereas using the fact that the list is sorted by x, with only integer coordinates, and that the square size has to be 1, there is a solution in Theta(N²) at worst and even Theta(N) in average (see Alex's answer).

user_74569230
Related