Sorting the following coordinates in the given pattern:

Question

I have the following image:

The coordinates corresponding to the white blobs in the image are sorted according to the increasing value of x-coordinate. However, I want them to follow the following pattern:

(In a zig-zag manner from bottom left to top left.)

Any clue how can I go about it? Any clue regarding the algorithm will be appreciated.

The set of coordinates are as follows:

[46.5000000000000,104.500000000000]
[57.5000000000000,164.500000000000]
[59.5000000000000,280.500000000000]
[96.5000000000000,66.5000000000000]
[127.500000000000,103.500000000000]
[142.500000000000,34.5000000000000]
[156.500000000000,173.500000000000]
[168.500000000000,68.5000000000000]
[175.500000000000,12.5000000000000]
[198.500000000000,37.5000000000000]
[206.500000000000,103.500000000000]
[216.500000000000,267.500000000000]
[225.500000000000,14.5000000000000]
[234.500000000000,62.5000000000000]
[251.500000000000,166.500000000000]
[258.500000000000,32.5000000000000]
[271.500000000000,13.5000000000000]
[284.500000000000,103.500000000000]
[291.500000000000,61.5000000000000]
[313.500000000000,32.5000000000000]
[318.500000000000,10.5000000000000]
[320.500000000000,267.500000000000]
[352.500000000000,57.5000000000000]
[359.500000000000,102.500000000000]
[360.500000000000,167.500000000000]
[366.500000000000,11.5000000000000]
[366.500000000000,34.5000000000000]
[408.500000000000,9.50000000000000]
[414.500000000000,62.5000000000000]
[419.500000000000,34.5000000000000]
[451.500000000000,12.5000000000000]
[456.500000000000,97.5000000000000]
[457.500000000000,168.500000000000]
[465.500000000000,62.5000000000000]
[465.500000000000,271.500000000000]
[468.500000000000,31.5000000000000]
[498.500000000000,10.5000000000000]
[522.500000000000,105.500000000000]
[524.500000000000,32.5000000000000]
[533.500000000000,60.5000000000000]
[534.500000000000,11.5000000000000]
[565.500000000000,164.500000000000]
[576.500000000000,33.5000000000000]
[581.500000000000,10.5000000000000]
[582.500000000000,67.5000000000000]
[586.500000000000,267.500000000000]
[590.500000000000,102.500000000000]
[622.500000000000,10.5000000000000]
[630.500000000000,32.5000000000000]
[646.500000000000,58.5000000000000]
[653.500000000000,94.5000000000000]
[669.500000000000,8.50000000000000]
[678.500000000000,167.500000000000]
[680.500000000000,31.5000000000000]
[705.500000000000,57.5000000000000]
[719.500000000000,9.50000000000000]
[729.500000000000,271.500000000000]
[732.500000000000,33.5000000000000]
[733.500000000000,97.5000000000000]
[757.500000000000,11.5000000000000]
[758.500000000000,59.5000000000000]
[778.500000000000,157.500000000000]
[792.500000000000,31.5000000000000]
[802.500000000000,10.5000000000000]
[812.500000000000,94.5000000000000]
[834.500000000000,59.5000000000000]
[839.500000000000,30.5000000000000]
[865.500000000000,160.500000000000]
[866.500000000000,272.500000000000]
[885.500000000000,58.5000000000000]
[892.500000000000,97.5000000000000]
[955.500000000000,94.5000000000000]
[963.500000000000,163.500000000000]
[972.500000000000,265.500000000000]

Answer 1

This approach assumes you know how many rows you expect, although I suspect there's programmatic ways you could estimate that.

nbins = 6;                            % Number of horizontal rows we expect
[bin,binC] = kmedoids(A(:,2),nbins);  % Use a clustering approach to group them
bin = binC(bin);                      % Clusters in random order, fix it so that clusters
[~,~,bin] = unique(bin);              %   are ordered by central y value
xord = A(:,1) .* (-1).^mod(bin+1,2);    % flip/flop for each row making the x-coord +ve or -ve
                                      %   so that we can sort in a zig-zag
[~,idx] = sortrows([bin,xord], [1,2]); % Sort by the clusters and the zig-zag
B = A( idx, : );                      % Create re-ordered array

Plotting this, it seems like what you want

figure(99); clf; hold on;
plot( A(:,1), A(:,2), '-o' );
plot( B(:,1), B(:,2), '-', 'linewidth', 1.5 );
set(gca, 'YDir', 'reverse');
legend( {'Original','Reordered'} );

Answer 2

Use a nearest neighbor search, where you define a custom distance measure which makes distance in the Y direction more expensive than distance in the X direction. Then start the algorithm with the bottom left point.

The "normal" Euclidean distance in Cartesian coordinates is calculated by sqrt( (x2 - x1)^2 + (y2 - y1)^2 )

To make the y direction more expensive, use a custom distance formula where you multiply the y result by a constant: sqrt( (x2 - x1)^2 + k*(y2 - y1)^2 ) where the constant k is larger than 1 but not much larger, I would start with 2.

Answer 3

The most similar algorithm I can think of is Andrew's algorithm for convex hulls, specifically the lower hull (though depending on the coordinate system, you may need to use the upper hull instead).

Running the lower hull algorithm and removing points until no points remain would get you want. To get the zig-zag patterning, reverse the ordering every other time you run it.

Here is implementations in most languages:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain

Edit: Downside here is precision in the case of fuzzy measurements. You may need to adjust the algorithm a bit if convex hulls aren't exactly what you need. IE: if you want to consider it still part of the hull if it's within say with 0.1 or say 1% of being on the hull or something. In the example given, the coordinates are exactly on the line so it would work well, but not so much so if the coordinates were say randomly distributed within say 0.1 of their actual positions.

Answer 4

Building upon uSeemSurprised's answer, I would go for a 3-steps approach:

• Sort the points list by y-coord. This is O(n log n)
• Determine the y-axis ranges. I simply iterate over the points and take note of where the y-coord difference is larger than a threshold value. This is O(n) of course
• Sort each of the sublists that represent the y-axis lines by x-coord. If we had m sublists of k items each this would be O(m (k log k)); so the overall process is still O(n log n)

The code:

def zigzag(points, threshold=10.0)
    #step 1
    points.sort(key=lambda x:x[1])

    #step 2
    breaks = []
    for i in range(1, len(points)):
        if points[i][1] - points[i-1][1] > threshold:
            breaks.append(i)
    breaks.append(i)

    #step 3
    rev = False
    start = 0
    outpoints = []
    for b in breaks:
        outpoints += sorted(points[start:b], reverse = rev)
        start = b
        rev = not rev

    return outpoints

Answer 5

You can sort the x-axis coordinates corresponding to y-axis coordinates, where you consider certain y-axis range, i.e the coordinates that are sorted according to x-axis all belong to the same y-axis range. Each time you move up to a different y-axis range you can flip the sorting order, i.e increasing then decreasing and so on.