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 ( segitem ). Every item in S contains as key a line segment with a fixed direction (see data type segment) and an information from data type I , called the information type of S . 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 > S .

#include < LEDA/geo/segment_set.h >

Creation

 segment_set< I> S creates an empty instance S of type segment_set with orientation zero, i.e., horizontal segments. segment_set< I> S(int rot) creates an empty instance S of type segment_set with orientation rot*/2 . segment_set< I> S(double a) creates an empty instance S of type segment_set 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 >    S with s q! = . 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 >    S with s l! = . 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[ ] 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: Sets of Parallel Rational Up: Advanced Data Types for Previous: Sets of Intervals (   Contents   Index
Christian Uhrig 2017-04-07