Trouvez tous les points d'une grille dans un cercle, ordonné par norme

Question

Comment résoudre le problème de la recherche des points d'une grille (entière) dans un cercle centré sur l'origine de l'axe, avec les résultats ordonnés par la norme, comme en distance du centre, en C ++?

J'ai écrit une implémentation qui fonctionne (oui, je sais, c'est extrêmement inefficace, mais pour mon problème, tout serait exagéré). Je suis extrêmement nouveau dans C ++, donc mon plus gros problème a été de trouver une structure de données capable de

1. être triable;
2. Pouvoir sauver un tableau dans l'un de ses éléments,

plutôt que la mise en œuvre de l'algorithme. Mon code est le suivant. Merci d'avance, tout le monde!

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

Comment résoudre le problème de la recherche des points d'une grille (entière) dans un cercle centré sur l'origine de l'axe, avec les résultats ordonnés par la norme, comme en distance du centre, en C ++?

Je n'utiliserais pas un std::pair pour tenir les points. Je créerais mon propre type descriptif.

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

Cette structure de données est (probablement) exactement de la même taille que deux INT, elle est moins que comparable, elle est attribuable et elle est facilement imprimable.

L'algorithme traverse tous les points valides qui satisfont x = [0, rayon] && y = [0, x] && (x, y) à l'intérieur du cercle:

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

J'ai choisi un std::set Pour conserver les données pour deux raisons:

• Il est stocké est trié, donc je n'ai pas à std::sort ça et
• Il rejette les doublons, donc je n'ai pas à me soucier des points dont la réflexion est identique

Enfin, l'utilisation de cet algorithme est simple:

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

Answer 2

Cela vaut toujours la peine d'ajouter une classe de points pour un tel problème géométrique, car généralement vous en avez plus d'un à résoudre. Mais je ne pense pas que ce soit une bonne idée de surcharger l'opérateur «moins» pour satisfaire le premier besoin rencontré. Car:

• Spécifier le comparateur où vous triez indiquera clairement l'ordre que vous souhaitez là-bas.
• La spécification du comparateur permettra de le changer facilement sans affecter votre classe de points génériques.
• La distance à l'origine n'est pas un mauvais ordre, mais pour une grille, mais il est probablement préférable d'utiliser des lignes et des colonnes (trier par x d'abord alors y).
• Un tel comparateur est plus lent et ralentira ainsi tout autre ensemble de points où vous ne vous souciez même pas de la norme.

Quoi qu'il en soit, voici une solution simple utilisant un comparateur spécifique et essayant d'optimiser un peu:

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