How to search for a square in an array?

Question

Pattern recognition

It is necessary to find a square with a given edge in the picture (pixels), for example 5. I can’t figure out how myself, I can’t.
There is a string of pixels (you can also translate into a 2-dimensional array) in a string every 3 bytes - 1 pixel.
The width and height of the image are known.
You need to find a square of identical pixels. For example, I want a square with a face of 2, then I need to check 1 pixel and the next one both from below and from below, well, if 2, then it’s still possible manually, but I need it to be easy and 2 and 10 and 15 pixels.
I want to write a function where you pass the entire array of pixels from the screen and the width of the edge, and the output is the coordinate of 1 pixel of the square of the 1st color.
I hope I explained clearly.

Answer 1

I will describe for the simplest case where the square has no inclination relative to the axes and the points must be found only on the vertices of the square, and not on their faces. Each point has at least 2 X and Y coordinates The
method works very simply - all possible centers of the square to which the point may belong are found, for each of them the point is added to the list
. Then we go through all the centers and find those with exactly 4 points, and it means there is a square, they are also returned
Advantages - it works very fast, low computational complexity (DZ - calculate it for this algorithm)
Features - works only with unique points, for non-unique ones with the same coordinates, you need to write a binding and slightly modify the algorithm; There may be problems when working with floating point - this must be taken into account (how to modify the code so that everything works with them - DZ No. 2)
Also, this code does not take into account the colors of the pixels, but this can be done by first dividing the list of pixels into several lists by color or by modifying the function

def get_squares(pts, side_length):
    '''
    pts - список точек в виде кортежей (x,y)
    side_length - длина стороны квадрата
    '''

    def shift(pt, dx, dy):
        return tuple([pt[0] + dx, pt[1] + dy])

    hl = side_length / 2
    if hl == 0:
        return None  # нет квадратов со стороной 0
    dirs = ((hl, hl), (-hl, -hl), (-hl, hl), (hl, -hl),)  # направления
    pts = set(pts)  # убираем дубли точек и ускоряем 
    cs = dict()  # центры потенциальных квадратов
    for pt in pts:
        for dir in dirs:
            center = shift(pt, *dir)
            cs[center] = cs.get(center, list()) + [pt]
    squares = list(filter(lambda q: len(q) == 4, cs.values()))
    return squares
# проверка
mx=10
side_len=5
pts_cnt=500
l=list()
for i in range(pts_cnt):
    l.append((randint(0,mx),randint(0,mx)))
sq=get_squares(l,side_len)
print(sq)