How to sort an nested array of coordinates with ruby

Viewed 67

I am trying to sort with ruby a nested array like this:

[[810, 266], [236, 236], [814, 820], [230, 800]]

Each array [x, y] means a position in a photo and I want to sort it so the first array in the nested array is the one in the top left, the second in the top right, the third in the bottom left and the last in the bottom right. The array will always be 4 arrays into one [[x,y],[x,y],[x,y],[x,y]].

input

[[810, 266], [236, 236], [814, 820], [230, 800]]

output

[[236, 236], [810, 266], [230, 800], [814, 820]]
1 Answers

For a rectangular selection, you can use sort_by! to sort the array in-place by y first (top to bottom) and x second (left to right):

ary = [[60, 60], [10, 10], [10, 60], [60, 10]]

ary.sort_by! { |x, y| [y, x] }
#=> [[10, 10], [60, 10], [10, 60], [60, 60]]

or: (because [y, x] is the reverse of [x, y])

ary.sort_by!(&:reverse)
#=> [[10, 10], [60, 10], [10, 60], [60, 60]]

This works, because arrays are sorted in an element-wise manner, i.e. it will sort all elements by y and elements with identical y value by x. (see Array#<=>)


For a non-rectangular selection like in your example, it's more tricky because the y coordinates are not pairwise equal and the above approach won't work. Let's switch the x-values for the bottom coordinates to make that problem more obvious:

ary = [[810, 266], [236, 236], [814, 800], [230, 820]]

ary.sort_by!(&:reverse)
#=> [[236, 236], [810, 266], [814, 800], [230, 820]]
#                             ^^^         ^^^

In the above result, the bottom left coordinate comes after the bottom right coordinate.

Assuming that your coordinates are roughly rectangular, you could first sort by y only (which is the last value) to get the top 2 coordinates first and the bottom 2 coordinates last:

ary.sort_by!(&:last)
#=> [[236, 236], [810, 266], [814, 800], [230, 820]]

You could then sort each of the top-two and bottom-two separately by x (which is the first value):

ary[0..1] = ary[0..1].sort_by(&:first)
ary[2..3] = ary[2..3].sort_by(&:first)

ary
#=> [[236, 236], [810, 266], [230, 820], [814, 800]]

Note that [230, 820] goes before [814, 800] now despite having a larger y-value.

Special cases like kite or dart shaped selections might require different sorting order.

Related