2

C ++で、軸の原点を中心とする円内の（整数）グリッドの点を見つける問題をどのように解決しますか？結果は、中心からの距離のように、ノルム順に並べられていますか？

私は機能する実装を作成しました（ええ、私は知っています、それは非常に非効率的ですが、私の問題ではそれ以上のものはやり過ぎでしょう）。私はC++に非常に慣れていないので、私の最大の問題は、次の機能を備えたデータ構造を見つけることでした。

  1. ソート可能であること。
  2. 配列をその要素の1つに保存できること、

アルゴリズムの実装ではなく。私のコードは次のとおりです。みなさん、よろしくお願いします！

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;
}
4

2 に答える 2

4

C ++で、軸の原点を中心とする円内の（整数）グリッドの点を見つける問題をどのように解決しますか？結果は、中心からの距離のように、ノルム順に並べられていますか？

std::pairポイントを保持するためにaを使用することはありません。もっとわかりやすいタイプを作成します。

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 << ")";
  }
};

このデータ構造は（おそらく）2つのintとまったく同じサイズであり、比較可能ではなく、割り当て可能であり、簡単に印刷できます。

アルゴリズムは、円の内側でx = [0、radius] && y = [0、x] &&（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私は2つの理由でデータを保持することを選択しました：

  • 並べ替えて保存されているので、必要ありませんstd::sort。
  • 重複を拒否するので、反射が同じポイントを気にする必要はありません

最後に、このアルゴリズムの使用は非常に簡単です。

int main () {
  std::set<Point> vp = GetListOfPointsInsideCircle(2);
  std::copy(vp.begin(), vp.end(),
    std::ostream_iterator<Point>(std::cout, "\n"));
}
于 2012-02-29T18:11:18.357 に答える
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);
于 2012-02-29T19:52:50.313 に答える