CODEWITHSUNDEEP
c++sorting
sancho.s ReinstateMonicaCellio
sancho.s ReinstateMonicaCellio

Reputation: 15561

Sort vector of spatial (2D/3D) vectors according to component 1, 2 (and 3)

I have a templated vector v of class T (either float or double), containing N*D (=npoints*ndims) elements. For example, for D=2, v would contain [ p0[0], p0[1], p1[0], p1[1], p2[0], p2[1], ... pN-1[0], pN-1[1] ].

I would like to get a vector lsort of N indexes that correspond to an ascending sorting the points, first according to coordinate 0 and then according to coordinate 1. There are no coincident points.

For example, if the points (p0...pN-1) are ((0,0), (0,1), (1,2), (1,0)), I mean:

v = [ 0, 0, 0, 1, 1, 2, 1, 0 ]
lsort = [ 0, 1, 3, 2 ]

since p3 has the same coordinate 0 than p2, but a lower coordinate 1.

I do not care about getting a sorted vector (I could do that once I have lsort).

I did comparisons with custom operators before, but I am not figuring out how have the comparison skip every other element.

Upvotes: 2

Views: 255

Answers (1)

eerorika
eerorika

Reputation: 238321

First generate a vector container of float pointers (or alternatively: iterators), where element points to every Dth element i.e. the first dimension of each spatial vector.

Then std::sort that vector of pointers using a custom comparison function, which does a lexicographical comparison of left[0], right[0], then left[1], right[1] until finally left[D-1], right[D-1] if all previous comparisons were equal.

You now have a vector container of pointers to each spatial vector, in your desired sorting. If you want to get the indices of those spatial vectors, simply subtract the pointer to the first element of v from each element of the pointer vector. This will be index within v. Divide by D to get the index matching your example output.

Alternatively, you could start out with sequence of indices from 0 to D-1 generated with std::iota, and use a more complex comparison function, which does the translation from index to coordinate.

Upvotes: 2

Related Questions