📄 chap35.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 35: COMPUTATIONAL GEOMETRY</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap36.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="chap34.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="09df_1c10">CHAPTER 35: COMPUTATIONAL GEOMETRY<a name="09df_1c10"></h1><P>
<a name="09df_1c0e"><a name="09df_1c0f">Computational geometry is the branch of computer science that studies algorithms for solving geometric problems. In modern engineering and mathematics, computational geometry has applications in, among other fields, computer graphics, robotics, VLSI design, computer-aided design, and statistics. The input to a computational-geometry problem is typically a description of a set of geometric objects, such as a set of points, a set of line segments, or the vertices of a polygon in counterclockwise order. The output is often a response to a query about the objects, such as whether any of the lines intersect, or perhaps a new geometric object, such as the convex hull (smallest enclosing convex polygon) of the set of points.<P>
In this chapter, we look at a few computational-geometry algorithms in two dimensions, that is, in the plane. Each input object is represented as a set of points {<I>p<SUB>i</I></SUB>}, where each <I>p<SUB>i</I></SUB> = (<I>x<SUB>i</SUB>, y<SUB>i</I></SUB>) and <I>x<SUB>i</SUB>, y<SUB>i</I></SUB> <img src="../images/memof12.gif"> <B>R</B>. For example, an <I>n</I>-vertex polygon <I>P </I>is represented by a sequence <img src="../images/lftwdchv.gif"><I>p</I><SUB>0</SUB>,<I> p</I><SUB>1</SUB>,<I> p</I><SUB>2</SUB>,<I> . . . </I>,<I> p<SUB>n</I>-1</SUB><img src="../images/wdrtchv.gif"><SUB></SUB> of its vertices in order of their appearance on the boundary of <I>P</I>. Computational geometry can also be performed in three dimensions, and even in higher- dimensional spaces, but such problems and their solutions can be very difficult to visualize. Even in two dimensions, however, we can see a good sample of computational-geometry techniques.<P>
Section 35.1 shows how to answer simple questions about line segments efficiently and accurately: whether one segment is clockwise or counterclockwise from another that shares an endpoint, which way we turn when traversing two adjoining line segments, and whether two line segments intersect. Section 35.2 presents a technique called "sweeping" that we use to develop an <I>O</I>(<I>n </I>l<I>g n</I>)-time algorithm for determining whether there are any intersections among a set of <I>n</I> line segments. Section 35.3 gives two "rotational-sweep" algorithms that compute the convex hull (smallest enclosing convex polygon) of a set of <I>n</I> points: Graham's scan, which runs in time <I>O</I>(<I>n</I> 1g <I>n</I>), and Jarvis's march, which takes <I>O</I>(<I>nh</I>) time, where <I>h</I> is the number of vertices of the convex hull. Finally, Section 35.4 gives an <I>O</I>(<I>n</I> 1g <I>n</I>)-time divide-and-conquer algorithm for finding the closest pair of points in a set of <I>n</I> points in the plane.<P>
<h1><a name="09e1_1c16">35.1 Line-segment properties<a name="09e1_1c16"></h1><P>
<a name="09e1_1c10"><a name="09e1_1c11"><a name="09e1_1c12"><a name="09e1_1c13"><a name="09e1_1c14"><a name="09e1_1c15">Several of the computational-geometry algorithms in this chapter will require answers to questions about the properties of line segments. A <I><B>convex combination</I></B> of two distinct points <I>p</I><SUB>1</SUB> = (<I>x</I><SUB>1</SUB>, <I>y</I><SUB>1</SUB>) and <I>p</I><SUB>2</SUB> = (<I>x</I><SUB>2</SUB>, <I>y</I><SUB>2</SUB>) is any point <I>p</I><SUB>3</SUB> = (<I>x</I><SUB>3</SUB>, <I>y</I><SUB>3</SUB>) such that for some <img src="../images/alpha12.gif"> in the range 0 <img src="../images/lteq12.gif"> <img src="../images/alpha12.gif"> <img src="../images/lteq12.gif"> 1, we have <I>x</I><SUB>3</SUB> = <I>ax</I><SUB>1</SUB> + (1 - <img src="../images/alpha12.gif">)<I>x</I><SUB>2</SUB> and <I>y</I><SUB>3</SUB> = <img src="../images/alpha12.gif"> <I>y</I><SUB>1</SUB> + (1 - <img src="../images/alpha12.gif">)<I>y</I><SUB>2.</SUB> We also write that <I>p</I><SUB>3</SUB> = <img src="../images/alpha12.gif"><I>p</I><SUB>1</SUB> + (1 - <img src="../images/alpha12.gif">)<I>p</I><SUB>2.</SUB> Intuitively, <I>p</I><SUB>3</SUB> is any point that is on the line passing through <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB> and is on or between <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB> on the line. Given two distinct points <I>p</I><SUB>1</SUB> and <I>p</I>2, the <I><B>line segment</I></B> <img src="887_a.gif"> is the set of convex combinations of <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB>. We call <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB> the <I><B>endpoints</I></B> of segment <img src="887_b.gif">. Sometimes the ordering of <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB> matters, and we speak of the <I><B>directed segment</I></B> <img src="887_c.gif">. If p<SUB>1</SUB> is the <I><B>origin</I></B> (0, 0), then we can treat the directed segment <img src="887_d.gif"> as the <I><B>vector</I></B> <I>p</I><SUB>2</SUB>.<P>
In this section, we shall explore the following questions:<P>
<img src="887_e.gif"><P>
There are no restrictions on the given points.<P>
We can answer each question in <I>O</I>(1) time, which should come as no surprise since the input size of each question is <I>O</I>(1). Moreover, our methods will use only additions, subtractions, multiplications, and comparisons. We need neither division nor trigonometric functions, both of which can be computationally expensive and prone to problems with round-off error. For example, the "straightforward" method of determining whether two segments intersect--compute the line equation of the form <I>y = mx + b</I> for each segment <I>(m</I> is the slope and <I>b</I> is the <I>y</I>-intercept), find the point of intersection of the lines, and check whether this point is on both segments<FONT FACE="CG Times (W1)" SIZE=2>--</FONT>uses division to find the point of intersection. When the segments are nearly parallel, this method is very sensitive to the precision of the division operation on real computers. The method in this section, which avoids division, is much more accurate.<P>
<h2>Cross products</h2><P>
<a name="09e2_1c16"><a name="09e2_1c17"><a name="09e2_1c18"><a name="09e2_1c19">Computing cross products is at the heart of our line-segment methods. Consider vectors <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB>, shown in Figure 35.1(a). The <I><B>cross product</I></B> <I>p</I><SUB>1</SUB> <I>x</I> <I>p</I><SUB>2</SUB> can be interpreted as the signed area of the parallelogram formed by the points (0, 0), <I>p</I><SUB>1</SUB>,<I> p</I><SUB>2</SUB>, and <I>p</I><SUB>1</SUB><I> + p</I><SUB>2</SUB><I> = (x</I><SUB>1</SUB><I> + x</I><SUB>2</SUB>,<I> y</I><SUB>1</SUB><I> + y</I><SUB>2<I>)</I></SUB>. An equivalent, but more useful, definition gives the cross product as the determinant of<P>
<img src="888_a.gif"><P>
<h4><a name="09e2_1c1b">Figure 35.1 (a) The cross product of vectors p<SUB>1</SUB> and p<SUB>2</SUB> is the signed area of the parallelogram. (b) The lightly shaded region contains vectors that are clockwise from p. The darkly shaded region contains vectors that are counterclockwise from p.<a name="09e2_1c1b"></sub></sup></h4><P>
a matrix:<SUP>1<P>
<img src="888_b.gif"><P>
<SUP>1</SUP> Actually, the cross product is a three-dimensional concept. It is a vector that is perpendicular to both <I>p</I><SUB>1</SUB> and <I>p</I><SUB>2</SUB> according to the "right-hand rule" and whose magnitude is |<I>x</I><SUB>1</SUB><I>y</I><SUB>2</SUB> - <I>x</I><SUB>2</SUB><I>y</I><SUB>1</SUB>|. In this chapter, however, it will prove convenient to treat the cross product simply as the value <I>x</I><SUB>1</SUB><I>y</I><SUB>2</SUB> - <I>x</I><SUB>2</SUB><I>y</I><SUB>1</SUB>.<P>
<a name="09e2_1c1a">If <I>p</I><SUB>1</SUB><I> </I>X<I> p</I><SUB>2</SUB> is positive, then <I>p</I><SUB>1</SUB> is clockwise from <I>p</I><SUB>2</SUB> with respect to the origin (0, 0); if this cross product is negative, then <I>p</I><SUB>1</SUB> is counterclockwise from <I>p</I><SUB>2</SUB>. Figure 35.1(b) shows the clockwise and counterclockwise regions relative to a vector <I>p</I>. A boundary condition arises if the cross product is zero; in this case, the vectors are <I><B>collinear</I></B>, pointing in either the same or opposite directions.<P>
To determine whether a directed segment <img src="888_c.gif"> is clockwise from a directed segment <img src="888_d.gif"> with respect to their common endpoint <I>p</I><SUB>0</SUB>, we simply translate to use <I>p</I><SUB>0</SUB> as the origin. That is, we let <I>p</I><SUB>1</SUB><I> - p</I><SUB>0</SUB> denote the vector <I>p</I><I>'</I><SUB>1</SUB><I> = (x</I>'<SUB>1</SUB>,<I> y</I>'<SUB>1</SUB><I>),</I> where <I>x</I>'<SUB>1</SUB><I> = x</I><SUB>1</SUB><I> - x</I><SUB>0</SUB> and y'<SUB>1</SUB> = y<SUB>1</SUB> - y<SUB>0</SUB>, and we define <I>p</I><SUB>2</SUB><I> - p</I><SUB>0</SUB> similarly. We then compute the cross product<P>
<pre>(p<SUB>1</SUB> - p<SUB>0</SUB>) x (p<SUB>2</SUB> - p<SUB>0</SUB>) = (x<SUB>1 </SUB>- x<SUB>0</SUB>) (y<SUB>2</SUB> - y<SUB>0</SUB>) - (x<SUB>2</SUB> - x<SUB>0</SUB>) (y<SUB>1</SUB> - y<SUB>0</SUB>).</sub></sup></pre><P>
If this cross product is positive, then <img src="888_e.gif"> is clockwise from <img src="888_f.gif">; if negative, it is counterclockwise.<P>
<P>
<h2>Determining whether consecutive segments turn left or right</h2><P>
<a name="09e3_1c1b">Our next question is whether two consecutive line segments <img src="888_g.gif"> turn left or right at point <I>p</I><SUB>l</SUB>.<I> </I>Equivalently, we want a method to determine which way a given angle <img src="../images/angle.gif"><I>p</I><SUB>0</SUB><I>p</I><SUB>1</SUB><I>p</I><SUB>2</SUB> turns. Cross products allow us to answer this question without computing the angle. As shown in Figure 35.2, we simply check whether directed segment <img src="889_e.gif"> is clockwise or counterclockwise relative to directed segment <img src="889_f.gif">. To do this, we compute the cross product (<I>p</I><SUB>2</SUB><I> - p</I><SUB>0</SUB>)<I> </I>X <I></I>(<I>p</I><SUB>1</SUB><I> - p</I><SUB>0</SUB>). If the sign of this cross product is negative, then <img src="889_g.gif"> is counterclockwise with respect to <img src="889_h.gif">, and thus we make a left turn at <I>P</I><SUB>1</SUB>. A positive cross product indicates a clockwise orientation and a right turn. A cross product of 0 means that points <I>p</I><SUB>0</SUB>,<I> p</I><SUB>1</SUB>, and <I>p</I><SUB>2</SUB><I> </I>are collinear<I>.</I><P>
<img src="889_a.gif"><P>
<h4><a name="09e3_1c1c">Figure 35.2 Using the cross product to determine how consecutive line segments <img src="889_b.gif"> turn at point p<SUB>1</SUB>. We check whether the directed segment <img src="889_c.gif"> is clockwise or counterclockwise relative to the directed segment <img src="889_d.gif">. (a) If counterclockwise, the points make a left turn. (b) If clockwise, they make a right turn.<a name="09e3_1c1c"></sub></sup></h4><P>
<P>
<h2>Determining whether two line segments intersect</h2><P>
<a name="09e4_1c1c"><a name="09e4_1c1d"><a name="09e4_1c1e">We use a two-stage process to determine whether two line segments intersect. The first stage is <I><B>quick rejection</I></B>: the line segments cannot intersect if their bounding boxes do not intersect. The <I><B>bounding box</I></B> of a geometric figure is the smallest rectangle that contains the figure and whose segments are parallel to the <I>x</I>-axis and <I>y</I>-axis. The bounding box of line segment <img src="889_i.gif"> is represented by the rectangle <img src="889_j.gif"> with lower left point <img src="889_k.gif"> and upper right point <img src="889_l.gif">, where <img src="889_m.gif">. Two rectangles, represented by lower left and upper right points <img src="889_m.gif">, intersect if and only if the conjunction<P>
<img src="889_n.gif"><P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -