Find 4 points that form a square from 2D list

Question

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.

Answer 1

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.