sort vector of Coordinates(x,y,z) by vector of z value

Question

I have a vector of 3D coordinates:

vector<float64>contourdata;
contourdata={x0,y0,z0,x1,y1,z1,x2,y2,z2,...}

And I want to sort them by the vector of the z value. How can I do it in c++?

Answer 1

I struggled to find a way to use std::sort but you can always drop back the the C qsort stdlib function:

#include <cstdlib>

int compare(const double *A, const double *B) {
    return (A[2] <= B[2]) ? -1 : +1;
}

...

const size_t N = contourdata.size() / 3;
qsort(contourdata.data(), N, 3*sizeof(double),
      (int (*)(const void *, const void*))compare);

qsort (and mergesort and heapsort) are sort routines provided by the C standard library that have been around a long time. They are designed to sort data stored in contiguous arrays, but it is the programmers job to specify how the data is laid out and how to order the elements. qsort is not type-safe and generally not preferred, but can handle cases like this one. qsort has three parameters:

1. A ptr to the base of the array. Note that the ptr type is void * and thus the compiler has no clue about the type of data in the buffer. std::vector provides a data() method that provides a ptr to its internal buffer (which is guaranteed to be contiguous).

2. The number of elements. Since each element consists of 3 double's we use we use the size of the vector divided by 3.

3. The size of each element in bytes.

4. A ptr to a function used for comparing two elements. The arguments to each element are generic ptrs, but since we know they are ptrs to buffers containing doubles we can specify the type in our compare function. Each element is an array of 3 doubles and, since we are using the z-component as the sort key, we compare the doubles at offset 2. We return -1 for "less than" and +1 for "greater" -- this is enough to know how to sort.

Note that when passing the compare function to qsort we cast it to the function ptr type that it expects to keep the compiler from issuing a warning.

Answer 2

Like this :

#include <algorithm>
#include <iostream>
#include <vector>
#include <format>

// 3d points have 3 coordinates and
// we need to move those 3 values together when sorting
// It is also good to use "concepts" from real world as
// names in code : so define a struct representing a 3d coordinate.
// (Or use a 3d coordinate type from an existing library)
struct vec_3d_t
{
    double x;
    double y;
    double z;
};

// helper function for outputing the values of one 3d point
// not essential for your problem.
std::ostream& operator<<(std::ostream& os, const vec_3d_t& data_point)
{
    os << std::format("({0},{1},{2})", data_point.x, data_point.y, data_point.z);
    return os;
}

int main()
{
    // std::vector is a (resizable) array
    // in this case to hold 3d coordinates
    // then initialize the data with some values
    // (you will probably get them from somewhere else, e.g. a file)
    std::vector<vec_3d_t> contour_data
    {
        {3.0,4.0,5.0},  // first coordinate
        {1.0,2.0,3.0},  // second etc ...
        {7.0,8.0,9.0}
    };

    // this calls the sort algorithm
    // using a function to compare two 3d points
    // to sort on z only compare z.
    std::sort(contour_data.begin(), contour_data.end(), [](const vec_3d_t& lhs, const vec_3d_t& rhs)
        {
            return lhs.z < rhs.z;
        });

    // range based for loop over data points
    for (const auto& data_point : contour_data)
    {
        std::cout << data_point << "\n";
    }

    return 0;
}