Thursday, 15 September 2011

Sorting lines by slope -



Sorting lines by slope -

is there function in of cgal packages sort lines (line_2) slope? or can recommend sorting algorithm considers degenerate cases vertical lines?

there's cgal::compare_slopes free function line_2 objects, , corresponding k::compare_slope_2 functor (which can extracted given instance k of k k.compare_slope_2_object()).

you can see in next example:

#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 { homecoming (cgal::compare_slopes (l1, l2) < 0); // homecoming (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.)); // vertical l.push_back (line_2 (1e-100, -1., 0.)); // vertical l.push_back (line_2 ( 0., -1., 1.)); // vertical l.push_back (line_2 (1e-100, 1., 2.)); // vertical l.push_back (line_2 (1e-100, -1., 3.)); // vertical l.push_back (line_2 ( 1., 0., 0.)); // horizontal l.push_back (line_2 ( 1., 1e-100, 0.)); // horizontal l.push_back (line_2 ( -1., 1e-100, 0.)); // horizontal l.push_back (line_2 ( -1., 0., 4.)); // horizontal l.push_back (line_2 ( -1., 1e-100, 5.)); // horizontal l.push_back (line_2 ( 1., 1e-100, 6.)); // horizontal std::cout << "insertion order:" << std::endl; (int = 0; < l.size(); ++i) std::cout << " " << l[i] << std::endl; std::sort (l.begin(), l.end(), slope_comparator()); std::cout << "sorted order:" << std::endl; (int = 0; < l.size(); ++i) std::cout << " " << l[i] << std::endl; }

note compare_slopes compares oriented lines, directions; if that's not want, have normalize lines (e.g. ensure y-coordinates positive).

sorting line computational-geometry cgal

No comments:

Post a Comment