chap35.htm

介绍算法的书籍

          <a name="09e8_1c28"><a name="09e8_1c29">To be more precise, consider two nonintersecting segments <I>s</I><SUB><FONT FACE="Times New Roman" SIZE=1>1</FONT></SUB> and <I>s</I><SUB><FONT FACE="Times New Roman" SIZE=1>2 </FONT></SUB>We say that these segments are <I><B>comparable</I></B> at<I> x</I> if the vertical sweep line with <I>x-</I>coordinate <I>x</I> intersects both of them. We say that <I>s<SUB>l</SUB></I> is <B>above<I></B></I> <I>s</I><SUB>2 </SUB>at <I>x</I>, written <I>s<SUB>1</SUB></I> &gt; X <I>s</I><SUB>2</SUB>, if <I>s</I><SUB><FONT FACE="Times New Roman" SIZE=1>1</FONT></SUB> and <I>s</I><SUB><FONT FACE="Times New Roman" SIZE=1>2</FONT></SUB> are comparable at <I>x</I> and the intersection of <I>s</I><SUB><FONT FACE="Times New Roman" SIZE=1>1</FONT></SUB> with the sweep line at <I>x</I> is higher than the intersection of <I>s</I><SUB><FONT FACE="Times New Roman" SIZE=1>2</FONT></SUB> with the same sweep line. In Figure 35.4(a), for example, we have the relationships <I>a &gt;<SUB><FONT FACE="Courier New" SIZE=2>r</SUB> c, a &gt;<SUB>t</SUB> b, b &gt;<SUB>t</SUB> c, a &gt;<SUB>t</SUB> c, </I></FONT>and<I> b &gt;<SUB><FONT FACE="Courier New" SIZE=2>u</SUB> c.</I></FONT> Segment <I>d</I> is not comparable with any other segment.<P>
For any given <I>x</I>, the relation &quot;&gt;<I><SUB>x</SUB></I>" is a total order (see Section 5.2) on segments that intersect the sweep line at X<SUB>.</SUB> The order may differ for differing values of <I>x</I><SUB>,</SUB> however, as segments enter and leave the ordering. A segment enters the ordering when its left endpoint is encountered by the sweep, and it leaves the ordering when its right endpoint is encountered.<P>
What happens when the sweep line passes through the intersection of two segments? As Figure 35.4(b) shows, their positions in the total order are reversed. Sweep lines <I>v</I> and <I>w</I> are to the left and right, respectively, of the point of intersection of segments <I>e</I> and <I>f</I>, and we have <I>e &gt;<SUB>v</SUB> f</I> and <I>f &gt;<SUB>w</SUB> e.</I> Note that because we assume that no three segments intersect at the same point, there must be some vertical sweep line <I>x</I> for which intersecting segments <I>e</I> and <I>f</I> are <I>consecutive</I> in the total order &gt;<I><SUB>x</I></SUB>. Any sweep line that passes through the shaded region of Figure 35.4(b), such as <I>z</I>, has <I>e</I> and <I>f</I> consecutive in its total order.<P>
<P>







<h2>Moving the sweep line</h2><P>
Sweeping algorithms typically manage two sets of data:<P>
<a name="09e9_1c2a">1.     The <I><B>sweep-line status</I></B> gives the relationships among the objects intersected by the sweep line. <P>
<a name="09e9_1c2b">2.     The <I><B>event-point schedule</I></B> is a sequence of <I>x-</I>coordinates, ordered from left to right, that defines the halting positions of the sweep line. We call each such halting position an <I><B>event point</I></B>. Changes to the sweep-line status occur only at event points.<P>
<a name="09e9_1c2c"><a name="09e9_1c2d">For some algorithms (the algorithm asked for in Exercise 35.2-7, for example), the event-point schedule is determined dynamically as the algorithm progresses. The algorithm at hand, however, determines the event points statically, based solely on simple properties of the input data. In particular, each segment endpoint is an event point. We sort the segment endpoints by increasing <I>x</I>-coordinate and proceed from left to right. We insert a segment into the sweep-line status when its left endpoint is encountered, and we delete it from the sweep-line status when its right endpoint is encountered. Whenever two segments first become consecutive in the total order, we check whether they intersect.<P>
The sweep-line status is a total order <I>T</I>, for which we require the following operations:<P>
<img src="../images/dot12.gif">     <FONT FACE="Courier New" SIZE=2>INSERT</FONT>(<I>T,</I> <I>s</I>): insert segment <I>s</I> into <I>T.</I><P>
<img src="../images/dot12.gif">     <FONT FACE="Courier New" SIZE=2>DELETE</FONT>(<I>T</I>, <I>s</I>): delete segment <I>s</I> from <I>T.</I><P>
<a name="09e9_1c2e"><img src="../images/dot12.gif">     <FONT FACE="Courier New" SIZE=2>ABOVE</FONT>(<I>T</I>, <I>s</I>): return the segment immediately above segment <I>s</I> in <I>T.</I><P>
<a name="09e9_1c2f"><img src="../images/dot12.gif">     <FONT FACE="Courier New" SIZE=2>BELOW</FONT>(<I>T</I>, <I>s</I>): return the segment immediately below segment <I>s</I> in <I>T.</I><P>
<a name="09e9_1c30">If there are <I>n</I> segments in the input, we can perform each of the above operations in <I>O(</I>lg <I>n)</I> time using red-black trees. Recall that the red-black-tree operations in Chapter 14 involve comparing keys. We can replace the key comparisons by cross-product comparisons that determine the relative ordering of two segments (see Exercise 35.2-2).<P>
<P>







<h2>Segment-intersection pseudocode</h2><P>
The following algorithm takes as input a set <I>S</I> of <I>n</I> line segments, returning the boolean value <FONT FACE="Courier New" SIZE=1>TRUE</FONT> if any pair of segments in <I>S</I> intersects, and <FONT FACE="Courier New" SIZE=2>FALSE </FONT>otherwise. The total order <I>T</I> is implemented by a red-black tree.<P>
<img src="895_a.gif"><P>
<h4><a name="09ea_1c32">Figure 35.5 The execution of <FONT FACE="Courier New" SIZE=2>ANY-SEGMENTS-INTERSECT</FONT>. Each dashed line is the sweep line at an event point, and the ordering of segment names below each sweep line is the total order T at the end of the for loop in which the corresponding event point is processed. The intersection of segments d and b is found when segment c is deleted.<a name="09ea_1c32"></sub></sup></h4><P>
<pre><a name="09ea_1c31">ANY-SEGMENTS-INTERSECT(<I>S</I>)</sub></sup></pre><P>
<img src="895_b.gif"><P>
<pre>2  sort the endpoints of the segments in <I>S</I> from left to right,</sub></sup></pre><P>
<pre>breaking ties by putting points with lower <I>y</I>-coordinates first</sub></sup></pre><P>
<pre>3  <B>for</B> each point <I>p</I> in the sorted list of endpoints</sub></sup></pre><P>
<pre>4      <B>do if</B> <I>p</I> is the left endpoint of a segment <I>s</I></sub></sup></pre><P>
<pre>5            <B>then</B> INSERT(<I>T</I>, <I>s</I>)</sub></sup></pre><P>
<pre>6                 <B>if</B> (ABOVE(<I>T</I>, <I>s</I>) exists and intersects <I>s</I>)</sub></sup></pre><P>
<pre>or (BELOW(<I>T</I>, <I>s</I>) exists and intersects <I>s</I>)</sub></sup></pre><P>
<pre>7                    <B>then return</B> TRUE</sub></sup></pre><P>
<pre>8                 <B>if</B> <I>p</I> is the right endpoint of a segment <I>s</I></sub></sup></pre><P>
<pre>9                    <B>then if</B> both ABOVE(<I>T</I>, <I>s</I>) and BELOW(<I>T</I>, <I>s</I>) exist</sub></sup></pre><P>
<pre>and ABOVE(<I>T</I>, <I>s</I>) intersects BELOW(<I>T</I>, <I>s</I>)</sub></sup></pre><P>
<pre>10                            <B>then return</B> TRUE</sub></sup></pre><P>
<pre>11                         DELETE(<I>T</I>, <I>s</I>)</sub></sup></pre><P>
<pre>12  <B>return</B> FALSE</sub></sup></pre><P>
Figure 35.5 illustrates the execution of the algorithm. Line 1 initializes the total order to be empty. Line 2 determines the event-point schedule by sorting the 2<I>n</I> segment endpoints from left to right, breaking ties by putting points with lower <I>y</I>-coordinates first. Note that line 2 can be performed by lexicographically sorting the endpoints on <I>(x, y).</I><P>
Each iteration of the <B>for</B> loop of lines 3-11 processes one event point <I>p</I>. If <I>p</I> is the left endpoint of a segment <I>s</I>, line 5 adds <I>s </I>to the total order, and lines 6-7 return <FONT FACE="Courier New" SIZE=1>TRUE</FONT> if <I>s</I> intersects either of the segments it is consecutive with in the total order defined by the sweep line passing through <I>p. </I>(A boundary condition occurs if <I>p</I> lies on another segment s'. In this case, we only require that <I>s</I> and <I>s</I><I>'</I> be placed consecutively into <I>T.</I>) If <I>p </I>is the right endpoint of a segment <I>s</I>, then <I>s</I> is to be deleted from the total order. Lines 9-10 return <FONT FACE="Courier New" SIZE=1>TRUE</FONT> if there is an intersection between the segments surrounding <I>s</I> in the total order defined by the sweep line passing through <I>p;</I> these segments will become consecutive in the total order when <I>s</I> is deleted. If these segments do not intersect, line 11 deletes segment <I>s</I> from the total order. Finally, if no intersections are found in processing all the 2<I>n</I> event points, line 12 returns <FONT FACE="Courier New" SIZE=2>FALSE<FONT FACE="Times New Roman" SIZE=2>.</FONT></FONT><P>
<P>







<h2>Correctness</h2><P>
The following theorem shows that <FONT FACE="Courier New" SIZE=2>ANY</FONT>-<FONT FACE="Courier New" SIZE=2>SEGMENTS</FONT>-<FONT FACE="Courier New" SIZE=2>INTERSECT</FONT> is correct.<P>
<a name="09eb_0001">Theorem 35.1<a name="09eb_0001"><P>