开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
segment_set.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：5k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

segment_set.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  segment_set.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #ifndef LEDA_SEGMENT_SET_H
  14. #define LEDA_SEGMENT_SET_H
  16. #include <LEDA/impl/seg_tree.h>
  17. #include <LEDA/line.h>
  19. typedef seg_tree_item seg_item;
  21. typedef list<seg_item> list_seg_item_;
  24. //------------------------------------------------------------------------------
  25. // SegmentSet: a dictionary for line segments  with a fixed orientation
  26. //------------------------------------------------------------------------------
  28. class SegmentSet : public segment_tree<double,double,GenPtr> {
  30. double alpha;           // orientation given by an angle
  32. public:
  33.  
  34. segment  key(seg_item);
  36. seg_item insert(segment, GenPtr);
  37. seg_item lookup(segment);
  38. void     del(segment);
  40. list<seg_item>  intersection(segment);
  41. list<seg_item>  intersection(line);
  42.  
  43. void clear() { clear_tree(); }
  45.  SegmentSet(double a=0)  { alpha =a; }
  46. ~SegmentSet()  {}
  47. };
  49. #define forall_seg_items(i,S) forall_seg_tree_items(i,S)
  52. //------------------------------------------------------------------------------
  53. // class segment_set: generic SegmentSet
  54. //------------------------------------------------------------------------------
  56.  
  57. /*{Manpage {segment_set} {I} {Sets of Parallel Segments}}*/
  59. template<class I>
  61. class segment_set : public SegmentSet {
  63. /*{Mdefinition
  64.     An instance $S$ of the parameterized data type name is a 
  65.     collection of items ($seg_item$). Every item in $S$ contains as key a
  66.     line segment with a fixed direction $alpha$ (see data type segment) and
  67.     an information from data type $I$, called the information type of $S$.
  68.     $alpha$ is called the orientation of $S$. We use $<s,i>$ to denote the
  69.     item with segment $s$ and information $i$. For each segment $s$ there is
  70.     at most one item $<s,i> in S$.}*/
  72. public:
  74. /*{Mcreation S }*/
  76. segment_set(double a) : SegmentSet(a) {}
  77. /*{Mcreate creates an empty instance var of type name with orientation 
  78.             $a$. }*/
  80. segment_set() : SegmentSet(0) {}
  81. /*{Mcreate creates an empty instance var of type name with orientation 
  82.             zero, i.e., horizontal segments.}*/
  83.     
  84. ~segment_set()  {}
  87. /*{Moperations 2.7 4.5}*/
  89. segment key(seg_item it) {return SegmentSet::key(it);}
  90. /*{Mop   returns the segment of item $it$.\
  91.   precond $it$ is an item in var.}*/
  93. I inf(seg_item it)  { return LEDA_ACCESS(I,SegmentSet::inf(it));  }
  94. /*{Mop   returns the information of item $it$.\
  95.   precond $it$ is an item in var.}*/
  97. seg_item insert(segment s, I i)   { return SegmentSet::insert(s,Copy(i));}
  98. /*{Mop   associates the information $i$ with segment 
  99.   $s$. If there is an item $<s,j>$ in var  
  100.   then $j$ is replaced by $i$, else a new item
  101.   $<s,i>$ is added to $S$. In both cases the
  102.   item is returned.}*/
  104. seg_item lookup(segment s) {return SegmentSet::lookup(s);}
  105. /*{Mop   returns the item with segment $s$ (nil if no 
  106.   such item exists in var).}*/
  108. list<seg_item> intersection(segment q) {return SegmentSet::intersection(q);}
  109. /*{Mop   returns all items $<s,i> in S$ with 
  110.   $s cap q neq emptyset$.\
  111.   precond $q$ is 
  112.   orthogonal to the segments in var.}*/
  114. list<seg_item> intersection(line l) {return SegmentSet::intersection(l);}
  115. /*{Mop   returns all items $<s,i> in S$ with 
  116.   $s cap l neq emptyset$. precond $l$ is 
  117.   orthogonal to the segments in var.}*/
  119. void del(segment s) {SegmentSet::del(s);}
  120. /*{Mop   deletes the item with segment $s$ from var.}*/
  122. void del_item(seg_item it) {SegmentSet::del_item(it);}
  123. /*{Mop   removes item $it$ from var.\
  124.   precond $it$ is an item in var.}*/
  126. void  change_inf(seg_item it, I i) { SegmentSet::change_inf(it,Copy(i)); }
  127. /*{Mopl  makes $i$ the information of item $it$.\ 
  128.   precond $it$ is an item in var.}*/
  130. void clear() { SegmentSet::clear(); }
  131. /*{Mop   makes var the empty segment_set.}*/
  133. bool empty() {return SegmentSet::empty();}
  134. /*{Mop   returns true iff var is empty.}*/
  136. int size() {return SegmentSet::size();}
  137. /*{Mop   returns the size of var.}*/
  139. };
  140.  
  141. /*{Mimplementation
  142. Segment sets are implemented by dynamic segment trees based on BB[$alpha$]
  143. trees (cite{Wi85,Lu78}) trees. Operations key, inf, change_inf, empty, and 
  144. size take time $O(1)$, insert, lookup, del, and del_item take time 
  145. $O(log^2 n)$ and an intersection operation takes time $O(k + log^2 n)$, 
  146. where $k$ is the size of the returned list. Here $n$ is the current size of 
  147. the set. The space requirement is $O(nlog n)$.}*/
  149.  
  150. #endif