home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / plane_al.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  2.3 KB  |  64 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 6.1.6 Algorithms }
  4.  
  5. %\bigskip
  6. %$\bullet$ {\bf Line sweep for straight line segments}
  7. %\medskip
  8. %\cleartabs
  9. %\+$void$\quad SWEEP\_SEGMENTS(&$list(segment)\&\ L_1$,\cr
  10. %\+                            &$list(segment)\&\ L_2$,\cr
  11. %\+                            &$GRAPH(point,int)\&\ G$ ) \cr
  12. %
  13. %SWEEP\_SEGMENTS takes as input two lists $L_1$ and $L_2$ of straight
  14. %line segments and performs a plane sweep to construct the arrangement $G$ 
  15. %defined by these segments. Each node $v$  of $G$ corresponds to a point of 
  16. %intersection $G$.inf($v$) between two segments in $S = L_1 \cup L_2$. Every 
  17. %edge  $e=(v,w)$ represents the part the segment $s \in S$ connecting 
  18. %intersection points $G$.inf($v$) and $G$.inf($w$). With $e$ is associated an 
  19. %integer information $G$.inf($e$) which is equal to 0 if $s \in L_1$ and equal 
  20. %to 1 if $s \in L_2$. The direction of $e$ corresponds to the direction of $s$.
  21. %
  22. %Running Time: $O((n+k)\log n)$ , where $n$ is the total number of segments,
  23. %and $k$ is the number of intersections.
  24. %
  25.  
  26. \bigskip
  27. $\bullet$ {\bf Line segment intersection}
  28.  
  29. $void$\quad SEGMENT\_INTERSECTION($list(segment)\&\ L,\ list(point)\&\ P$);
  30.  
  31. SEGMENT\_INTERSECTION takes a list of segments $L$ as input and computes 
  32. the list of intersection points between all segments in $L$.
  33.  
  34. Running Time: $O((n+k)\log n)$ , where $n$ is the number of segments,
  35. and $k$ is the number of intersections.
  36.  
  37.  
  38.  
  39. \bigskip
  40. $\bullet$ {\bf Convex hull of point set}
  41.  
  42. $polygon$\quad CONVEX\_HULL($list(point)\ L$);
  43.  
  44. CONVEX\_HULL takes as argument a list of points and returns the polygon
  45. representing the convex hull of $L$. It is based on a randomized incremental 
  46. algorithm. 
  47.  
  48. Running Time: $O(n\log n)$ (with high probability), where $n$ is the number 
  49. of segments.
  50.  
  51.  
  52. \bigskip
  53. $\bullet$ {\bf Voronoi Diagrams}
  54. \medskip
  55. $void$\quad VORONOI$(list(point)\&\ sites,\ real\ R,\ GRAPH(point,point)\&\ G)$
  56.  
  57. VORONOI takes as input a list of points  $sites$ and a real number 
  58. $R$. It computes a directed graph $G$ representing the planar subdivision
  59. defined by the Voronoi-diagram of $sites$ where all ``infinite" edges have
  60. length $R$. For each node $v$ $G$.inf($v$) is the corresponding Voronoi 
  61. vertex ($point$) and for each edge $e$  $G$.inf($e$) is the site ($point$) 
  62. whose Voronoi region is bounded by $e$. 
  63.  
  64.