Triage des lignes par pente

Question

Y a-t-il une fonction dans l'un des packages CGAL pour trier les lignes (Line_2) par pente? Ou est-ce que quelqu'un peut recommander un algorithme de tri qui prend en compte les cas dégénérés tels que les lignes verticales?

Answer 1

Vous pouvez utiliser CGAL::Direction_2. Il y a un constructeur à partir de Line_2, et il y a un opérateur < entre les Direction_2 qui permet de les trier.

Vous pouvez par exemple utiliser une std::map, insérer dans cette map la paire de Direction_2 et leur Line_2 correspondante. Vous obtenez directement les lignes triées car std::map est triée.

Answer 2

Il y a la fonction libre CGAL::compare_slopes pour les objets Line_2, et le foncteur correspondant K::Compare_slope_2 (qui peut être extrait d'une instance donnée k de K par k.compare_slope_2_object()).

Vous pouvez le voir dans l'exemple suivant:

#include 
#include 
#include 
#include 

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef typename K::Line_2 Line_2;

struct Slope_comparator {
  // K k;
  // Slope_comparator (const K &k = K()) : k(k) {}
  bool operator() (const Line_2 &l1, const Line_2 &l2) const {
    return (CGAL::compare_slopes (l1, l2) < 0);
    // return (k.compare_slope_2_object()(l1, l2) < 0);
  }
};

int main () {
  std::vector< Line_2 > l;
  l.push_back (Line_2 (    1.,     1., 0.));
  l.push_back (Line_2 (    1.,    -1., 0.));
  l.push_back (Line_2 (    0.,     1., 0.)); // vertical
  l.push_back (Line_2 (1e-100,     1., 0.)); // almost vertical
  l.push_back (Line_2 (1e-100,    -1., 0.)); // almost vertical
  l.push_back (Line_2 (    0.,    -1., 1.)); // also vertical
  l.push_back (Line_2 (1e-100,     1., 2.)); // also almost vertical
  l.push_back (Line_2 (1e-100,    -1., 3.)); // also almost vertical
  l.push_back (Line_2 (    1.,     0., 0.)); // horizontal
  l.push_back (Line_2 (    1., 1e-100, 0.)); // almost horizontal
  l.push_back (Line_2 (   -1., 1e-100, 0.)); // almost horizontal
  l.push_back (Line_2 (   -1.,     0., 4.)); // also horizontal
  l.push_back (Line_2 (   -1., 1e-100, 5.)); // also almost horizontal
  l.push_back (Line_2 (    1., 1e-100, 6.)); // also almost horizontal

  std::cout << "ordre d'insertion:" << std::endl;
  for (int i = 0; i < l.size(); ++i)
    std::cout << "    " << l[i] << std::endl;

  std::sort (l.begin(), l.end(), Slope_comparator());
  std::cout << "ordre trié:" << std::endl;
  for (int i = 0; i < l.size(); ++i)
    std::cout << "    " << l[i] << std::endl;
}

Remarquez que compare_slopes compare des lignes orientées, essentiellement des directions ; si ce n'est pas ce que vous voulez, vous devez normaliser vos lignes (par exemple, assurez-vous que toutes les coordonnées y sont positives).

Answer 3

En fait, il n'y a pas vraiment besoin de définir struct Slope_comparator et de le faire appeler la fonction globale. Vous pouvez directement passer le foncteur CGAL::Compare_slope_2 à la fonction std::sort().