next up previous contents index
Next: Planar Subdivisions ( subdivision Up: Advanced Data Types for Previous: Sets of Parallel Segments   Contents   Index


Sets of Parallel Rational Segments ( rat_segment_set )

Definition

An instance S of the parameterized data type rat_segment_set<I> is a collection of items ( seg$\_$item). Every item in S contains as key a rational line segment with a fixed direction $\alpha$ (see data type rat_segment) and an information from data type I, called the information type of S. $\alpha$ is called the orientation of S, it must be a multiple of $\pi$/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 > $\in$ 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*$\pi$/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 >   $\in$  S with s $\cap$ q! = $\emptyset$.
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 >   $\in$  S with s $\cap$ l! = $\emptyset$.
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[$\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: Planar Subdivisions ( subdivision Up: Advanced Data Types for Previous: Sets of Parallel Segments   Contents   Index