Bentley-Otmann Algorithm 2.0
An implementation of Bentley-Ottmann algorithm in order to count the m,n-cubes
|
Some declarations use in bentley_ottmann.cpp. More...
#include <vector>
#include <map>
#include <utility>
#include "geometry.hpp"
#include "structures.hpp"
Go to the source code of this file.
Typedefs | |
typedef std::map< Event, std::vector< Segment * > > | map_event |
Map for events. | |
typedef std::pair< Event, std::vector< Segment * > > | pair_event |
Element type of map_event. | |
typedef std::vector< Segment * > | vector_seg |
Vector of Segment*. | |
Functions | |
map_event | bentley_ottmann (std::vector< Segment > &) |
Computes all the intersections between segment lines of set. | |
void | find_neighboors (const Point &, BST< Segment, Point >::Type &, Segment *&, Segment *&) |
Find the two neighboors of a point. | |
Segment * | find_leftmost (vector_seg &, const Point &) |
Finds the lower segment. | |
Segment * | find_rightmost (vector_seg &, const Point &) |
Finds the upper segment. | |
Segment * | find_left_neighboor (Segment *, BST< Segment, Point >::Type &) |
Finds the lower neighboor of a segment in a BST. | |
Segment * | find_right_neighboor (Segment *, BST< Segment, Point >::Type &) |
Finds the upper neighboor of a segment in a BST. | |
std::pair< vector_seg, vector_seg > | get_sets (const Point &, BST< Segment, Point >::Type &) |
All segment lines containing a given point. | |
void | compute_new_events (Segment *, Segment *, const Event &, PriorityQueue< Event, Segment * > &) |
Compute new events. |
Some declarations use in bentley_ottmann.cpp.
Definition in file bentley_ottmann.hpp.
Map for events.
Map containing events associated to a vector of segment lines : those which are crossing in this point.
Definition at line 23 of file bentley_ottmann.hpp.
Computes all the intersections between segment lines of set.
set | Set of segment lines (implemented as Segment instances) |
Remark : the only Segment instances used are those in set ; to compute the algorithm, we use pointers on Segment-s in order no to copy all those data.
Definition at line 118 of file bentley_ottmann.cpp.
void compute_new_events | ( | Segment * | s0, |
Segment * | s1, | ||
const Event & | p, | ||
PriorityQueue< Event, Segment * > & | q | ||
) |
Compute new events.
s0,s1 | Pointers on segment lines potentially introducing new events. |
p | Current event : only events on the right of this one are relevant. |
q | Priority queue which into the new events are pushed. |
First are checked s0 and s1 for equality to NULL. Next, lazily, s0 and s1 are checked for intersection. Next, lazily again, is checked the intersection to be relevant or not. Finally, the event are pushed into the queue.
Definition at line 357 of file bentley_ottmann.cpp.
Finds the lower neighboor of a segment in a BST.
s | Pointer on the segment whose lower neighboor is wanted. |
btree | BST ordering the segment at the given time. |
Definition at line 278 of file bentley_ottmann.cpp.
Segment* find_leftmost | ( | vector_seg & | v, |
const Point & | p | ||
) |
Finds the lower segment.
v | Non empty vector which for the lower segment is wanted. |
p | Point setting the order on segment |
This is just a classical search for minimum in a vector v.
Definition at line 240 of file bentley_ottmann.cpp.
void find_neighboors | ( | const Point & | p, |
BST< Segment, Point >::Type & | btree, | ||
Segment *& | above, | ||
Segment *& | below | ||
) |
Find the two neighboors of a point.
p | Point that neighboors are searched for. |
btree | Binary search tree used to order segments. |
above,below | Two pointers use two store the potential neighboors. |
This function create a segment of length 0, so a point, anchored in p. In the tree, we search for the upper bound of the segment, getting this way the upper neighboor (if exists). The lower neighboor is now (if exists) the one just before the upper neighboor. That's what this function strictely does.
Definition at line 213 of file bentley_ottmann.cpp.
Finds the upper neighboor of a segment in a BST.
s | Pointer on the segment whose upper neighboor is wanted. |
btree | BST ordering the segment at the given time. |
Definition at line 292 of file bentley_ottmann.cpp.
Segment* find_rightmost | ( | vector_seg & | v, |
const Point & | p | ||
) |
Finds the upper segment.
v | Non empty vector which for the upper segment is wanted. |
p | Point setting the order on segment |
This is just a classical search for maximum in a vector v.
Definition at line 260 of file bentley_ottmann.cpp.
std::pair<vector_seg, vector_seg> get_sets | ( | const Point & | p, |
BST< Segment, Point >::Type & | btree | ||
) |
All segment lines containing a given point.
p | Point contained in the wanted segment lines. |
btree | BST ordering the segment at the given time. |
We use here the following trick : we first create a vertical segment line of length 0 anchored in p ; this segment line have a slope of value infinity and so is greather than any segment line going through p except maybe some other vertical segment line containing p ; that kind of vertical segment line is limited to a single element because we do not accept overlapping segment (undefined comportement of the algorithm) ; so having the upper bound of the segment line with length 0 assure us to point on the greatest segment line containing p ; it just remains to back browsing the BST structure because all the segment containing p are adjacent in the tree.
Definition at line 320 of file bentley_ottmann.cpp.