当前位置：文档之家 › On Visibility Problems in the Plane – Solving Minimum Vertex Guard Problems by Successive

On Visibility Problems in the Plane – Solving Minimum Vertex Guard Problems by Successive

  • 格式：pdf
  • 大小：535.19 KB
  • 文档页数：12

On Visibility Problems in the Plane–Solving Minimum Vertex Guard Problems by Successive Approximations Ana Paula Tom´a s1,Ant´o nio Leslie Bajuelos2and F´a bio Marques31DCC-FC&LIACC,University of Porto,Portugalapt@ncc.up.pt2Dept.of Mathematics&CEOC-Center for Research in Optimization and Control,University of Aveiro,Portugalleslie@mat.ua.pt3School of Technology and Management,University of Aveiro,Portugalfabio@estga.ua.ptAbstract.We address the problem of stationing guards in vertices of a simplepolygon in such a way that the whole polygon is guarded and the number ofguards is minimum.It is known that this is an NP-hard Art Gallery Problemwith relevant practical applications.In this paper we present an approximationmethod that solves the problem by successive approximations,which we intro-duced in[21].We report on some results of its experimental evaluation and des-cribe two algorithms for characterizing visibility from a point,that we designedfor its implementation.1IntroductionThe classical Art Gallery problem for a polygon P is tofind a minimum set of points G in P such that every point of P is visible from some point of G.We address M INIMUM V ERTEX G UARD in which the set of guards G is a subset of the vertices of P and each guard has2πrange unlimited visibility.This is an NP-hard combinatorial problem both for arbitrary and orthogonal polygons[13,17].Orthogonal(i.e.rectilinear)polygons are interesting for they may be seen as abstractions of art galleries,for instance.Many variants of art gallery problems have been proposed and studied over the years,with relevant practical applications[15,19,18].An approach that has been ne-glected is that offinding algorithms that obtain approximate solutions[19],although, more recently,the use of some meta-heuristics(simulated annealing and genetic algo-rithms)was investigated by Canales[5].Greedy algorithms for M INIMUM V ERTEX G UARD were proposed by Ghosh[8]and Eidenbenz[7],the latter addressing also ex-tensions to terrains.These approximation algorithms transform M INIMUM V ERTEX G UARD instances into M INIMUM S ET C OVER instances,using decompositions of P. It may be required that each piece of the decomposition is either totally visible or totally invisible from each vertex,which guarantees that the approximation is exact[8].This feature,that we call P IECE R ESTRICTION,may render decompositions too grained.In[21],we proposed an anytime algorithm for solving M INIMUM V ERTEX G UARD by successive approximations.It may start from a partition that does not satisfy P IECE R ESTRICTION.Indeed,its main idea is tofind a sequence of successively shorter inter-vals that enclose the minimum value OP T(P).Tofind a sequence of decreasing upper bounds,we successively refine an initial partition of the polygon.To approximate the optimum from below,we consider an in-creasing powerful subset of dominant pieces that are not visible by sections.A piece R is visible by sections iff no guard sees it completely but guards may collaborate to jointly guard it.When we decompose R,we obtain several smaller pieces that satisfy P IECE R ESTRICTION.Dominance of visibility regions is exploited for reducing the problem dimension,as it is helpful to identify pieces or vertices that are irrelevant.It is also exploited for choosing the pieces that will be decomposed to getfiner partitions.Our algorithm applies both Computational Geometry and Constraint Programming techniques.In this paper we present some results of its experimental evaluation.The samples used consist of orthogonal polygons.For the initial decomposition,we took Πr-cut(the partition of the polygon into rectangles by extension of all edges incident to its reflex vertices),which is constructed by vertical and horizontal sweeping.We describe the algorithms we developed tofind how each rectangular piece ofΠr-cut is seen from each vertex and to compute the partition induced by the visibility regions in each piece.To make the paper self-contained,wefirst introduce some useful concepts and recall our approximation method.2Total Visibility,Visibility by Sections and DominanceGiven two points x and y in a simple polygon P,we say that x sees y(or y is visible to x)iff the closed segmentDefinition 1.Two vertices v i and v j are equivalent if V (v i )=V (v j )and 2-equivalent if G t v j =G t v i .If V (v j )⊂V (v i )then v i strictly dominates v j .If G t v j ⊂G t v i then v iis 2-dominant over v j .Two pieces R i ,R j ∈Πare 2-equivalent if G t R i =G t R j .If G t R i ⊂G t R j then R i 2-dominates R j .If R ∈ΓΠ∞and R ∈Π,then R strictlydominates R when G t R ⊂G t R (implying that R is necessarily guarded whenever R isguarded).If R,R ∈ΓΠ∞and G t R =G t R ,then R and R are equivalent.Example 1.In order to illustrate these notions,we present as small example in Fig.1.11212345678Fig.1.The initial partition Πr-cut and the visibility regions of vertices 1and 12(in CCW order).Pieces 1and 8are in ΓΠ0,as well as 2and 7.G tR 1={v 1,v 2,v 3,v 4}and G s R 1={v 12}.G tR 2={v 1,v 2,v 3,v 4,v 5,v 8,v 9,v 12}and G s R 2={v 7}.Piece 2is redundant since piece 1strictly dominates (and 2-dominates)it.G tR 4={v 5,v 6,v 7,v 8}and G s R 4={v 1,v 12}.Piece 4is visible by sections:the partition induced by its visibility sections (V s R 4(v 1)and V s R 4(v 12))is shown also on the right,the triangle in the center being redundant.3Solving Minimum Vertex Guard by Successive Approximations Our method solves a sequence of M INIMUM V ERTEX G UARD problems,each one with the additional restriction that guards will not cooperatively guard pieces that they do not totally see on their own (i.e.,visibility by sections is disregarded).Such a prob-lem is called M INIMUM V ERTEX G UARD WITH P IECE R ESTRICTION .Given a set of pieces F ,OP T (F )and OP T 2(F )refer to the optimal values of M INIMUM V ERTEX G UARD and of M INIMUM V ERTEX G UARD WITH P IECE R ESTRICTION w.r.t.F ,for guards located in vertices of P .If each piece in Πis totally visible from at least one vertex of P ,which is true for Πr-cut ,then OP T (F )≤OP T 2(F ),for all F ⊆Π.We now present the skeleton of our approximation algorithm.A PPROX M IN V ERTEX G UARD (P )Π:=D ECOMPOSE (P )(each piece must be totally visible from some vertex)Compute G t v ,G s v ,for all vertices vCompute G t R and G s R for all R ∈Π(delay decomposition of pieces by visibility sections)Γ:=ΓΠ0while (OP T 2(Γ)<OP T 2(Π))doΓ,Π:=R EFINE (Π).The algorithm obtains a sequence of non-increasing intervals that enclose OP T(P)and such thatOP T2(Γi)≤OP T2(Γi+1)≤OP T(P)≤OP T2(Πi+1)≤OP T2(Πi), whereΓi is the set of pieces of the current partitionΠi that are known to be not visible by sections,up to iteration i.If for some i,the solverfinds that OP T2(Γi)=OP T2(Πi),the approximation stops,because OP T(P)was achieved.If OP T2(Γi)<OP T2(Πi),the partitionΠi will be refined:a piece will be decom-posed to obtain afiner partitionΠi+1.For that,we consider pieces that are2-dominant in∆i+1with∆i+1=(Πi\Γi)\{R|R is2-dominated by a piece in D(Γi)},where D(Γi)is a maximal set of strictly dominant pieces inΓi.We select a2-dominant piece R∈∆i+1,compute the partition Z R determined by its visibility sections and check whether each piece of Z R is visible from any vertex in G s R.If this is the case,R is visible by sections and,since each piece in Z R satisfies P IECE R ESTRICTION,we defineΠi+1:=(Πi\{R})∪D(Z R)andΓi+1:=Γi∪D(Z R). Otherwise,Πi+1:=Πi andΓi+1:=Γi∪{R}.When∆i+1=∅,the dominant classes inΓi andΠi coincide and OP T2(D(Γi))=OP T(D(Πi))=OP T(P).Finding OP T2(F).The reformulation of M INIMUM V ERTEX G UARD WITH P IECE R ESTRICTION as M INIMUM S ET C OVER allows us to model it as a Constraint Satisfac-tion Optimization Problem(CSOP)and to solve it using Constraint Programming tech-niques[14].If V F is the set of vertices that totally see pieces of F,the decision variables are:X v∈{0,1},for v∈V F(1iff a guard is placed at vertex v)and Y R∈{0,1},for R∈F(1iff piece R is guarded).The constraints are(1)–(3)R∈F Y R=|F|(1)v∈G tR X v≥Y R,for all R∈F(2)R∈G t vY R≥X v|G t v|,for all v∈V F(3)and state that all pieces must be visible,that R is visible only if there exists v∈G t R with X v=1,and that a guard at v sees all pieces in G t v,respectively.The goal is to minimize v∈V F X v,that is tofind OP T2(F),as well as an optimal guard set. Additional constraints may be imposed here to reduce the search space.For orthogonal polygons,Kahn et al.[11]showed that OP T(P)≤ nExample2.For the polygon given in Example1,R7and R2are strictly dominated by R8and R1(so that,they will be discarded)and R5is2-dominated by R4,for instance, meaning that it is irrelevant during the computation of OP T2(Π0).If we apply jointly 2-dominance for pieces and for vertices,we getG t[R8]={v9,v10,v11,v12}G t[R1]={v1,v2,v3,v4}G t[R6,R3]={v1,v4,v5,v8,v9,v12}G t[R4]={v5,v6,v7,v8}where[R6,R3]means that these pieces are2-equivalent.Then,for vertices,we obtainG t[v1,v4]={[R1],[R6,R3]}G t[v5,v8]={[R4],[R3,R6]}G t[v9,v12]={[R8],[R3,R6]}G t[v2,v3]={[R1]},2-dominated by[v1,v4]G t[v6,v7]={[R4]},2-dominated by[v5,v8]G t[v10,v11]={[R8]},2-dominated by[v9,v12].If we remove the2-dominated vertices and apply2-dominance again,we obtain for pieces for verticesG t[R8]={[v9,v12]}G t[v1,v4]={[R1]}G t[R1]={[v1,v4]}G t[v5,v8]={[R4]}G t[R4]={[v5,v8]}G t[v9,v12]={[R8]}G t[R6,R3]={[v1,v4],[v5,v8],[v9,v12]} 2-dominated by,e.g.,[R4]so that,the reduced CSOP model,will just involve six decision variables,namely Y[R8],Y[R1],Y[R4],X[v1,v4],X[v5,v8]and X[v9,v12],yielding OP T2(Π0)=3.When we apply a similar procedure toΓΠ00={[R8],[R1],[R5],[R7],[R2]},wewillfind that the classes of2-dominant pieces and vertices are:G t[R8]={[v9,v12]}G t[R1]={[v1,v4]}G t[v1,v4]={[R1]}G t[v9,v12]={[R8]}This means that the reduced CSOP for OP T2(ΓΠ00)involves four decision variablesonly.We see that OP T2(ΓΠ00)=2.Since2=OP T2(ΓΠ00)≤OP T(P)≤3=OP T2(Π0),the partition must berefined:either R3,R4or R6will be then decomposed and the approximation proceeds. 4Computing VisibilityThere exist linear algorithms that compute the visibility region of a point in a poly-gon[10,12].We are interested infinding the relative location of each piece ofΠr-cut,within each visibility region and these methods do not answer directly this question. So,we designed a new method,adapting work by Aronov et al.[1],whose main idea is the propagation of visibility cones(as shown in Fig.2).Pieces that are adjacent to vFig.2.Finding the visibility region of v by propagation of visibility cones.(that is,that have v as vertex)propagate visibility to their neighbours and successively. The dual graph of the partition(that translates the adjacency relation)will be explored in breadth-first,starting from the pieces that are adjacent to v.When v is a convex vertex there is a single piece,say R0,0,to start the propagation. We mark R0,0as totally visible and put its adjacent pieces in the queue(in Fig.2,R0,0 has a single adjacent,which is enlighted on the left).R0,0determines the search direc-tions:they are defined by the relative position of the vertex of R0,0that is diametrically opposite to v.In Fig.2,these directions are(West,South).Every reflex vertex has three adjacent pieces.The three quadrants they define may be explored at the same time.We just need to mark each adjacent piece as totally visible and insert their adjacent ones in the queue to start the propagation.Only pieces that are partially visible or totally visible may propagate visibility.Not all pieces will be visited, in general,but all that are visible from v will be visited.If R i,j is the head of the queue at a given step,the relative position of its centroid(wrt.v)determines the quadrant R i,j belongs to and the corresponding directions,say(d1,d2),of search.We determine thevisibility section V s Ri,j (v)byfinding the intersection of R i,j with a visibility cone.Thiscone is defined by v and the visible part(i.e.,window)of the edges shared by R i,j and its adjacent pieces in the directions(−d1,−d2),which have been already visited. The propagation method ensures that R i,j was enqueued by some previously visited neighbour(either by R i−1,j or R i,j−1).After characterizing the visible section of R i,j,we mark R i,j as already visited, enqueue each of its adjacent pieces,say R i+1,j and R i,j+1,in the directions(d1,d2), provided they exist,are not already in the queue,and share with R ij an edge that is visible(either totally or partially)from v.We say that an edge is visible if at least two of its interior points are visible from v.The method stops when the queue gets empty.The propagation method may be slightly adapted to deal with other kind of parti-tions,namely the partition determined by extending the horizontal(or vertical)edges only,which has at most r+1pieces(where r is the number of reflex vertices),or trian-gulations.To simplify the analysis of the visibility section,it is important that the pieces are convex.5Finding the Partition Induced by Visibility SectionsWe now describe the algorithm used forfinding the partition Z R induced by the set of visibility sections on R(ie.,by{V s R(v)|v∈G s R}),and to determine the vertices that see each piece of Z R.The example given in Fig.3illustrates its main idea.The depictedFig.3.The construction of Z R.In this case,R is not visible by sections.We show the insertion of the third visibility section(i.e.,fourth segment)in the arrangement step by step and the faces it sequentially splits.The dual graph represented will be used to“propagate”visibility.rays support the oblique edges of three visibility sections,one of them being defined by the two dotted rays.The visible part is to the left of each cutting ray(considering the CCW orientation for the visibility sections).The pieces of Z R are the faces of the arrangement of line segments that define the edges of the visibility sections and of R itself.Each visibility section is a simple convex polygon,always perfectly determined by one or two oriented oblique edges.Indeed, we saw that the section V s R(v)is the intersection of R and a visibility cone,so that it has at most two oblique edges.Since R belongs toΠr-cut,the horizontal and vertical edges of its visibility sections are necessarily contained in its boundary.Thus,these edges are redundant for the arrangement.When the vertices of V s R(v)are labeled in counterclockwise order,V s R(v)is to the left of each of its(oriented)edges,and,thus,it is to the left of its oblique edges.Lemma1states that Z R satisfies P IECE R ESTRICTION, a property that has been proved and used in previous works,namely by Ghosh[8],Bos´e et al.[4]and Guibas et al.[9].Lemma1.Any two points in the interior of each face C of Z R see exactly the same vertices of P.The interior of C is either totally visible or invisible to each vertex of P.This results is helpful forfinding the vertices that see each piece of Z R,since it im-plies that we may decide whether a face C is totally visible from a vertex by checking visibility for a single point w in its interior.As the faces are convex sets[8],we couldchoose the witness point w as1Fig.4.The unique F AT and M IN A REA grid n-ogons for n=4,6,8,12,14(up to symmetry).We think F AT and M IN A REA are representative of extremal behaviour,as the ex-perimental results given in Fig.5show.Fig.5.Execution time for the three classes of samples,showing an exponential increase for F AT.Although each F AT n-ogon requires only two guards for n≥12,the computational cost of the construction and update of Hasse diagrams for the dominance relations be-comes too high in the current implementation.The reduced CSOP models are then solved quite quickly,but we think that the dominance checking module needs some improvement.In contrast,for both M IN A REA and randomly generated samples,the results show almost linear growth in the execution time:the correlation coefficient is0.955and 0.9996,respectively.The value OP T(P)is close to n4.These results are given in Fig.6.In Fig.7we present the average number of iterations that were needed to reach OP T(P),again with almost linear growth,for all samples,with correlation coefficients 0.999,0.943and0.999,respectively.Fig.6.Average number of guards.Fig.7.Average number of iterations.7Conclusions and Future WorkWe addressed the M INIMUM V ERTEX G UARD problem,reviewing an anytime method we proposed in[21],that solves the problem by reduction to a sequence of M INIMUM S ET C OVER problems.This sequence is created by successive refinements of a partition of the given polygon.We reported on results of its experimental evaluation.For that purpose,we focused on the case of rectilinear polygons,and analysed in detail some of the algorithms developed for the implementation of the method.Neverthless,both our approximation method and the algorithms described in the paper for the analysis of visibility extend to generic simple polygons and partitions.The sole requirement is that each piece in the initial partition be convex and totally visible from at least one vertex. It is also possible to apply our approximation method when polygons have holes.Each M INIMUM S ET C OVER problem is solved as a constraint satisfaction opti-mization problem.In order to keep its dimension small,we exploit visibility domi-nance,ordering vertices and pieces accordingly.Experiments have shown that this may become quite a burden when the number of pieces of the initial partition is large,so that we plan to improve this issue in future implementations.No specific heuristics were designed to drive the refinement of the partition.We simply selected any of the dominant(more precisely2-dominant)pieces that is likely visible by sections,starting from the ones that are(partially)visible from less vertices. We think it may be still worthwhile to devise heuristics for choosing a piece among these minimal ones,although the computational results point to a linear increase in the number of iterations(i.e.,decomposition steps)with the number of vertices,for randomly generated polygons.Our current work is also focusing on extensions of our method to solve problems where the visibility range is limited toπorπ/2.References1.Aronov B.,Guibas L.,Teichmann M.,Zang L.:Visibility queries and maintenance in simplepolygons.Discrete and Computational Geometry,27(2002)461–483.2.Bajuelos A.L.,Tomas A.P.,Marques F.:Partitioning orthogonal polygons by extension ofall edges incident to reflex vertices:lower and upper bounds on the number of pieces.Ingan`a et al.(eds):Proc.of ICCSA2004,LNCS3045,Springer Verlag(2004)127–136.3.De Berg M.,Van Kreveld M.,Overmars M.,and Schwarzkopf O.:Computational Geometry(Algorithms and Applications),Springer-Verlag(1997).4.Bose P.,Lubiw A.,and Munro J.I.:Efficient visibility queries in simple polygons.Proc.4thput.Geom.(1992)23–28.5.Canales S.:Metodos Heuristicos en Problemas Geometricos:Visibilidad,Iluminacion y Vigi-lancia.PhD Thesis,Universidad Politecnica de Madrid,Spain(2004).6.Carlsson M.,Ottosson G.,Carlson B.:An Open-Ended Finite Domain Constraint Solver.InProceedings of PLILP’97,LNCS1292.Springer-Verlag,(1997)191–206.7.Eidenbenz S.:Aproximation algorithms for terrain rmation Processing Letters82(2002)99–105.8.Ghosh,S.K.:Approximation algorithms for art gallery problems.Proc.Canadian InformationProcessing Society Congress.(1987)429–434.9.Guibas L.J.,Motwani R.,Raghavan P.:The robot localization problem in two dimen-sions.Proc.3rd ACM–SIAM Symp.Discrete Algorithms(1992)259–268.10.Joe B.,Simpson R.B.:Corrections to Lee’s Visibility Polygon Algorithm.BIT27(1987)458–473.11.Kahn,J.,Klawe,M.,Kleitman,D.:Traditional galleries require fewer watchmen.SIAM J.Algebraic and Discrete Methods4(1983)194–206.12.Lee,D.T.:Visibility of a simple puter Vision,Graphics,and Image Processing22(1983)207–221.13.Lee,D.T.,Lin,A.K.:Computational complexity of art gallery problems.IEEE Transactionon Information Theory IT-32(1986)276–282.14.Marriott K.,Stuckey P.:Programming with Constraints–An Introduction.MIT Press(1998).15.O’Rourke J.:Art Gallery Theorems and Algorithms.Oxford University Press(1987).16.Schrijver A.:Theory of Linear and Integer Programming,Wiley-Interscience(1986).17.Schuchardt D.,Hecker H.:Two NP-hard problems for ortho-polygons.Math.Logiv Quart41(1995)261–267.18.Shermer T.:Recent results in art galleries.Proc.IEEE80:9(1992)1384–1399.19.Urrutia,J.:Art gallery and illumination problems.In J.-R.Sack and J.Urrutia,editors,Hand-book on Computational Geometry.Elsevier(2000).20.Tomas,A.P.,Bajuelos,A.L.:Quadratic-Time Linear-Space Algorithms for Generating Or-thogonal Polygons with a Given Number of Vertices.In gan`a et al.(Eds):Proc.of ICCSA 2004,LNCS3045,Springer-Verlag(2004)117–126.21.Tomas A.P.,Bajuelos A.L.,Marques F.:Approximation algorithms to minimum vertexcover problems on polygons and terrains.In P.M.A Sloot et al.(Eds):Proc.of ICCS2003, LNCS2657,Springer-Verlag(2003)869-878.。

合集下载

unit7

unit7


3. Do not eat or drink when you are near your computer. Pieces of food and a little water in the keyboard can also cause many problems. 4. Make sure that the keyboard and screen are the correct height for you. If they are not correct, you will get backache.
Conversation 5
A: Do you like traveling by train or by plane? B: By train, I think. A: Why? I think a train is much slower than a plane. B: You are right. When I have something urgent to do I usually go by air. It saves a lot of time. But when I’m not in a hurry, I prefer to go by train. A: Don’t you feel bored on a train? B: Not at all. Unlike the plane travel, you have much time to make friends on a train. And you can also enjoy the scenery outside the window. N 5. The man thinks that it is safer to travel by train than by plane.
航空英语口语900句

航空英语口语900句

航空英语口语30句1、Would you like to read these news papers or magazines?您想看这些报纸或杂志吗?2、I'd like to reconfirm my plane reservation please.我想要确认我预定的机位。

4、are you going to study there or just for sight seeing?你是去学习还是只去旅游?5、we can't take off because the airport is closed due to poor visibility.由于低能见度，机场关闭，我们不能起飞。

6、Any check-in bags?你有托运行李吗?7、morning, madam(sir). welcome board!早上好，女士(先生)。

欢迎登机!8、open seat belts. leave everything behind and come this way!解开安全带，别拿行李，朝这边走!9、morning, sir. welcome aboard. business class or economy?早上好，先生。

欢迎登机。

坐公务还是经济舱?10、 fasten your seat belts immediately. the plane will make an emergency landing because of the sudden breakdown of an engine.马上系好安全带。

由于飞机发动机出现故障，将做紧急迫降。

11、would you like anything to drink first?您想先喝点什么?12、the flight has been delayed because of bad weather.由于天气恶劣，航班已经延误。

剑桥雅思阅读解析8（test2）

剑桥雅思阅读解析8（test2）

剑桥雅思阅读解析8(test2)店铺为大家整理收集了剑桥雅思阅读8真题解析：test2阅读原文解析，希望对各位考生的备考有所帮助,祝每位烤鸭考试顺利，都能取得好成绩!剑桥雅思阅读8原文(test2)READING PASSAGE 1You should spend about 20 minutes on Questions 1-13, which are based on Reading Passage 1 below.Sheet glass manufacture:the float processGlass, which has been made since the time of the Mesopotamians and Egyptians, is little more than a mixture of sand, soda ash and lime. When heated to about 1500 degrees Celsius (℃) this becomes a molten mass that hardens when slowly cooled. The first successful method for making clear, flat glass involved spinning. This method was very effective as the glass had not touched any surfaces between being soft and becoming hard, so it stayed perfectly unblemished, with a 'fire finish'. However, the process took a long time and was labour intensive.Nevertheless, demand for flat glass was very high and glassmakers across the world were looking for a method of making it continuously. The first continuous ribbon process involved squeezing molten glass through two hot rollers, similar to an old mangle. This allowed glass of virtually any thickness to be made non-stop, but the rollers would leave both sides of the glass marked, and these would then need to be ground and polished. This part of the process rubbed away around 20 per cent of the glass, and the machines were very expensive.The float process for making flat glass was invented by Alistair Pilkington. This process allows the manufacture of clear, tinted and coated glass for buildings, and clear and tinted glass for vehicles. Pilkington had been experimenting with improving the melting process, and in 1952 he had the idea of using a bed of molten metal to form the flat glass, eliminating altogether the need for rollers within the float bath. The metal had to melt at a temperature less than the hardening point of glass (about 600℃), but could not boil at a temperature below the temperature of the molten glass (about 1500℃). The best meta l for the job was tin.The rest of the concept relied on gravity, which guaranteed that the surface of the molten metal was perfectly flat and horizontal. Consequently, when pouring molten glass onto the molten tin, the underside of the glass would also be perfectly flat. If the glass were kept hot enough, it would flow over the molten tin until the top surface was also flat, horizontal and perfectly parallel to the bottom surface. Once the glass cooled to 604℃ or less it was too hard to mark and could be transported out of the cooling zone by rollers. The glass settled to a thickness of six millimetres because of surface tension interactions between the glass and the tin. By fortunate coincidence, 60 per cent of the flat glass market at that time was for six-millimetre glass.Pilkington built a pilot plant in 1953 and by 1955 he had convinced his company to build a full-scale plant. However, it took 14 months of non-stop production, costing the company ￡100,000 a month, before the plant produced any usable glass. Furthermore, once they succeeded in making marketable flat glass, the machine was turned off for a service to prepare it for years of continuous production. When it started up again it took another four months to get the process right again. They finallysucceeded in 1959 and there are now float plants all over the world, with each able to produce around 1000 tons of glass every day, non-stop for around 15 years.Float plants today make glass of near optical quality. Several processes —melting, refining, homogenising —take place simultaneously in the 2000 tonnes of molten glass in the furnace. They occur in separate zones in a complex glass flow driven by high temperatures. It adds up to a continuous melting process, lasting as long as 50 hours, that delivers glass smoothly and continuously to the float bath, and from there to a coating zone and finally a heat treatment zone, where stresses formed during cooling are relieved.The principle of float glass is unchanged since the 1950s. However, the product has changed dramatically, from a single thickness of 6.8 mm to a range from sub-millimetre to 25 mm, from a ribbon frequently marred by inclusions and bubbles to almost optical perfection. To ensure the highest quality, inspection takes place at every stage. Occasionally, a bubble is not removed during refining, a sand grain refuses to melt, a tremor in the tin puts ripples into the glass ribbon. Automated on-line inspection does two things. Firstly, it reveals process faults upstream that can be corrected. Inspection technology allows more than 100 million measurements a second to be made across the ribbon, locating flaws the unaided eye would be unable to see. Secondly, it enables computers downstream to steer cutters around flaws.Float glass is sold by the square metre, and at the final stage computers translate customer requirements into patterns of cuts designed to minimise waste.Questions 1-8Complete the table and diagram below.Choose NO MORE THAN TWO WORDS from the passage for each answer.Write your answers in boxes 1-8 on your answer sheet.Early methods of producing flat glassMethod Advantages Disadvantages1............Glass remained2........... ? Slow3.............RibbonCould produce glass sheets of varying 4.............non-stop process ? Glass was 5...........20% of glass rubbed awayMachines were expensive图片11Questions 9-13Do the following statements agree with the information given in Reading Passage 1?In boxes 9-13 on your answer sheet, writeTRUE if the statement agrees with the informationFALSE if the statement contradicts the informationNOT GIVEN if there is no information on this9 The metal used in the float process had to have specific properties.10 Pilkington invested some of his own money in his float plant.11 Pilkington’s first full-scale plant was an instant commercial success.12 The process invented by Pilkington has now beenimproved.13 Computers are better than humans at detecting faults in glass.READING PASSAGE 2You should spend about 20 minutes on Questions 14-26, which are based on Reading Passage 2 on the following pages.Question 14-17Reading passage 2 has six paragraphs, A-F.Choose the correct heading for paragraphs B and D-F from the list of headings below.Write the correct number, i-ix, in boxes 14-17 on your answer sheet.List of Headingsi Predicting climatic changesii The relevance of the Little Ice Age todayiii How cities contribute to climate change.iv Human impact on the climatev How past climatic conditions can be determinedvi A growing need for weather recordsvii A study covering a thousand yearsviii People have always responded to climate changeix Enough food at lastExample AnswerParagraph A Viii14 Paragraph BExample AnswerParagraph C V15 Paragraph D16 Paragraph E17 Paragraph FTHE LITTLE ICE AGEA This book will provide a detailed examination of the Little Ice Age and other climatic shifts, but, before I embark on that, let me provide a historical context. We tend to think of climate — as opposed to weather — as something unchanging, yet humanity has been at the mercy of climate change for its entire existence, with at least eight glacial episodes in the past 730,000 years. Our ancestors adapted to the universal but irregular global warming since the end of the last great Ice Age, around 10,000 years ago, with dazzling opportunism. They developed strategies for surviving harsh drought cycles, decades of heavy rainfall or unaccustomed cold; adopted agriculture and stock-raising, which revolutionised human life; and founded the world's first pre-industrial civilisations in Egypt, Mesopotamia and the Americas. But the price of sudden climate change, in famine, disease and suffering, was often high.B The Little Ice Age lasted from roughly 1300 until the middle of the nineteenth century. Only two centuries ago, Europe experienced a cycle of bitterly cold winters; mountain glaciers in the Swiss Alps were the lowest in recorded memory, and pack ice surrounded Iceland for much of the year. The climatic events of the Little Ice Age did more than help shape the modern world. They are the deeply important context for the current unprecedented global warming. The Little Ice Age was far from a deep freeze, however; rather an irregular seesaw of rapid climatic shifts, few lasting more than a quarter-century, driven by complex and still little understood interactions between the atmosphere and the ocean. The seesaw brought cycles of intensely cold winters and easterly winds, then switched abruptly to years of heavy spring and early summer rains, mild winters,and frequent Atlantic storms, or to periods of droughts, light northeasterly winds, and summer heat waves.C Reconstructing the climate changes of the past is extremely difficult, because systematic weather observations began only a few centuries ago, in Europe and North America. Records from India and tropical Africa are even more recent. For the time before records began, we have only 'proxy records' reconstructed largely from tree rings and ice cores, supplemented by a few incomplete written accounts. We now have hundreds of tree-ring records from throughout the northern hemisphere, and many from south of the equator, too, amplified with a growing body of temperature data from ice cores drilled in Antarctica, Greenland, the Peruvian Andes, and other locations, we are close to a knowledge of annual summer and winter temperature variations over much of the northern hemisphere going back 600 years.D This book is a narrative history of climatic shifts during the past ten centuries, and some of the ways in which people in Europe adapted to them. Part One describes the Medieval Warm Period, roughly 900 to 1200. During these three centuries, Norse voyagers from Northern Europe explored northern seas, settled Greenland, and visited North America. It was not a time of uniform warmth, for then, as always since the Great Ice Age, there were constant shifts in rainfall and temperature. Mean European temperatures were about the same as today, perhaps slightly cooler.E It is known that the Little Ice Age cooling began in Greenland and the Arctic in about 1200. As the Arctic ice pack spread southward, Norse voyages to the west were rerouted into the open Atlantic, then ended altogether. Storminess increased in the North Atlantic and North Sea. Colder, much wetter weatherdescended on Europe between 1315 and 1319, when thousands perished in a continent-wide famine. By 1400, the weather had become decidedly more unpredictable and stormier, with sudden shifts and lower temperatures that culminated in the cold decades of the late sixteenth century. Fish were a vital commodity in growing towns and cities, where food supplies were a constant concern. Dried cod and herring were already the staples of the European fish trade, but changes in water temperatures forced fishing fleets to work further offshore. The Basques, Dutch, and English developed the first offshore fishing boats adapted to a colder and stormier Atlantic. A gradual agricultural revolution in northern Europe stemmed from concerns over food supplies at a time of rising populations. The revolution involved intensive commercial farming and the growing of animal fodder on land not previously used for crops. The increased productivity from farmland made some countries self-sufficient in grain and livestock and offered effective protection against famine.F Global temperatures began to rise slowly after 1850, with the beginning of the Modern Warm Period. There was a vast migration from Europe by land-hungry farmers and others, to which the famine caused by the Irish potato blight contributed, to North America, Australia, New Zealand, and southern Africa. Millions of hectares of forest and woodland fell before the newcomers' axes between 1850 and 1890, as intensive European farming methods expanded across the world. The unprecedented land clearance released vast quantities of carbon dioxide into the atmosphere, triggering for the first time humanly caused global warming. Temperatures climbed more rapidly in the twentieth century as the use of fossil fuels proliferated and greenhouse gas levels continued to soar. The rise has been even steeper since theearly 1980s. The Little Ice Age has given way to a new climatic regime, marked by prolonged and steady warming. At the same time, extreme weather events like Category 5 hurricanes are becoming more frequent.Questions 18-22Complete the summary using the list of words, A-I, below.Write the correct letter, A-I, in boxes 18-22 on your answer sheet.Weather during the Little Ice AgeDocumentation of past weather conditions is limited: our main sources of knowledge of conditions in the distant past are 18...........and 19.................. We can deduce that the Little Ice Age was a time of 20.............. , rather than of consistent freezing. Within it there were some periods of very cold winters, other of 21...............and heavy rain, and yet others that saw 22................with no rain at all.A climatic shiftsB ice coresC tree ringsD glaciersE interactionsF weather observationsG heat waves H storms I written accountsQuestions 23-26Classify the following events as occurring during theA Medieval Warm PeriodB Little Ice AgeC Modern Warm PeriodWrite the correct letter, A, B or C, in boxes 23-26 on your answer sheet.23 Many Europeans started farming abroad.24 The cutting down of trees began to affect the climate.25 Europeans discovered other lands.26 Changes took place in fishing patterns.READING PASSAGE 3You should spend about 20 minutes on Questions 27-40, which are based on Reading Passage 3 on the following pages.Questions 27-32Reading Passage 3 has six paragraphs, A-F.Choose the correct heading for each paragraph from the list of headings below.Write the correct number, i-viii, in boxes 27-32 on your answer sheet.List of Headingsi The difficulties of talking about smellsii The role of smell in personal relationshipsiii Future studies into smelliv The relationship between the brain and the nosev The interpretation of smells as a factor in defining groups vi Why our sense of smell is not appreciatedvii Smell is our superior senseviii The relationship between smell and feelings27 paragraph A28 paragraph B29 paragraph C30 paragraph D31 paragraph E32 paragraph FThe meaning and power of smellThe sense of smell, or olfaction, is powerful. Odours affect us on a physical, psychological and social level. For the most part, however, we breathe in the aromas which surround us without being consciously aware of their importance to us. It is only when the faculty of smell is impaired for some reason that we begin torealise the essential role the sense of smell plays in our sense of well-beingA A survey conducted by Anthony Synott at Montreal's Concordia University asked participants to comment on how important smell was to them in their lives. It became apparent that smell can evoke strong emotional responses. A scent associated with a good experience can bring a rush of joy, while a foul odour or one associated with a bad memory may make us grimace with disgust. Respondents to the survey noted that many of their olfactory likes and dislikes were based on emotional associations. Such associations can be powerful enough so that odours that we would generally label unpleasant become agreeable, and those that we would generally consider fragrant become disagreeable for particular individuals. The perception of smell, therefore, consists not only of the sensation of the odours themselves, but of the experiences and emotions associated with them.B Odours are also essential cues in social bonding. One respondent to the survey believed that there is no true emotional bonding without touching and smelling a loved one. In fact, infants recognise the odours of their mothers soon after birth and adults can often identify their children or spouses by scent. In one well-known test, women and men were able to distinguish by smell alone clothing worn by their marriage partners from similar clothing worn by other people. Most of the subjects would probably never have given much thought to odour as a cue for identifying family members before being involved in the test, but as the experiment revealed, even when not consciously considered, smells register.C In spite of its importance to our emotional and sensorylives, smell is probably the most undervalued sense in many cultures. The reason often given for the low regard in which smell is held is that, in comparison with its importance among animals, the human sense of smell is feeble and undeveloped. While it is true that the olfactory powers of humans are nothing like as fine as those possessed by certain animals, they are still remarkably acute. Our noses are able to recognise thousands of smells, and to perceive odours which are present only in extremely small quantities.D Smell, however, is a highly elusive phenomenon. Odours, unlike colours, for instance, cannot be named in many languages because the specific vocabulary simply doesn't exist. ‘It smells like…,’ we have to say when describing an odour, struggling to express our olfactory experience. Nor can odours be recorded: there is no effective way to either capture or store them over time. In the realm of olfaction, we must make do with descriptions and recollections. This has implications for olfactory research.E Most of the research on smell undertaken to date has been of a physical scientific nature. Significant advances have been made in the understanding of the biological and chemical nature of olfaction, but many fundamental questions have yet to be answered. Researchers have still to decide whether smell is one sense or two — one responding to odours proper and the other registering odourless chemicals in the air. Other unanswered questions are whether the nose is the only part of the body affected by odours, and how smells can be measured objectively given the non-physical components. Questions like these mean that interest in the psychology of smell is inevitably set to play an increasingly important role for researchers.F However, smell is not simply a biological and psychologicalphenomenon. Smell is cultural, hence it is a social and historical phenomenon. Odours are invested with cultural values: smells that are considered to be offensive in some cultures may be perfectly acceptable in others. Therefore, our sense of smell is a means of, and model for, interacting with the world. Different smells can provide us with intimate and emotionally charged experiences and the value that we attach to these experiences is interiorised by the members of society in a deeply personal way. Importantly, our commonly held feelings about smells can help distinguish us from other cultures. The study of the cultural history of smell is, therefore, in a very real sense, an investigation into the essence of human culture.Questions 33-36Choose the correct letter, A, B, C or D.Write the correct letter in boxes 33-36 on your answer sheet.33 According to the introduction, we become aware of the importance of smell whenA we discover a new smell.B we experience a powerful smell.C our ability to smell is damaged.D we are surrounded by odours.34 The experiment described in paragraph BA shows how we make use of smell without realising it.B demonstrates that family members have a similar smell.C proves that a sense of smell is learnt.D compares the sense of smell in males and females.35 What is the write doing in paragraph C?A supporting other researchB making a proposalC rejecting a common beliefD describing limitations36 What does the write suggest about the study of smell in the atmosphere in paragraph E?A The measurement of smell is becoming more accurate.B Researchers believe smell is a purely physical reaction.C Most smells are inoffensive.D Smell is yet to be defined.Questions 37-40Complete the sentences below.Choose ONE WORD ONLY from the passage for each answer.Write your answers in boxes 37-40 on your answer sheet.37 Tests have shown that odours can help people recognise the.......... belonging to their husbands and wives.38 Certain linguistic groups may have difficulty describing smell because they lack the appropriate ................ .39 The sense of smell may involve response to................ which do not smell, in addition to obvious odours.40 Odours regarded as unpleasant in certain.................are not regarded as unpleasant in others.剑桥雅思阅读8原文参考译文(test2)PASSAGE 1 参考译文：玻璃板制造：浮法工艺早在美索不达米亚时期和古埃及时期人们就开始制造玻璃，当时制作出的玻璃只不过是沙子、碳酸钠和石灰的混合物而已。

民航英语100句

民航英语100句

1．Good morning. Welcome aboard!早上好，欢迎登机！2．Excuse me. May I see your boarding pass?对不起，能看一下您的登机牌吗？3．What's your seat number?您的座位号是多少？4．I'm afraid you are in the wrong seat.恐怕您坐错了座位。

5．May I help you with your bag?我能帮您提行李吗？6．Please carry your bag and follow me.请提着行李跟我来。

7．I'm afraid you'll have to stow your bag under the seat in front of you.恐怕您要将行李放您前排的座椅下面。

8．You may adjust your seat back by pressing the button on the arm of your seat.您可以通过座椅扶手的按钮来调节座椅靠背。

9．If there's anything we can do for you, just press the call button.如有任何需要，请按呼唤铃。

10．Your hot towel/wet towel, madam/sir.请您用热毛巾/湿纸巾，女士/先生。

11．There are toilets in the front and rear of the cabin.客舱的前面和后面都有洗手间。

12．Lavatory is not allowed to use during take－off.飞机起飞期间，洗手间禁止使用。

13．We have People's Daily, China Daily, CAAC inflight magazines, Phoenix weekly, Commercial Travel and other local papers for you to read. Which would you like?我们有《人民日报》、《中国日报》、《中国民航杂志》、《凤凰周刊》、《商旅报》和其他一些地方报纸。