2

CGAL パッケージのいずれかに、ライン (Line_2) を勾配でソートする機能はありますか? または、縦線のような退化したケースを考慮した並べ替えアルゴリズムを推奨できる人はいますか?

4

3 に答える 3

3

オブジェクトのCGAL::compare_slopesfree 関数と、対応するファンクター ( byの特定のインスタンスから抽出できます) があります。Line_2K::Compare_slope_2kKk.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座標が正であることを確認します)。

于 2013-02-06T08:39:39.727 に答える
3

使用できますCGAL::Direction_2。from のコンストラクターがあり、それらを並べ替えることができるbetweenLine_2があります。operator <Direction_2

たとえば、 を使用してstd::map<CGAL::Direction_2, CGAL::Line_2>、このマップにペアof Direction_2とそれに対応するを挿入できLine_2ます。ソートされているソート行を直接取得しましたstd::map。

于 2013-02-06T08:12:25.400 に答える
1

struct Slope_comparator実際、グローバル関数を定義して呼び出す必要はありません。CGAL::Compare_slope_2ファンクターを関数に直接渡すことができstd::sort()ます。

于 2013-02-08T08:38:26.203 に答える