CGAL provides traits class implementations that allow to use the
segment tree with point classes from the CGAL kernel as keys. These
classes are presented in Section . In
Section
we give the requirements that segment
tree traits classes must fulfill. This allows the advanced user to
develop further segment tree traits classes.
#include <CGAL/Segment_tree_k.h>
| |
the type of the segment tree traits class.
|
| ||
|
||
| ||
|
| |||||
Introduces an empty segment tree S.
| |||||
| |||||
| |||||
Introduces a segment tree S and initializes it with the data
in the range [first, last).
Precondition: value_type(first) == Traits::Interval.
|
| ||||||
|
| |||||
Introduces a segment tree S and initializes it with the data
in the range [first, last). This function can only be
applied once on an empty segment tree.
Precondition: value_type(first) == Traits::Interval. | ||||||
| ||||||
|
| |||||
writes all intervals that have non empty intersection with interval
window to the container where out points to, and
returns an output iterator that points to the last location the
function wrote to. Precondition: value_type(out) == Traits::Interval. | ||||||
| ||||||
|
| |||||
writes all intervals that enclose in the interval window to
the container where out points to, and returns an output
iterator that points to the last location the function wrote to.
Precondition: value_type(out) == Traits::Interval. |
#include <CGAL/Homogeneous.h> #include <CGAL/Point_2.h> #include <CGAL/Segment_tree_k.h> #include <CGAL/Range_segment_tree_traits.h> typedef CGAL_Cartesian<double> Rep; typedef CGAL_Range_segment_tree_traits_2<Rep> Traits; typedef CGAL_Segment_tree_2<Traits > Segment_tree_2_type; int main() { typedef Traits::Key Key; /* is a CGAL_Point_2<Rep> */ typedef Traits::Interval Interval; /* is a pair<Key,Key> */ list<Interval> InputList, OutputList, N; InputList.push_back(Interval(Key(1,5), Key(2,7))); InputList.push_back(Interval(Key(2,7), Key(3,8))); InputList.push_back(Interval(Key(6,9), Key(9,13))); InputList.push_back(Interval(Key(1,3), Key(3,9))); Segment_tree_2_type Segment_tree_2(InputList.begin(), InputList.end()); Interval a(Key(3,6), Key(7,12)); Segment_tree_2.window_query(a,back_inserter(OutputList)); /* output of the query elements on stdout */ list<Interval>::iterator j = OutputList.begin(); cout << "\n window_query \n"; while(j!=OutputList.end()) { cout << (*j).first.x() << "-" << (*j).second.x() << " " << (*j).first.y() << "-" << (*j++).second.y() << endl; } Interval b(Key(6,10),Key(7,11)); Segment_tree_2.enclosing_query(b,back_inserter(OutputList)); cout << "\n enclosing_query \n"; while(j!=OutputList.end()) { cout << (*j).first.x() << "-" << (*j).second.x() << " " << (*j).first.y() << "-" << (*j++).second.y() << endl; } }