在一个圆内找到网格的所有点，按范数排序

Question

在C++中，如何解决在以轴原点为中心的圆内查找（整数）网格的点的问题，并且结果按范数排序（如距中心的距离）？

我写了一个有效的实现（是的，我知道，它效率非常低，但对于我的问题来说，任何更多的东西都是多余的）。我对C++非常陌生，所以我最大的问题是找到一个能够进行的数据结构

1. 能够分类
2. 能够将阵列保存在其元素之一中

而不是算法的实现。我的代码如下。提前谢谢大家！

typedef std::pair<int, int[2]> norm_vec2d;
bool norm_vec2d_cmp (norm_vec2d a, norm_vec2d b)
{
    bool bo;
    bo = (a.first < b.first ? true: false);
    return bo;
}
int energy_to_momenta_2D (int energy, std::list<norm_vec2d> *momenta)
{
    int i, j, norm, n=0;
    int energy_root = (int) std::sqrt(energy);
    norm_vec2d temp;
    for (i=-energy_root; i<=energy_root; i++)
    {
        for (j =-energy_root; j<=energy_root; j++)
        {
            norm = i*i + j*j;
            if (norm <= energy)
            {
                temp.first = norm;
                temp.second[0] = i;
                temp.second[1] = j;
                (*momenta).push_back (temp);
                n++;
            }
        }
    }
    (*momenta).sort(norm_vec2d_cmp);
    return n;
}

Answer 1

在C++中，你将如何解决在以轴原点为中心的圆内寻找（整数）网格的点的问题，其结果按范数排序，如与中心的距离？

我不会用std::pair来保持分数。我会创建自己的更具描述性的类型。

struct Point {
  int x;
  int y;
  int square() const { return x*x + y*y; }
  Point(int x = 0, int y = 0)
    : x(x), y(y) {}
  bool operator<(const Point& pt) const {
    if( square() < pt.square() )
      return true;
    if( pt.square() < square() )
      return false;
    if( x < pt.x )
      return true;
    if( pt.x < x)
      return false;
    return y < pt.y;
  }
  friend std::ostream& operator<<(std::ostream& os, const Point& pt) {
    return os << "(" << pt.x << "," << pt.y << ")";
  }
};

这种数据结构（可能）与两个int大小完全相同，不具有可比性，可赋值，并且易于打印。

该算法遍历满足x＝[0，radius]&amp；y=[0，x]&amp；（x，y）内圈：

std::set<Point>
GetListOfPointsInsideCircle(double radius = 1) {
  std::set<Point> result;
  // Only examine bottom half of quadrant 1, then
  // apply symmetry 8 ways
  for(Point pt(0,0); pt.x <= radius; pt.x++, pt.y = 0) {
    for(; pt.y <= pt.x && pt.square()<=radius*radius; pt.y++) {
      result.insert(pt);
      result.insert(Point(-pt.x, pt.y));
      result.insert(Point(pt.x, -pt.y));
      result.insert(Point(-pt.x, -pt.y));
      result.insert(Point(pt.y, pt.x));
      result.insert(Point(-pt.y, pt.x));
      result.insert(Point(pt.y, -pt.x));
      result.insert(Point(-pt.y, -pt.x));
    }
  }
  return result;
}

我选择std::set来保存数据有两个原因：

• 它是按排序顺序存储的，所以我不必std::sort它，并且
• 它拒绝重复，所以我不必担心反射相同的点

最后，使用这种算法非常简单：

int main () {
  std::set<Point> vp = GetListOfPointsInsideCircle(2);
  std::copy(vp.begin(), vp.end(),
    std::ostream_iterator<Point>(std::cout, "n"));
}

Answer 2

为这样的几何问题添加一个点类总是值得的，因为通常需要解决多个点类。但我认为让"less"操作符过载以满足第一次遇到的需求不是一个好主意。因为：

• 指定排序的比较器将清楚地显示您想要的排序顺序
• 指定比较器将允许在不影响泛型点类的情况下轻松更改它
• 到原点的距离不是一个坏顺序，但对于网格来说，最好使用行和列（先按x排序，然后按y排序）
• 这样的比较器比较慢，因此会减慢任何其他你甚至不关心范数的点

无论如何，这里有一个简单的解决方案，使用一个特定的比较器并尝试优化一点：

struct v2i{
    int x,y;
    v2i(int px, int py) : x(px), y(py) {}
    int norm() const {return x*x+y*y;}
};
bool r_comp(const v2i& a, const v2i& b)
    { return a.norm() < b.norm(); }
std::vector<v2i> result;
for(int x = -r; x <= r; ++x) {
    int my = r*r - x*x;
    for(int y = 0; y*y <= my; ++y) {
        result.push_back(v2i(x,y));
        if(y > 0)
            result.push_back(v2i(x,-y));
    }
}
std::sort(result.begin(), result.end(), r_comp);