chap35.htm

程序设计的艺术,此书是英文版的,经久不衰,非常的经典

is true. The rectangles must intersect in both dimensions. The first two comparisons above determine whether the rectangles intersect in <I>x;</I> the second two comparisons determine whether the rectangles intersect in <I>y</I>.<P>
The second stage in determining whether two line segments intersect decides whether each segment &quot;straddles&quot; the line containing the other. A segment <img src="889_o.gif"> <I><B>straddles</I></B> a line if point <I>p</I><SUB>1</SUB> lies on one side of the line and point <I>p</I><SUB>2</SUB> lies on the other side. If <I>p</I><SUB>1</SUB> or <I>p</I><SUB>2</SUB> lies on the line, then we say that the segment straddles the line. Two line segments intersect if and only if they pass the quick rejection test and each segment straddles the line containing the other.<P>
<img src="890_a.gif"><P>
<h4><a name="09e4_1c1f">Figure 35.3 Determining whether line segment <img src="890_b.gif"> straddles the line containing segment <img src="890_c.gif">. (a) If it does straddle, then the signs of the cross products (p<SUB>3</SUB> - p<SUB>1</SUB>) x (p<SUB>2</SUB> - p<SUB>1</SUB>) and (p<SUB>4</SUB> - p<SUB>1</SUB>) x (p<SUB>2</SUB> - p<SUB>1</SUB>) differ. (b) If it does not straddle, then the signs of the cross products are the same. (c)-(d) Boundary cases in which at least one of the cross products is zero and the segment straddles. (e) A boundary case in which the segments are collinear but do not intersect. Both cross products are zero, but they would not be computed by our algorithm because the segments fail the quick rejection test--their bounding boxes do not intersect.<a name="09e4_1c1f"></sub></sup></h4><P>
We can use the cross-product method to determine whether line segment <img src="890_d.gif"> straddles the line containing points <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB><I>.</I> The idea, as shown in Figures 35.3(a) and (b), is to determine whether directed segments <img src="890_e.gif"> and <img src="890_f.gif"> have opposite orientations relative to <img src="890_g.gif">. If so, then the segment straddles the line. Recalling that we can determine relative orientations with cross products, we just check whether the signs of the cross products (<I>p</I><SUB>3</SUB><I> - p</I><SUB>1</SUB>)<I> </I>X<I> </I>(<I>p</I><SUB>2</SUB><I> - p</I><SUB>1</SUB>) and (<I>p</I><SUB>4</SUB><I> - p</I><SUB>1</SUB>)<I> </I>X<I><SUB> </I></SUB>(<I>p</I><SUB>2</SUB><I> - p</I><SUB>1</SUB>)<I> </I>are different. A boundary condition occurs if either cross product is zero. In this case, either <I>p</I><SUB>3</SUB> or <I>p</I><SUB>4</SUB> lies on the line containing segment <img src="890_h.gif">. Because the two segments have already passed the quick rejection test, one of the points <I>p</I><SUB>3</SUB> and <I>p</I><SUB>4</SUB><I> </I>must in fact lie on segment <img src="890_i.gif">. Two such situations are shown in Figures 35.3(c) and (d). The case in which the two segments are collinear but do not intersect, shown in Figure 35.3(e), is eliminated by the quick rejection test. A final boundary condition occurs if one or both of the segments has zero length, that is, if its endpoints are coincident. If both segments have zero length, then the quick rejection test suffices. If just one segment, say <img src="890_j.gif">, has zero length, then the segments intersect if and only if the cross product (<I>p</I><SUB>3</SUB> - <I>p</I><SUB>1</SUB>) x (<I>p</I><SUB>2</SUB> - <I>p</I><SUB>1</SUB>) is zero.<P>
<P>







<h2>Other applications of cross products</h2><P>
Later sections of this chapter will introduce additional uses for cross products. In Section 35.3, we shall need to sort a set of points according to their polar angles with respect to a given origin. As Exercise 35.1-2 asks you to show, cross products can be used to perform the comparisons in the sorting procedure. In Section 35.2, we shall use red-black trees to maintain the vertical ordering of a set of nonintersecting line segments. Rather than keeping explicit key values, we shall replace each key comparison in the red-black tree code by a cross-product calculation to determine which of two segments that intersect a given vertical line is above the other.<P>
<P>







<h2><a name="09e6_1c24">Exercises<a name="09e6_1c24"></h2><P>
<a name="09e6_1c25">35.1-1<a name="09e6_1c25"><P>
Prove that if <I>p</I><SUB>1</SUB><I> </I>X<I> p</I><SUB>2</SUB> is positive, then vector <I>p</I><SUB>1</SUB> is clockwise from vector <I>p</I><SUB>2<FONT FACE="Times New Roman" SIZE=1> </FONT></SUB>with respect to the origin (0, 0) and that if this cross product is negative, then <I>p</I><SUB>1</SUB> is counterclockwise from <I>p</I><SUB>2</SUB>.<P>
<a name="09e6_1c26">35.1-2<a name="09e6_1c26"><P>
Write pseudocode to sort a sequence <img src="../images/lftwdchv.gif"><I><FONT FACE="Courier New" SIZE=2>p</I><SUB><FONT FACE="Courier New" SIZE=1>1</FONT></SUB>,<I> <FONT FACE="Courier New" SIZE=2>p</I><SUB><FONT FACE="Courier New" SIZE=1>2</FONT></SUB>,<I> . . . . ,<FONT FACE="Courier New" SIZE=2>p<SUB>n</SUB>)</I> </FONT></FONT></FONT>of <I>n</I> points according to their polar angles with respect to a given origin point <I>p</I><SUB><FONT FACE="Courier New" SIZE=2>0</FONT></SUB>. Your procedure should take <I>0(n </I>lg <I>n</I>) time and use cross products to compare angles.<P>
<a name="09e6_1c27">35.1-3<a name="09e6_1c27"><P>
<a name="09e6_1c21">Show how to determine in <I>0(n</I><SUP>2<FONT FACE="Times New Roman" SIZE=1> </FONT></SUP>1g <I>n</I>) time whether any three points in a set of <I>n</I> points are collinear.<P>
<a name="09e6_1c28">35.1-4<a name="09e6_1c28"><P>
Professor Amundsen proposes the following method to determine whether a sequence <img src="../images/lftwdchv.gif"><I>p</I><SUB>0</SUB>,<SUB><FONT FACE="Times New Roman" SIZE=1>  </SUB><I>p</I><SUB>1</FONT></SUB>,<SUB><FONT FACE="Times New Roman" SIZE=1> . . . . </FONT></SUB>, <I>p<SUB>n-</I>1</SUB><img src="../images/wdrtchv.gif"> of <I>n</I> points forms the consecutive vertices of a convex polygon. (See Section 16.4 for definitions pertaining to polygons.) Output &quot;yes&quot; if the set {<img src="../images/angle.gif"><I>p<SUB><FONT FACE="Courier New" SIZE=2>i</SUB>p<SUB>i + </I>1</SUB><I>p<SUB>i + </I>2 </FONT></SUB>:<I> i = </I>0<I>, </I>1<I>, . . . ,n - </I>1}, where subscript addition is performed modulo <I>n</I>, does not contain both left turns and right turns; otherwise, output &quot;no.&quot; Show that although this method runs in linear time, it does not always produce the correct answer. Modify the professor's method so that it always produces the correct answer in linear time.<P>
<a name="09e6_1c29">35.1-5<a name="09e6_1c29"><P>
Given a point <I>p</I><SUB>0</SUB><I> = </I>(<I>x</I><SUB>0</SUB><I>, y</I><SUB>0</SUB>), the <I><B>right horizontal ray</I></B> from <I>p</I><SUB>0</SUB> is the set of points { <I>p<SUB>i</SUB> = </I>(<I>x<SUB>i</SUB>, y<SUB>i</I></SUB>) :<I> x<SUB>i</SUB> </I><img src="../images/gteq.gif"><I> x</I><SUB>0</SUB> and <I>y<SUB>i</SUB> = y</I><SUB>0</SUB>}<I>, </I>that is, it is the set of points due right of <I>p</I><SUB>0</SUB> along with <I>p</I><SUB>0</SUB> itself. Show how to determine whether a given right horizontal ray from <I>p</I><SUB>0</SUB> intersects a line segment <img src="891_a.gif"> in <I>O</I>(1) time by reducing the problem to that of determining whether two line segments intersect.<P>
<a name="09e6_1c2a">35.1-6<a name="09e6_1c2a"><P>
<a name="09e6_1c22"><a name="09e6_1c23">One way to determine whether a point<I> p</I><SUB>0</SUB> is in the interior of a simple, but not necessarily convex, polygon <I>P</I> is to look at any ray from <I>p</I><SUB>0</SUB> and check that the ray intersects the boundary of <I>P</I> an odd number of times but that <I>p</I><SUB>0</SUB> itself is not on the boundary of <I>P</I>. Show how to compute in <img src="../images/bound.gif">(<I>n</I>) time whether a point <I>p</I><SUB>0</SUB> is in the interior of an <I>n-</I>vertex polygon <I>P. </I>(<I>Hint</I>: Use Exercise 35.1-5. Make sure your algorithm is correct when the ray intersects the polygon boundary at a vertex and when the ray overlaps a side of the polygon.)<P>
<a name="09e6_1c2b">35.1-7<a name="09e6_1c2b"><P>
Show how to compute the area of an <I>n-</I>vertex simple, but not necessarily convex, polygon in <img src="../images/bound.gif">(<I>n</I>) time.<P>
<P>


<P>







<h1><a name="09e7_1c28">35.2 Determining whether any pair of segments intersects<a name="09e7_1c28"></h1><P>
<a name="09e7_1c24"><a name="09e7_1c25">This section presents an algorithm for determining whether any two line segments in a set of segments intersect. The algorithm uses a technique known as &quot;sweeping,&quot; which is common to many computational-geometry algorithms. Moreover, as the exercises at the end of this section show, this algorithm, or simple variations of it, can be used to solve other computational-geometry problems. <P>
The algorithm runs in <I>O(n </I>lg<I> n)</I> time, where <I>n</I> is the number of segments we are given. It determines only whether or not any intersection exists; it does not print all the intersections. (By Exercise 35.2-1, it takes <img src="../images/omega12.gif">(<I>n<SUP><FONT FACE="Times New Roman" SIZE=1>2</I></FONT></SUP>) time in the worst case to find <I>all</I> the intersections in a set of <I>n</I> line segments.)<P>
<a name="09e7_1c26"><a name="09e7_1c27">In <I><B>sweeping</I></B>, an imaginary vertical <I><B>sweep line</I></B> passes through the given set of geometric objects, usually from left to right. The spatial dimension that the sweep line moves across, in this case the <I>x-</I>dimension, is treated as a dimension of time. Sweeping provides a method for ordering geometric objects, usually by placing them into a dynamic data structure, and for taking advantage of relationships among them. The line-segment-intersection algorithm in this section considers all the line-segment endpoints in left-to-right order and checks for an intersection each time it encounters an endpoint.<P>
Our algorithm for determining whether any two of <I>n</I> line segments intersect makes two simplifying assumptions. First, we assume that no input segment is vertical. Second, we assume that no three input segments intersect at a single point. (Exercise 35.2-8 asks you to describe an implementation that works even if these assumptions fail to hold.) Indeed, removing such simplifying assumptions and dealing with boundary conditions is often the most difficult part of programming computational-geometry algorithms and proving their correctness.<P>
<img src="893_a.gif"><P>
<h4><a name="09e7_1c29">Figure 35.4 The ordering among line segments at various vertical sweep lines. (a) We have a &gt;<SUB>r</SUB> c, a &gt;<SUB>t</SUB> b, b &gt;<SUB>t</SUB> c, a &gt;<SUB>t</SUB> c, and b &gt;<SUB>u</SUB> c. Segment d is comparable with no other segment shown. (b) When segments e and f intersect, their orders are reversed: we have e &gt;<SUB>v</SUB> f but f &gt;<SUB>w</SUB> e. Any sweep line (such as z) that passes through the shaded region has e and f consecutive in its total order.<a name="09e7_1c29"></sub></sup></h4><P>





<h2>Ordering segments</h2><P>
Since we assume that there are no vertical segments, any input segment that intersects a given vertical sweep line intersects it at a single point. We can thus order the segments that intersect a vertical sweep line according to the <I>y</I>-coordinates of the points of intersection. <P>