Bentley-Otmann Algorithm: bentley_ottmann.hpp Source File

Bentley-Otmann Algorithm 2.0

An implementation of Bentley-Ottmann algorithm in order to count the m,n-cubes

00001 
00008 #ifndef H_BEN_OTT
00009 #define H_BEN_OTT
00010 
00011 #include <vector>
00012 #include <map>
00013 #include <utility>
00014 #include "geometry.hpp"
00015 #include "structures.hpp"
00016 
00023 typedef std::map<Event, std::vector<Segment*> > map_event;
00024 
00028 typedef std::pair<Event, std::vector<Segment*> > pair_event;
00029 
00033 typedef std::vector<Segment*> vector_seg;
00034 
00035 map_event bentley_ottmann(std::vector<Segment>&);
00036 void find_neighboors(const Point&,BST<Segment,Point>::Type&,Segment*&,Segment*&);
00037 Segment* find_leftmost(vector_seg&,const Point&);
00038 Segment* find_rightmost(vector_seg&,const Point&);
00039 Segment* find_left_neighboor(Segment*,BST<Segment,Point>::Type&);
00040 Segment* find_right_neighboor(Segment*,BST<Segment,Point>::Type&);
00041 std::pair<vector_seg, vector_seg> get_sets(const Point&,BST<Segment,Point>::Type&);
00042 void compute_new_events(Segment*, Segment*,const Event&,PriorityQueue<Event,Segment*>&);
00043 
00044 
00045 #endif //H_BEN_OTT