sorting - Ordering coordinates from top left to bottom right

Question

How can I go about trying to order the points of an irregular array from top left to bottom right, such as in the image below?

Methods I've considered are:

• calculate the distance of each point from the top left of the image (Pythagoras's theorem) but apply some kind of weighting to the Y coordinate in an attempt to prioritise points on the same 'row' e.g. distance = SQRT((x * x) + (weighting * (y * y)))

• sort the points into logical rows, then sort each row.

Part of the difficulty is that I do not know how many rows and columns will be present in the image coupled with the irregularity of the array of points. Any advice would be greatly appreciated.

Answer 1

Even though the question is a bit older, I recently had a similar problem when calibrating a camera.

The algorithm is quite simple and based on this paper:

• Find the top left point: min(x+y)
• Find the top right point: max(x-y)
• Create a straight line from the points.
• Calculate the distance of all points to the line
  • If it is smaller than the radius of the circle (or a threshold): point is in the top line.
  • Otherwise: point is in the rest of the block.
• Sort points of the top line by x value and save.
• Repeat until there are no points left.

My python implementation looks like this:

#detect the keypoints
detector = cv2.SimpleBlobDetector_create(params)
keypoints = detector.detect(img)
img_with_keypoints = cv2.drawKeypoints(img, keypoints, np.array([]), (0, 0, 255), 
cv2.DRAW_MATCHES_FLAGS_DRAW_RICH_KEYPOINTS)

points = []
keypoints_to_search = keypoints[:]
while len(keypoints_to_search) > 0:
    a = sorted(keypoints_to_search, key=lambda p: (p.pt[0]) + (p.pt[1]))[0]  # find upper left point
    b = sorted(keypoints_to_search, key=lambda p: (p.pt[0]) - (p.pt[1]))[-1]  # find upper right point

    cv2.line(img_with_keypoints, (int(a.pt[0]), int(a.pt[1])), (int(b.pt[0]), int(b.pt[1])), (255, 0, 0), 1)

    # convert opencv keypoint to numpy 3d point
    a = np.array([a.pt[0], a.pt[1], 0])
    b = np.array([b.pt[0], b.pt[1], 0])

    row_points = []
    remaining_points = []
    for k in keypoints_to_search:
        p = np.array([k.pt[0], k.pt[1], 0])
        d = k.size  # diameter of the keypoint (might be a theshold)
        dist = np.linalg.norm(np.cross(np.subtract(p, a), np.subtract(b, a))) / np.linalg.norm(b)   # distance between keypoint and line a->b
        if d/2 > dist:
            row_points.append(k)
        else:
            remaining_points.append(k)

    points.extend(sorted(row_points, key=lambda h: h.pt[0]))
    keypoints_to_search = remaining_points