Sets of Parallel Segments ( segment_set )

Definition

An instance S of the parameterized data type segment_set<I> is a collection of items ( seg$\_$item). Every item in S contains as key a line segment with a fixed direction $\alpha$ (see data type segment) and an information from data type I, called the information type of S. $\alpha$ is called the orientation of S. 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 > $\in$ S.

#include < LEDA/geo/segment_set.h >

Creation

segment_set<I>	S	creates an empty instance S of type segment_set<I> with orientation zero, i.e., horizontal segments.
segment_set<I>	S(int rot)	creates an empty instance S of type segment_set<I> with orientation rot*$\pi$/2.
segment_set<I>	S(double a)	creates an empty instance S of type segment_set<I> with orientation a. (Note that there may be incorrect results due to rounding errors.)

Operations

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 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 segment& s)
		returns the item with segment s (nil if no such item exists in S).
list<seg_item>	S.intersection(const segment& q)
		returns all items < s, i >   $\in$  S with s $\cap$ q! = $\emptyset$. Precondition q is orthogonal to the segments in S.
list<seg_item>	S.intersection_sorted(const 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 line& l)
		returns all items < s, i >   $\in$  S with s $\cap$ l! = $\emptyset$. Precondition l is orthogonal to the segments in S.
list<seg_item>	S.intersection_sorted(const 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 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 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[$\alpha$] 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²n) and an intersection operation takes time O(k + log²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).