网络营销导向的企业网站建设的要求,惠州网站建设报价,wordpress feed插件,视频医疗平台网站开发如何在指定的输出设备上根据坐标描述构造基本二维几何图形#xff08;点、直线、圆、椭圆、多边形域、字符串及其相关属性等#xff09;。 图形生成的概念 图形的生成#xff1a;是在指定的输出设备上#xff0c;根据坐标描述构造二维几何图形。 图形的扫描转换#xff1a…如何在指定的输出设备上根据坐标描述构造基本二维几何图形点、直线、圆、椭圆、多边形域、字符串及其相关属性等。 图形生成的概念 图形的生成是在指定的输出设备上根据坐标描述构造二维几何图形。 图形的扫描转换在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。 直线段的扫描转换 直线的绘制要求 1直线要直 2直线的端点要准确无定向性无断裂 3直线的亮度、色泽要均匀 4画线的速度要快 5具有不同的色泽、亮度、线型等。 解决的问题给定直线两端点P0(x0,y0)和P1(x1,y1)画出该直线。 逐点比较法 数值微分法(DDA法): 增量算法 直观、易实现 不利于用硬件实现 x(i1) x(i) 1 y(i1) y(i) k 中点Bresenhan算法: 算法原理根据直线的斜率确定或选择变量在x或y方向上每次递增一个单位而另一方向的增量为1或0它取决于实际直线与相邻象素点的距离这一距离称为误差项。 中点Bresenham算法——算法步骤 输入直线的两端点P0(x0,y0)和P1(x1,y1)。 计算初始值△x、△y、D△x-2△y、xx0、yy0。 绘制点(x,y)。判断D的符号。若D0则(x,y)更新为(x1,y1)D更新为D2△x-2△y否则(x,y)更新为(x1,y), D更新为D-2△y。 当直线没有画完时重复上一步骤否则结束。 改进的Bresenhan算法——算法步骤 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值△x、△y、e-△x、xx0、yy0。 3.绘制点(x,y)。 4.e更新为e2△y判断e的符号。若e0则(x,y)更新为(x1,y1)同时将e更新为e-2△x否则(x,y)更新为(x1,y)。 5.当直线没有画完时重复步骤3和4。否则结束。 圆的扫描转换 解决的问题绘出圆心在原点半径为整数R的圆x2y2R2。 简单方程产生圆弧: 算法原理利用其函数方程直接离散计算。 中点Bresenham画圆——算法步骤 1.输入圆的半径R。 2.计算初始值d1-R、x0、yR。 3.绘制点(x,y)及其在八分圆中的另外七个对称点。 4.判断d的符号。若d0则先将d更新为d2x3再将(x,y)更新为(x1,y)否则先将d更新为d2(x-y)5再将(x,y)更新为(x1,y-1)。 5.当xy时重复步骤3和4。否则结束。 多边形的扫描转换与区域填充: 多边形的扫描转换主要是通过确定穿越区域的扫描线的覆盖区间来填充。 区域填充是从给定的位置开始涂描直到指定的边界条件为止。 多边形的扫描转换: 顶点表示用多边形的顶点序列来刻划多边形。 点阵表示是用位于多边形内的象素的集合来刻划多边形。 扫描转换多边形从多边形的顶点信息出发求出位于其内部的各个象素并将其颜色值写入帧缓存中相应单元的过程。 X扫描线算法——原理 基本思想按扫描线顺序计算扫描线与多边形的相交区间再用要求的颜色显示这些区间的所有象素。 X扫描线算法——算法步骤 1.确定多边形所占有的最大扫描线数得到多边形顶点的最小和最大y值ymin和ymax。 2.从yymin到yymax每次用一条扫描线进行填充。 3.对一条扫描线填充的过程可分为四个步骤 求交排序交点配对区间填色。 X扫描线算法——取整规则 交点的取整规则使生成的像素全部位于多边形之内。用于直线等图元扫描转换的四舍五入原则可能导致部分像素位于多边形之外从而不可用。 假定非水平边与扫描线ye相交交点的横坐标为x规则如下 规则1X为小数即交点落于扫描线上两个相邻像素之间时 交点位于左边界之上向右取整 交点位于右边界之上向左取整 规则2边界上象素的取舍问题避免填充扩大化。规定落在右边边界上的像素不予填充。具体实现时只要对扫描线与多边形的相交区间左闭右开 规则3当扫描线与多边形顶点相交时交点的取舍保证交点正确配对。 解决方法 当扫描线与多边形的顶点相交时 若共享顶点的两条边分别落在扫描线的两边交点只算一个 若共享顶点的两条边在扫描线的同一边这时交点作为零个或两个。 实际处理只要检查顶点的两条边的另外两个端点的Y值两个Y值中大于交点Y值的个数是012来决定取012个交点。 改进的有效边表算法: 改进原理 处理一条扫描线时仅对有效边求交。 利用扫描线的连贯性。 利用多边形边的连贯性。 改进的有效边表算法Y连贯性算法 有效边Active Edge指与当前扫描线相交的多边形的边也称为活性边。 有效边表Active Edge Table, AET把有效边按与扫描线交点x坐标递增的顺序存放在一个链表中此链表称为有效边表。 有效边表的每个结点 x ymax 1/k next 改进的有效边表算法——构造边表 首先构造一个纵向链表链表的长度为多边形所占有的最大扫描线数链表的每个结点称为一个桶则对应多边形覆盖的每一条扫描线 。 将每条边的信息链入与该边最小y坐标ymin 相对应的桶处。也就是说若某边的较低端点为ymin则该边就放在相应的扫描线桶中。 每条边的数据形成一个结点内容包括该扫描线与该边的初始交点x即较低端点的x值1/k以及该边的最大y值ymax。 x|ymin ymax 1/k NEXT 同一桶中若干条边按X|ymin由小到大排序若X|ymax 相等则按照1/k由小到大排序。 改进的有效边表算法——算法步骤 (1)初始化构造边表AET表置空 (2)将第一个不空的ET表中的边与AET表合并 (3)由AET表中取出交点对进行填充。填充之后删除yymax的边 (4)yi1yi1,根据xi1xi1/k计算并修改AET表同时合并ET表中yyi1桶中的边按次序插入到AET表中形成新的AET表 (5)AET表不为空则转(3)否则结束。 边缘填充算法: 基本思想按任意顺序处理多边形的每条边。处理时先求出该边与扫描线的交点再对扫描线上交点右方的所有象素取反。 算法简单但对于复杂图型每一象素可能被访问多次 栅栏填充算法: 栅栏指的是一条过多边形顶点且与扫描线垂直的直线。它把多边形分为两半。 基本思想按任意顺序处理多边形的每一条边但处理每条边与扫描线的交点时将交点与栅栏之间的象素取反。 这种算法尽管减少了被重复访问象素的数目但仍有一些象素被重复访问。 边标志算法: 基本思想先用特殊的颜色在帧缓存中将多边形的边界勾画出来然后将着色的象素点依x坐标递增的顺序配对再把每一对象素构成的区间置为填充色。 分为两个步骤打标记填充。 当用软件实现本算法时速度与改进的有效边表算法相当但本算法用硬件实现后速度会有很大提高。 区域填充 基本概念: 区域填充是指从区域内的某一个象素点种子点开始由内向外将填充色扩展到整个区域内的过程。 区域是指已经表示成点阵形式的填充图形它是相互连通的一组像素的集合。 区域的表示方法: 边界表示法把位于给定区域的边界上的象素一一列举出来的方法。 边界表示法中由于边界由特殊颜色指定填充算法可以逐个象素地向外处理直到遇到边界颜色为止这种方法称为边界填充算法Boundary-fill Algorithm。 内点表示法枚举出给定区域内所有象素的表示方法。以内点表示法为基础的区域填充算法称为泛填充算法Flood-fill Algorithm。 区域的分类: 4-连通区域从区域上的一点出发通过访问已知点的4-邻接点在不越出区域的前提下遍历区域内的所有象素点。 8-连通区域从区域上的一点出发通过访问已知点的8-邻接点在不越出区域的前提下遍历区域内的所有象素点。 4连通与8连通区域的区别: 连通性 4连通可看作8连通区域但对边界有要求。 对边界的要求。 区域填充算法: 区域填充算法边界填充算法和泛填充算法是根据区域内的一个已知象素点种子点出发找到区域内其他象素点的过程所以把这一类算法也成为种子填充算法。 算法的输入种子点坐标(x,y)填充色以及边界颜色。 利用堆栈实现简单的种子填充算法 算法从种子点开始检测相邻位置是否是边界颜色若不是就用填充色着色并检测该像素点的相邻位置直到检测完区域边界颜色范围内的所有像素为止。 栈结构实现4-连通边界填充算法的算法步骤为 种子象素入栈当栈非空时重复执行如下三步操作 (a)栈顶象素出栈 (b)将出栈象素置成填充色 (c)检查出栈象素的4-邻接点若其中某个象素点不是边界色且未置成多边形色则把该象素入栈。 栈结构实现8-连通边界填充算法的算法步骤为 种子象素入栈当栈非空时重复执行如下三步操作 (a)栈顶象素出栈 (b)将出栈象素置成填充色 (c)检查出栈象素的8-邻接点若其中某个像素点不是边界色且未置成多边形色则把该像素入栈。可以用于填充带有内孔的平面区域。 把太多的像素压入堆栈降低了效率同时需要较大的存储空间。 递归执行算法简单但效率不高区域内每一像素都引起一次递归进/出栈费时费内存。 通过沿扫描线填充水平象素段来代替处理4-邻接点和8-邻接点。 扫描线种子填充算法扫描线通过在任意不间断扫描线区间中只取一个种子像素的方法使堆栈的尺寸极小化。不间断区间是指在一条扫描线上的一组相邻像素。 基本过程当给定种子点时首先填充种子点所在的扫描线上的位于给定区域的一个区段然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段并依次保存下来。反复这个过程直到填充结束。 区域填充算法——泛填充算法 算法的输入种子点坐标(x,y)填充色和内部点的颜色。 算法原理算法从指定的种子(x,y)开始用所希望的填充颜色赋给所有当前为给定内部颜色的象素点。种子象素入栈栈非空时重复执行如下三步操作 (1)栈顶象素出栈 (2)将出栈象素置成填充色 (3)检查出栈象素的8-邻接点若其中某个象素点不是给定内部点的颜色且未置成新的填充色则把该象素入栈。 当以边界表示时4-连通边界填充算法只能填充4-连通区域8-连通边界填充算法也只能填充8-连通区域。 当以内点表示时8-连通泛填充算法可以填充8-连通区域也可以填充4-连通区域当然4-连通泛填充算法还是只能填充4-连通区域。
