用于对二维坐标数组进行排序并计算边界框的 C++ 函数

Question

我有一个 n 个大小为 2 的 double 组:

double **stored_points_;

我需要编写一个函数，根据给定的轴(x 或 y)按升序对这些坐标进行排序，并将这些排序后的坐标存储在一个新的二维数组中。我还需要一个函数来计算坐标的边界框并存储在两个给定的输出参数中。

我已经成功地编写了复制构造函数、getter、setter 等。我尝试过一种冒泡排序，但无法弄清楚如何让它与二维数组一起工作。

我期望的是

如果坐标是 (1,5), (2,2), (1,1), (1,3) 轴 = 0 时的结果:(1,1), (1,3), (1,5), (2,2) 轴 = 1 时的结果:(1,1), (2,2), (1,3), (1,5)

//function definitions from class Points2D{}:

void SortByAxis(size_t axis, double** sorted_points) const;
//axis: 0 means sort by x-axis, 1 means sort by y-axis

void CalcBoundingBox(double lower_left[2], double upper_right[2])     const;

//some members of class Points2D{}:

public:
  static const size_t x = 0;
  static const size_t y = 0;
private:  0;
  double **stored_points_;

Answer 1

正如 immibis 已经指出的那样:

Notice that sorting your 2D array, is the same as sorting a normal 1D array where the items you're sorting happen to be arrays.

我想补充一点，OP 希望知道 2D 数组(数组的数组)不是 OP 公开的内容。

double **stored_points是指向 double* 的指针并且可以表示 double* 的数组.这不是兼容的类型，例如double points[][2] . (SO 中有许多与此相关的问答:
SO: Why can't we use double pointer to represent two dimensional arrays?
实际上标记为 c但适用于 c++还有。)

标准库已经提供了现成的 std::sort() 对可在大多数常见情况下使用的各种容器(包括数组)进行排序——OP 中的一种:

Sorts the elements in the range [first, last) in ascending order. The order of equal elements is not guaranteed to be preserved.

std::sort() 的复杂性是 O(N·log(N)) → 比 Bubble sort 的复杂度好很多(考虑使用 OP)即 O(N²)。

有多种口味可供选择。对于 OP 案例，需要自定义比较器，因为升序的含义应根据要求更改。

因此，

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp )

被选中。

Parameters

first, last - the range of elements to sort

comp - comparison function object (i.e. an object that satisfies the requirements of Compare) which returns ​true if the first argument is less than (i.e. is ordered before) the second.

The signature of the comparison function should be equivalent to the following:

bool cmp(const Type1 &a, const Type2 &b);

While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1 & is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)). The types Type1 and Type2 must be such that an object of type RandomIt can be dereferenced and then implicitly converted to both of them. ​

对于 double **stored_points , 在 first stored_points可以在 last 中通过stored_points + n .因此，n是数组的大小。 OPs 暴露的代码中没有提到它，但它是绝对必要的值。指针可以表示任意长度的数组。我只知道两种从指针获取数组长度的方法:单独提供它或使用特定值作为结束标记(就像在 C 字符串中使用 '\0' 所做的那样)。

对于比较器，必须传递具有匹配签名的函数(或仿函数)。 在这种特定情况下，它是

bool(double* const &, double* const &)

但是(甚至更好)

bool(double*, double*)

也会这样做。

这可以是函数、仿函数(即带有 operator() 的类)或 lambda(类似于前者之一)。我决定使用 lambda(以尽量减少我的代码):

    [](double *pt1, double *pt2) {
      return pt1[0] != pt2[0] // if first elements unequal
        ? pt1[0] < pt2[0] // return whether first first < second first
        : pt1[1] < pt2[1]; // else whether first second < second second
    }

这提供了比较第一个子元素的 less 运算符，仅当第一个子元素相等时才考虑第二个子元素。这个 less 比较器定义了一个 Order在 std::sort() 中需要定义升序的含义。

要更改顺序(使用前导 y 坐标排序)，只需使用另一个 lambda:

    [](double *pt1, double *pt2) {
      return pt1[1] != pt2[1] // if second elements unequal
        ? pt1[1] < pt2[1] // return whether first second < second second
        : pt1[0] < pt2[0]; // else whether first first < second first

实际上看起来非常相似——只是索引被交换了。

---

完整示例:

#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>

// a print function (usable in output streams)
std::string print(double **data, size_t n)
{
  std::ostringstream out;
  const char *sep = "";
  for (size_t i = 0; i < n; ++i) {
    out << sep << '(' << data[i][0] << ", " << data[i][1] << ')';
    sep = ", ";
  }
  return out.str();
}

int main()
{
  // sample data of OP
  double points[][2] = {
    { 1, 5 }, { 2, 2 }, { 1, 1 }, { 1, 3 }
  };
  const size_t n = sizeof points / sizeof *points; // let compiler determine
  // resemble input data of OP
  double *stored_points[n];
  for (size_t i = 0; i < n; ++i) stored_points[i] = points[i];
  // show input data
  std::cout
    << "Input data:\n"
    << "  " << print(stored_points, n) << '\n';
  // sort in ascending order with leading x:
  std::sort(stored_points, stored_points + n,
    [](double *pt1, double *pt2) {
      return pt1[0] != pt2[0] // if first elements unequal
        ? pt1[0] < pt2[0] // return whether first first < second first
        : pt1[1] < pt2[1]; // else whether first second < second second
    });
  // show result
  std::cout
    << "Data sorted by leading x:\n"
    << "  " << print(stored_points, n) << '\n';
  // sort in ascending order with leading y:
  std::sort(stored_points, stored_points + n,
    [](double *pt1, double *pt2) {
      return pt1[1] != pt2[1] // if second elements unequal
        ? pt1[1] < pt2[1] // return whether first second < second second
        : pt1[0] < pt2[0]; // else whether first first < second first
    });
  // show result
  std::cout
    << "Data sorted by leading y:\n"
    << "  " << print(stored_points, n) << '\n';
  // done
  return 0;
}

输出:

Input data:
  (1, 5), (2, 2), (1, 1), (1, 3)
Data sorted by leading x:
  (1, 1), (1, 3), (1, 5), (2, 2)
Data sorted by leading y:
  (1, 1), (2, 2), (1, 3), (1, 5)

Live Demo on coliru