交点设A为l与P的边界的公共点.pdfVIP

Chapter 3 Polygon 3.1 the concept of polygon Mathematically defined a polygon is a plane figure specified by a set of three or more coordinate positions,called vertices,that are connected in sequence by straight-line segments,called the edges of the polygon. We will use the term “polygon” to refer only to those planar shapes that have a closed-poly line boundary and no edge crossing. 1. Polygon Classifications If all interior angles of a polygon are less than or equal to 180°,the polygon is convex An equivalent definition of an convex polygo is that its interior lies completely on one side of infinite extension line of any one of its edges,Also, if we select any two points in the interior of a convex polygon,the line segmen joining the two points is also in the interior.A Polygon that is not convex is called a concave ol on. 2. Polygon attributes Vertex: P1,P2, ….Pn Edge: PiPi+1 3.2 Filling Polygon 1 Inside-Outside Tests 交点：设A为l与P的边界的公共点，当沿着l在A点附 近l从P的外部（内部）跨入内部（外部），则认为 是一个交点，否则不作为一个交点。 交点个数：射线l跨越多边形P的边界的次数。 射线法: 过该点划射线与多边形的边界的交点如果为偶数， 则该点在多边形外，如果为奇数,则该点在多边形内。 奇点：射线l与多边形P的公共点为P的顶点时该点 为奇点。 奇点处理：与奇点相连的多边形P的边，若在射线l 的同测，该奇点不做为交点，若在射线两侧则该 奇点做为一个交点。 2 the coherence of polygon Polygon: P ＝P1 P2 ……Pn P1 记：Pi ＝（xi ，yi ），yi1 ，yi2 ，……，yin 为yi递增序 列。 1，area coherence ： 在带状区域： yi yi+1。 [xi =x=xi+1, yi =y=yi+1] 内的象素被P的边界分割成 梯形和三角形。 作用：1 ）区域中的梯形或三角形关于P的内外关系 一旦确定，各个梯形或三角形关于P的内外关 系也随之确定。 2 ）区域内关于大量点P的关系的判别转换为 一个点的判别。 2 ，the coherence of scan line 设扫描线y ＝c与多边形P的各边的交点的坐标递 增序列为x1 ，x2 ，……，xl 。 1 ）l为偶数（？） 2 ）交点序列， 3 ）在P 内外线段沿y ＝c的扫描线相间排列。 在P 内的线段的区间：(x1 ，x2), (x3 ，x4) ……, (xl-1 ， xl) 3 edge coherence 设扫描线y ＝c －1与P的各边交点的x 坐标递增序 列为x’1 ，x’2 ，……，x’h ，如果：yij c ，c －1yij+1 则1 ）h ＝l； 2 ）（x’i ，c －1 ），（xi ，c ）位于多边形P的同 一边pkpk ＋1上。 3 ）x’I ＝xi ＋Δxik ，Δxik 为pkpk ＋1