Definition
An instance S of the parameterized data type rat_segment_set<I> is a collection of items ( segitem). Every item in S contains as key a rational line segment with a fixed direction (see data type rat_segment) and an information from data type I, called the information type of S. is called the orientation of S, it must be a multiple of /2. We use < s, i > to denote the item with segment s and information i. For each segment s there is at most one item < s, i > S.
#include < LEDA/geo/rat_segment_set.h >
Creation
rat_segment_set<I> | S | creates an empty instance S of type rat_segment_set<I> with orientation zero, i.e., horizontal segments. |
rat_segment_set<I> | S(int rot) | creates an empty instance S of type rat_segment_set<I> with orientation rot*/2. |
Operations
rat_segment | S.key(seg_item it) | returns the segment of item it.
Precondition it is an item in S. |
const I& | S.inf(seg_item it) | returns the information of item it.
Precondition it is an item in S. |
seg_item | S.insert(const rat_segment& s, const I& i) | |
associates the information i with segment s. If there is an item < s, j > in S then j is replaced by i, else a new item < s, i > is added to S. In both cases the item is returned. | ||
seg_item | S.lookup(const rat_segment& s) | |
returns the item with segment s (nil if no such item exists in S). | ||
list<seg_item> | S.intersection(const rat_segment& q) | |
returns all items
< s, i > S with
s q! = .
Precondition q is orthogonal to the segments in S. |
||
list<seg_item> | S.intersection_sorted(const rat_segment& q) | |
as above, but the returned segments are ordered as they are intersected by q if one travels from q.source() to q.target(). | ||
list<seg_item> | S.intersection(const rat_line& l) | |
returns all items
< s, i > S with
s l! = .
Precondition l is orthogonal to the segments in S. |
||
list<seg_item> | S.intersection_sorted(const rat_line& l) | |
as above, but the returned segments are ordered as they are intersected by l if one travels along l in direction l.direction(). | ||
void | S.del(const rat_segment& s) | |
deletes the item with segment s from S. | ||
void | S.del_item(seg_item it) | removes item it from S.
Precondition it is an item in S. |
void | S.change_inf(seg_item it, const I& i) | |
makes i the information of item it.
Precondition it is an item in S. |
||
void | S.clear() | makes S the empty rat_segment_set. |
bool | S.empty() | returns true iff S is empty. |
int | S.size() | returns the size of S. |
Implementation
Segment sets are implemented by dynamic segment trees based on BB[] trees ([90,57]) trees. Operations key, inf, change_inf, empty, and size take time O(1), insert, lookup, del, and del_item take time O(log^{2}n) and an intersection operation takes time O(k + log^{2}n), where k is the size of the returned list. Here n is the current size of the set. The space requirement is O(n log n).