sorting - 按斜率排序线

Question

任何 CGAL 包中是否有按斜率对线（Line_2）进行排序的功能？或者任何人都可以推荐一种考虑退化情况的排序算法，如垂直线？

Answer 1

您可以使用CGAL::Direction_2. 有一个构造函数Line_2，并且有一个允许对它们进行排序的operator <之间。Direction_2

例如，您可以使用std::map<CGAL::Direction_2, CGAL::Line_2>，在此映射中插入对of Direction_2及其对应的Line_2。您直接获得了排序后的排序行std::map。

Answer 2

有对象的CGAL::compare_slopes自由函数Line_2和相应的K::Compare_slope_2函子（可以从给定的 by 实例k中K提取k.compare_slope_2_object()）。

您可以在以下示例中看到它：

#include <algorithm>
#include <iostream>
#include <vector>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

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 << "insertion order:" << 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 << "sorted order:" << std::endl;
  for (int i = 0; i < l.size(); ++i)
    std::cout << "    " << l[i] << std::endl;
}

请注意，compare_slopes比较定向线，本质上是方向；如果这不是你想要的，你必须标准化你的线条（例如确保所有y坐标为正）。

Answer 3

实际上并没有真正需要定义struct Slope_comparator并使其调用全局函数。您可以直接将仿函数传递CGAL::Compare_slope_2给std::sort()函数。