mirror of https://github.com/CGAL/cgal
105 lines
2.6 KiB
C++
105 lines
2.6 KiB
C++
|
|
#include <CGAL/Cartesian.h>
|
|
#include <CGAL/Segment_tree_k.h>
|
|
#include <CGAL/Range_segment_tree_traits.h>
|
|
#include <CGAL/Timer.h>
|
|
#include <iostream>
|
|
#include <fstream>
|
|
#include <vector>
|
|
#include <list>
|
|
|
|
|
|
|
|
typedef CGAL::Cartesian<double> K;
|
|
typedef CGAL::Range_segment_tree_set_traits_2<K> Traits;
|
|
typedef CGAL::Segment_tree_2<Traits > Segment_tree_2_type;
|
|
|
|
typedef K::Point_2 Point_2;
|
|
typedef K::Iso_rectangle_2 Iso_rectangle_2;
|
|
typedef std::pair<Point_2, Point_2> Interval;
|
|
typedef CGAL::Timer Timer;
|
|
|
|
int main()
|
|
{
|
|
|
|
Timer t;
|
|
|
|
int ignore = 0;
|
|
std::list<Iso_rectangle_2> rectangles;
|
|
std::ifstream ifs("data.rect");
|
|
std::copy(std::istream_iterator<Iso_rectangle_2>(ifs),
|
|
std::istream_iterator<Iso_rectangle_2>(),
|
|
std::back_inserter(rectangles));
|
|
|
|
std::list<Interval> intervals;
|
|
for(std::list<Iso_rectangle_2>::iterator it = rectangles.begin();
|
|
it != rectangles.end();
|
|
++it){
|
|
if( CGAL::x_equal(it->vertex(0),it->vertex(2)) ||
|
|
CGAL::y_equal(it->vertex(0),it->vertex(2))){
|
|
ignore++;
|
|
} else {
|
|
intervals.push_back(Interval(it->vertex(0),it->vertex(2)));
|
|
}
|
|
}
|
|
std::cout << intervals.size() << std::endl;
|
|
|
|
if(ignore > 0){
|
|
std::cerr << "ignored " << ignore << " 1D rectangle" << std::endl;
|
|
}
|
|
|
|
std::list<Interval> output, N;
|
|
|
|
t.start();
|
|
Segment_tree_2_type segment_tree_2(intervals.begin(), intervals.end());
|
|
|
|
t.stop();
|
|
std::cerr << "Construction time t = " << t.time() << std::endl;
|
|
t.reset();
|
|
t.start();
|
|
// perform a window query
|
|
Interval a(Point_2(1.5, 1.5), Point_2(3.5, 4.5));
|
|
|
|
segment_tree_2.window_query(a, std::back_inserter(output));
|
|
|
|
t.stop();
|
|
std::cerr << "Window query time t = " << t.time() << std::endl;
|
|
|
|
// output of the querey elements on stdout
|
|
|
|
std::cout << "\n window_query " << Iso_rectangle_2(a.first, a.second) << std::endl;
|
|
for(std::list<Interval>::iterator j = output.begin();
|
|
j != output.end();
|
|
++j)
|
|
{
|
|
std::cout << Iso_rectangle_2(j->first, j->second) << std::endl;
|
|
}
|
|
|
|
std::cout << "\n enclosing_query " << Iso_rectangle_2(a.first, a.second) << std::endl;
|
|
|
|
t.reset();
|
|
t.start();
|
|
segment_tree_2.enclosing_query(a,std::back_inserter(N));
|
|
t.stop();
|
|
std::cerr << "Enclosing query time t = " << t.time() << std::endl;
|
|
|
|
for(std::list<Interval>::iterator eit = N.begin();
|
|
eit != N.end();
|
|
++eit)
|
|
{
|
|
std::cout << Iso_rectangle_2(eit->first, eit->second) << std::endl;
|
|
}
|
|
|
|
|
|
if(segment_tree_2.segment_tree_2->is_valid())
|
|
std::cout << "Tree is valid\n";
|
|
else
|
|
std::cout << "Tree is not valid\n";
|
|
|
|
|
|
std::cout << "done" << std::endl;
|
|
return 0;
|
|
}
|
|
|
|
|