Sort a list of points in row major snake scan order

Question

I have a list of points that represent circles that have been detected in an image.

[(1600.0, 26.0), (1552.0, 30.0), (1504.0, 32.0), (1458.0, 34.0), (1408.0, 38.0), (1360.0, 40.0), (1038.0, 54.0), (1084.0, 52.0), (1128.0, 54.0), (1174.0, 50.0), (1216.0, 52.0), (1266.0, 46.0), (1310.0, 46.0), (1600.0, 74.0), (1552.0, 76.0), (1504.0, 82.0), (1456.0, 80.0), (1406.0, 88.0), (1362.0, 86.0), (1310.0, 90.0), (1268.0, 94.0), (1224.0, 96.0), (1176.0, 98.0), (1128.0, 100.0), (1084.0, 100.0), (1040.0, 100.0), (996.0, 102.0), (992.0, 62.0), (950.0, 60.0), (950.0, 106.0), (908.0, 104.0), (904.0, 64.0), (862.0, 66.0), (862.0, 110.0), (820.0, 108.0), (816.0, 62.0), (776.0, 112.0), (774.0, 66.0), (732.0, 112.0), (730.0, 68.0), (686.0, 108.0), (684.0, 64.0), (642.0, 66.0), (600.0, 70.0), (600.0, 112.0), (558.0, 112.0), (552.0, 64.0), (512.0, 66.0), (510.0, 112.0), (470.0, 70.0), (464.0, 110.0), (420.0, 66.0), (376.0, 68.0), (376.0, 112.0), (332.0, 68.0), (332.0, 112.0), (426.0, 118.0), (1598.0, 124.0), (1552.0, 124.0), (1504.0, 126.0), (1454.0, 128.0), (1404.0, 134.0), (1362.0, 132.0), (1310.0, 138.0), (1266.0, 138.0), (1220.0, 136.0), (336.0, 156.0), (378.0, 156.0), (422.0, 156.0), (472.0, 160.0), (508.0, 154.0), (556.0, 154.0), (602.0, 156.0), (646.0, 156.0), (686.0, 154.0), (734.0, 158.0), (774.0, 152.0), (818.0, 152.0), (864.0, 154.0), (906.0, 150.0), (950.0, 152.0), (996.0, 148.0), (1038.0, 146.0), (1084.0, 146.0), (1128.0, 144.0), (1172.0, 144.0), (1598.0, 170.0), (1552.0, 170.0), (1506.0, 174.0), (1458.0, 170.0), (1408.0, 178.0), (1360.0, 178.0), (1314.0, 178.0), (332.0, 200.0), (382.0, 204.0), (422.0, 200.0), (466.0, 202.0), (512.0, 200.0), (556.0, 198.0), (600.0, 202.0), (642.0, 198.0), (690.0, 200.0), (732.0, 196.0), (776.0, 198.0), (820.0, 196.0), (862.0, 198.0), (908.0, 200.0), (950.0, 196.0), (998.0, 196.0), (1042.0, 196.0), (1084.0, 192.0), (1130.0, 188.0), (1174.0, 186.0), (1220.0, 184.0), (1266.0, 186.0), (1596.0, 220.0), (1554.0, 216.0), (1500.0, 222.0), (1454.0, 222.0), (1402.0, 226.0), (1354.0, 228.0), (1312.0, 230.0), (1264.0, 232.0), (1220.0, 232.0), (1176.0, 232.0), (1128.0, 234.0), (1084.0, 236.0), (1038.0, 236.0), (996.0, 238.0), (950.0, 238.0), (906.0, 238.0), (864.0, 244.0), (818.0, 240.0), (776.0, 242.0), (734.0, 244.0), (690.0, 244.0), (644.0, 242.0), (602.0, 246.0), (554.0, 242.0), (514.0, 248.0), (466.0, 244.0), (422.0, 244.0), (378.0, 244.0), (1456.0, 266.0), (1504.0, 264.0), (1552.0, 264.0), (1406.0, 272.0), (1360.0, 272.0), (1312.0, 276.0), (1270.0, 276.0), (1218.0, 278.0), (1172.0, 280.0), (1128.0, 280.0), (1084.0, 280.0), (1040.0, 280.0), (996.0, 282.0), (952.0, 282.0), (908.0, 284.0), (866.0, 288.0), (820.0, 284.0), (776.0, 286.0), (732.0, 292.0), (688.0, 286.0), (644.0, 286.0), (600.0, 288.0), (558.0, 290.0), (510.0, 288.0), (466.0, 288.0), (422.0, 288.0), (378.0, 288.0), (1504.0, 310.0), (1556.0, 308.0), (1454.0, 316.0), (1406.0, 318.0), (1360.0, 316.0), (1312.0, 318.0), (1270.0, 318.0), (1220.0, 320.0), (1176.0, 320.0), (1130.0, 320.0), (1086.0, 324.0), (1040.0, 328.0), (998.0, 326.0), (954.0, 328.0), (908.0, 328.0), (864.0, 328.0), (822.0, 330.0), (778.0, 334.0), (734.0, 330.0), (692.0, 332.0), (648.0, 334.0), (602.0, 332.0), (556.0, 330.0), (512.0, 332.0), (468.0, 332.0), (422.0, 332.0), (378.0, 332.0), (378.0, 376.0), (428.0, 378.0), (470.0, 378.0), (512.0, 376.0), (556.0, 376.0), (602.0, 376.0), (646.0, 374.0), (690.0, 374.0), (736.0, 378.0), (780.0, 376.0), (824.0, 372.0), (866.0, 372.0), (910.0, 372.0), (954.0, 370.0), (998.0, 370.0), (1042.0, 370.0), (1084.0, 368.0), (1130.0, 370.0), (1178.0, 366.0), (1220.0, 366.0), (1270.0, 362.0), (1316.0, 362.0), (1364.0, 360.0), (1412.0, 358.0), (1460.0, 356.0), (1510.0, 356.0), (1554.0, 356.0), (1504.0, 404.0), (1454.0, 408.0), (1408.0, 406.0), (1362.0, 406.0), (1312.0, 410.0), (1268.0, 408.0), (1220.0, 410.0), (1176.0, 410.0), (1130.0, 412.0), (1088.0, 414.0), (1042.0, 414.0), (996.0, 418.0), (954.0, 416.0), (910.0, 416.0), (866.0, 416.0), (822.0, 416.0), (778.0, 418.0), (734.0, 416.0), (688.0, 418.0), (644.0, 418.0), (602.0, 420.0), (560.0, 420.0), (514.0, 418.0), (468.0, 420.0), (422.0, 420.0), (472.0, 466.0), (516.0, 466.0), (560.0, 466.0), (604.0, 464.0), (646.0, 464.0), (688.0, 462.0), (734.0, 462.0), (778.0, 462.0), (822.0, 460.0), (866.0, 464.0), (908.0, 460.0), (952.0, 460.0), (998.0, 460.0), (1042.0, 462.0), (1086.0, 458.0), (1130.0, 456.0), (1176.0, 456.0), (1224.0, 454.0), (1270.0, 454.0), (1316.0, 454.0), (1362.0, 456.0), (1408.0, 454.0), (1460.0, 450.0), (1412.0, 496.0), (1366.0, 496.0), (1314.0, 500.0), (1272.0, 500.0), (1222.0, 500.0), (1174.0, 504.0), (1132.0, 502.0), (1088.0, 502.0), (1042.0, 502.0), (998.0, 504.0), (954.0, 504.0), (910.0, 504.0), (864.0, 504.0), (820.0, 506.0), (778.0, 504.0), (736.0, 506.0), (690.0, 506.0), (648.0, 508.0), (602.0, 510.0), (560.0, 506.0), (514.0, 510.0), (558.0, 552.0), (602.0, 550.0), (646.0, 550.0), (692.0, 554.0), (734.0, 550.0), (780.0, 548.0), (824.0, 548.0), (868.0, 552.0), (912.0, 548.0), (956.0, 548.0), (996.0, 550.0), (1042.0, 548.0), (1088.0, 546.0), (1134.0, 546.0), (1178.0, 546.0), (1224.0, 546.0), (1272.0, 544.0), (1316.0, 544.0), (1368.0, 542.0)]

I want to sort the points in "snake scan" order like so:

Here is the original image converted to jpg to fit the maximum upload size on SO:

I'm having trouble though because the rows don't have the exact same y value and the columns don't have the exact same x value, it's a non-regular grid.

I tried using the the following function, but it's really sensitive to the tolerance value and doesn't quite work right.

def sort_points_snake_scan(points, tolerance=10):
    """Sort the points in a snake-scan pattern with a tolerance for y-coordinates.

    Arguments:
    - points (list): a list of (x, y) points
    - tolerance (int): the y-coordinate tolerance for grouping points into rows

    Returns:
    - snake_scan_order (list): the points sorted in snake-scan order.
    """
    # Group points by the y-coordinate with tolerance
    if not points:
        return []

    # Sort points by y to simplify grouping
    points = sorted(points, key=lambda p: p[1])
    
    rows = []
    current_row = [points[0]]

    for point in points[1:]:
        if abs(point[1] - current_row[-1][1]) <= tolerance:
            current_row.append(point)
        else:
            rows.append(current_row)
            current_row = [point]
    if current_row:
        rows.append(current_row)

    snake_scan_order = []
    reverse = True
    ind = 0
    for row in rows:
        # Sort the row by x-coordinate, alternating order for each row
        row_sorted = sorted(row, key=lambda point: point[0], reverse=reverse)
        snake_scan_order.extend(row_sorted)
        reverse = not reverse  # Flip the order for the next row
        ind += 1
    
    return snake_scan_order

Here is the result:

Does anyone know the right way to do this?

Answer 1

I would first sort the data by a diagonal sweep, i.e. by increasing sum-of-coordinates. At each point (in that order) determine what would be a good left-neighbor among the points that were already processed. A good neighbor will be in the ">" shaped cone at its left, and the rightmost candidate. Once attached, the attached nodes form a near-horizontal line, and we only need to consider the rightmost of each line when looking for a match in the ">"-cone of a next point.

This way we build all the lines from left to right. It is then a small task to turn that into a snake order.

Here is a Python function to perform this algorithm:

def sort_points_snake_scan(data):    
    lines = []
    for x, y in sorted(data, key=sum): # visited by a diagonal sweep
        for line in lines:
            x1, y1 = line[-1]
            # Is this point inside the ">"-cone of x,y?
            if abs(x1 - x) > abs(y1 - y):
                line.append([x, y])
                break
        else:  # Not found: this is a point on a new line
            lines.append([[x, y]])

    # sort lines from top to bottom
    lines.sort(key=lambda line: line[0][1]) 

    # concatenate the lines into snake order
    return [
        point    
        for i, line in enumerate(lines)
        for point in (line[::-1] if i%2 else line)
    ]

No need for a tolerance parameter: the algorithm assumes that the grid is not tilted more than 45° (up or down) at any point.