Ordering coordinates from top left to bottom right

Jumping on this old thread because I just dealt with the same thing: sorting a sloppily aligned grid of placed objects by left-to-right, top to bottom location. The drawing at the top in the original post sums it up perfectly, except that this solution supports rows with varying numbers of nodes.

S. Vogt's script above was super helpful (and the script below is entirely based on his/hers), but my conditions are narrower. Vogt's solution accommodates a grid that may be tilted from the horizontal axis. I assume no tilting, so I don't need to compare distances from a potentially tilted top line, but rather from a single point's y value.

Javascript below:

interface Node {x: number; y: number; width:number; height:number;}
const sortedNodes = (nodeArray:Node[]) => {
    let sortedNodes:Node[] = []; // this is the return value
    let availableNodes = [...nodeArray]; // make copy of input array
    while(availableNodes.length > 0){
        // find y value of topmost node in availableNodes. (Change this to a reduce if you want.)
        let minY = Number.MAX_SAFE_INTEGER;
        for (const node of availableNodes){
            minY = Math.min(minY, node.y)
        }
        // find nodes in top row: assume a node is in the top row when its distance from minY 
        // is less than its height
        const topRow:Node[] = [];
        const otherRows:Node[] = [];
        for (const node of availableNodes){
            if (Math.abs(minY - node.y) <= node.height){
                topRow.push(node);
            } else {
                otherRows.push(node);
            }
        }
        topRow.sort((a,b) => a.x - b.x); // we have the top row: sort it by x
        sortedNodes = [...sortedNodes,...topRow] // append nodes in row to sorted nodes
        availableNodes = [...otherRows] // update available nodes to exclude handled rows
    }
    return sortedNodes;
};

The above assumes that all node heights are the same. If you have some nodes that are much taller than others, get the value of the minimum node height of all nodes and use it instead of the iterated "node.height" value. I.e., you would change this line of the script above to use the minimum height of all nodes rather that the iterated one.

if (Math.abs(minY - node.y) <= node.height)

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