我有一个表示在图像中检测到的圆的点列表.
[(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:
但我遇到了麻烦，因为行的y值不完全相同，列的x值也不完全相同，这是一个非规则网格.
我try 使用以下函数，但它对容差值非常敏感，并且工作不太正常.
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?