Iterate multi-dimensional array and search for points that form squares

Question

Part of my application is dedicated to recognizing the corners of all the object inside an image. I've found many ways to detect the corners, such as Harris corner detection and GoodFeatureToTrack. After some tests, GoodFeatureToTrack has proved to be the best solution but I'm stuck with the manipulation of the multi-dimensional array.

How can I iterate this type of array to check if inside the list of points there are four coordinates that form a square?

image = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
corners = cv2.goodFeaturesToTrack(image, 150, 0.01, 15)
corners = np.int0(corners) 
print("Points")
for corner in corners:
   x, y = corner.ravel()
   cv2.circle(image, (x, y), 5, (0, 0, 255), -1)
print(corners)

This is the actual result

Points

[[[141 265]]

[[148 176]]

[[136 360]]

[[233 358]]

[[192 218]]

[[130 465]]]

Answer 1

I wrote a function, that looks for square forming points in a list of points and returns the four points if they exist, None if not. For any two points in the list it first calculates their difference and turns this vector 90 degrees. Then it checks if either point1 + this vector and point2 + this vector or point1 - this vector and point2 - this vector are in the list and returns them if this is the case. diffRotated.any() is there just to make sure point1 and point2 are not the same.

def findSquare(points):
    for i, point1 in enumerate(points):
        for point2 in points[i+1:]:
            diffRotated = np.array([point2[1]-point1[1], point1[0]-point2[0]])
            if (diffRotated.any() and np.any(points == point1 + diffRotated) and np.any(points == point2 + diffRotated)):
                return np.array([point1, point2, point1 + diffRotated, point2 + diffRotated])
            elif(diffRotated.any() and np.any(points == point1 - diffRotated) and np.any(points == point2 - diffRotated)):
                return np.array([point1, point2, point1 - diffRotated, point2 - diffRotated])
    return None

For testing I added two entries to your list such that they form a square with two other points from your list:

points = np.array([[141, 265],
                   [148, 176],
                   [136, 360],
                   [233, 358],
                   [192, 218],
                   [130, 465],
                   [145, 167],
                   [ 94, 214]])
print(findSquare(points))
# array([[141, 265],
#        [192, 218],
#        [ 94, 214],
#        [145, 167]])
print(findSquare(points[:-1]))
# None

If you want to get all the squares you will need to modify my code and check that each square is only returned once. Also this code is not very efficient, there could be a way I haven't thought of to do this in a numpy stylish way.