next up previous contents index
Next: Sets of Parallel Rational Up: Advanced Data Types for Previous: Sets of Intervals (   Contents   Index


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(log2n) and an intersection operation takes time O(k + log2n), 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).


next up previous contents index
Next: Sets of Parallel Rational Up: Advanced Data Types for Previous: Sets of Intervals (   Contents   Index
root 2008-01-09