字符、裁剪算法

2014地理空间图形学地理信息工程教研室信息工程大学地理空间信息学院学习内容字符及汉字生成二维图形裁剪信息工程大学地理空间信息学院学习要点1、了解字符和汉字编码；2、理解字符及汉字的生成原理，掌握点阵汉字及矢量汉字的文件结构和显示过程；3、掌握点、直线段在区域内、外的判别方法；4、掌握直线段裁剪的几种常用方法；5、了解多边形的逐边裁剪法以及其他图形的裁剪方法。信息工程大学地理空间信息学院一、字符及汉字生成信息工程大学地理空间信息学院 字符是指数字、字母、汉字等，用于图形标注、说明等字符及汉字编码

点阵字符、汉字

矢量字符、汉字

轮廓字型技术

信息工程大学地理空间信息学院ASCII码：

“美国信息交换用标准代码集”

1、字符及汉字编码规定了128个字符代码。代码0—31：控制字符代码32—127：表示英文字母、标点符号、各种运算符以及特殊符号。每个ASCII码用一个字节(实际上只要七位二进制)代码表示。

信息工程大学地理空间信息学院

GB2312—80：我国最常用的字符集是“信息交换用汉字编码字符集基本集”。该字符集包含了六千多个常用汉字，以及英文字母、数字和其它图形符号。编码原则：汉字用两个字节表示，每个字节用七位码（高位为0），前字节的编码称为区码，后字节的编码称为位码，此即区位码，如“保”字在二维代码表中处于17区第3位，区位码即为“1703”。信息工程大学地理空间信息学院

国标码：并不等于区位码，它是由区位码稍作转换得到,其转换方法为：先将十进制区码和位码转换为十六进制的区码和位码，这样就得了一个与国标码有一个相对位置差的代码，再将这个代码的第一个字节和第二个字节分别加上20H，就得到国标码。如：“保”字的国标码为3123Ｈ，它是经过下面的转换得到的：1703D－>1103H->+20H－>3123H。信息工程大学地理空间信息学院

国标码问题？：

国标码是汉字信息交换的标准编码，但因其前后字节的最高位为0，与ASCII码发生冲突？如“保”字，国标码为31H和23H，而西文字符“1”和“#”的SCII也为31H和23H，现假如内存中有两个字节为31H和23H，这到底是一个汉字，还是两个西文字符“1”;和“#”?于是就出现了二义性。显然，国标码是不可能在计算机内部直接采用。信息工程大学地理空间信息学院

机内码：计算机内部表示码，采用变形国标码。变换方法：将国标码的每个字节都加上128，即将两个字节的最高位由0改1，其余7位不变如：由上面我们知道，“保”字的国标码为3123H，前字节为00110001B，后字节为00100011B，高位改1为10110001B和10100011B即为B1A3H，因此，“保”字的机内码就是B1A3H。

机内码高位=区码+

A0H（10100000D） 机内码低位=位码+

A0H信息工程大学地理空间信息学院

输入码:就是使用英文键盘输入汉字时的编码。目前，我国已推出的输入码有数百种，但用户使用较多的约为十几种，按输入码编码的主要依据，大体可分为顺序码、音码、形码、音形码四类。如“保”字，用全拼，输入码为码为“BAO”，用区位码，输入码为“1703”，用五笔字型则为“WKS”。

信息工程大学地理空间信息学院

汉字在计算机中如何表示？

字库：把所有汉字的字模组织起来，并统一组织存储在一起形成的文件叫字库。2、点阵字符、汉字采用图形（对应）的方法，显示(或绘制)一个汉字就是显示一个图形符号，这个图形符号称为汉字字模。每个汉字在计算机中都对应一个字模，字模分为两种类型。一是点阵字模，一种是矢量字模。

信息工程大学地理空间信息学院FE3F008220FA2F0220A2208220FA2F82202F9220B220FE3F0220FA022000

16×16点阵字形实例(国)，整个汉字占32个字节，整个字库的大小为32*6763=210K。点阵汉字是汉字字形最基本的表示法。

点阵汉字原理：信息工程大学地理空间信息学院

点阵汉字缺点：数据量大，放大后会出现明显的锯齿边，这严重地影响了大字的输出质量信息工程大学地理空间信息学院

点阵汉字显示：例如16*16点阵汉字的每一横行占2个字节(2*8位/字节=16位)。也就是说16*16大方格的横行的黑白点是由这两个字节来决定的。将其数字转化为二进制，0的地方不填充，1的地方填充为黑色信息工程大学地理空间信息学院

矢量汉字原理：3、矢量字符、汉字特点：与点阵字相比较，矢量字体的最大优点是数据压缩量大；可以任意缩放。

是把汉字所在的方形区域画成一个N*N的坐标图，然后把汉字的每一个笔划分解成线、圆弧，记录其坐标位置，并将其坐标位置和图形都存储起来，这样形成的汉字字模称之为矢量字模——矢量汉字。信息工程大学地理空间信息学院(63,63)P4P0P1P2P3P5字符的编码X0Y00P0X1Y11P1X2Y20P2X3Y31P3X4Y40P4X5Y51P5-1不连线

连线

字符结束

字符矢量表示，记录字符的笔画信息信息工程大学地理空间信息学院

矢量汉字显示步骤：

1、根据给定的字符编码，在字库中检索出表示该字符的数据。

2、取出端点的坐标，对其适当的几何变形，再根据各端点的标志显示字符。信息工程大学地理空间信息学院

轮廓字：字符的外轮廓由一系列直线段来描述，矢量字体中保存的是该字符外轮廓一系列直线坐标。（一次直线方程）4、轮廓字型技术信息工程大学地理空间信息学院大字仍有“刀割”现象信息工程大学地理空间信息学院

曲线字：以高次曲线代替矢量字轮廓的一次直线的方程，即为曲线字。信息工程大学地理空间信息学院 曲线字库在放大后仍能保证光滑。信息工程大学地理空间信息学院两种曲线字：PostScript字体

（Adobe

公司）：

AdobeType1、AdobeType3

三次Bezier曲线来描述的(精度高)TrueType字体

（Apple和Microsoft公司联手推出的） 二次B样条曲线来描述的(内置系统)信息工程大学地理空间信息学院字符的属性包括字体、字形、大小、字符间距、字符倾斜角、字符串路径、字符串对齐方式等。信息工程大学地理空间信息学院二、二维图形裁剪信息工程大学地理空间信息学院1、线段的裁剪

2、多边形的裁剪

3、其它图形的裁剪

编码裁剪法、矢量裁剪法、中点分割裁剪法

逐边裁剪法 曲线的裁剪、字符的裁剪信息工程大学地理空间信息学院为什么裁剪？

例子：计算机内可以存储全国地图。如果全部显示在屏幕上，则看不见局部细节。这时，可以使用缩放技术，把地图中的局部区域放大显示，这时需要确定地图中那一部分落在显示区域之外，那些部分落在显示区域之内，以便显示落在显示区域之内的那部分图形。——

裁剪信息工程大学地理空间信息学院信息工程大学地理空间信息学院裁剪定义

——确定图形对象的哪些部分在指定区域内部，哪些部分在指定区域外部的过程。裁剪有关概念图形裁剪算法，直接影响图形系统的效率。信息工程大学地理空间信息学院

裁剪实质

——

数据集合中抽取信息的过程，是许多图形操作的基础。

裁剪方法

——判断图形元素是否落在裁剪窗口之内并找出其位于内部的部分。裁剪有关概念信息工程大学地理空间信息学院

裁剪窗口

——多边形区域、曲线边界的区域、矩形窗口。其中最简单最常用的裁剪窗口是矩形窗口。裁剪有关概念由上、下、左、右四条边界围成，通常通过其左下角坐标（XL，YB）和右上角坐标（XR，YT）来定义。(Xr,Yt)(Xl,Yb)信息工程大学地理空间信息学院裁剪分类点的裁剪；线段裁剪；圆的裁剪；多边形的裁剪；字符裁剪等裁剪有关概念信息工程大学地理空间信息学院

点的裁剪是最简单的一种，是裁剪其他元素的基础。判断点的可见性可用下式，若P（x，y）1、点的裁剪P(x,y)XlXrYtYb满足：Xl<=x<=Xr Yb<=y<=Yt点P为可见（在窗口内）否则不可见。

别的图形裁剪是否可以利用这种方法？信息工程大学地理空间信息学院2、线段的裁剪

直线段是组成一切其它图形的基础，直线段裁剪算法是复杂图形裁剪的基础。

编码裁剪法 矢量裁剪法

中点分割裁剪法信息工程大学地理空间信息学院下图表示直线段与窗口的位置关系

每条线段无非三种可能性：

完全不可见（那些？）完全可见（？）部分可见（？）信息工程大学地理空间信息学院

结论：

1、对于任意一条直线段，它要么被完全排斥在窗口之外（？）；

2、要么在窗口内留下一个可见段，并且只能有一个可见段；

可通过对线段端点的简单判别，判断线段与窗口的关系。信息工程大学地理空间信息学院直接求交算法：信息工程大学地理空间信息学院（1）编码裁剪法（CoHen和Sutherland）基本思想：

线段P1P2分为三种情况处理:（1）若P1P2完全在窗口内，则显示该线段P1P2。（2）若P1P2明显在窗口外，则丢弃该线段。（3）若线段不满足（1）或（2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。信息工程大学地理空间信息学院为快速判断，采用如下编码方法:100100010101100000000100101000100110ABCD

将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。信息工程大学地理空间信息学院将区域码的各位从右到左编号，则坐标区域与各位的关系为： 上下右左 XXXX 编码规律：任何位赋值为1，代表端点落在相应的位置上，否则该位为0。例如：若端点在剪取矩形内，区域码为0000。若端点落在矩形的左下角，区域码为0101。信息工程大学地理空间信息学院具体点P(x,y)编码方法：

信息工程大学地理空间信息学院具体判断方法：给定所有的线段端点的区域码，快速判断哪条直线完全在窗口内，哪条直线完全在窗口外。若P1P2完全在窗口内code1=0,且code2=0,则“取”；若P1P2明显在窗口外code1&code2≠0，则“弃”；在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。(处理P1、P2)信息工程大学地理空间信息学院具体算法步骤：（设端点P1,P2的代码为C1,C2)两端点P1(X1,Y1)和P2(X2,Y2)在区域内0000,C1=C2=0全保留。当两个端点在窗口边线外的同侧位置,C1、C2按位与不等零，全舍弃。其它情况，需计算出直线与窗口边线的交点？，将直线分段后继续进行检查判断。信息工程大学地理空间信息学院裁剪例子：信息工程大学地理空间信息学院算法总结：特点：可快速判断线段的完全可见和不可见。简单，易于实现。算法中求交点（求法？）是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。特别适用二种场合：大窗口场合（大部分线段完全可见）；窗口特别小的场合（大部分线段完全不可见的情况下）——该算法特别有效。

在一般情况下，该算法有时要做不必要的求交运算，因而效率不是太高。信息工程大学地理空间信息学院（2）矢量裁剪法（自学）基本思想：与编码裁剪算法相类似，只是判别端点是否落在窗口内的过程不同。如图所示，我们同样用四条窗口边框直线把平面分割成九个区域，每一个区域分别标上相应的编号。XlXr316027845YtYbAB信息工程大学地理空间信息学院（3）中点分割裁剪法基本思想：分别寻找直线段两个端点各自对应最远的可见点，这两个可见点的连线就是原线段的可见部分。P1P2S2S1P2P2P2P1P1P1PmPmebadc信息工程大学地理空间信息学院最远的可见点只有两种选择：P1P2S2S1P2P2P2P1P1P1PmPmebadc要么是直线段一个相应端点；要么是在不断的中点再分过程中产生的某个子段的中点；信息工程大学地理空间信息学院具体实现：与编码裁剪算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。P1P2S2S1P2P2P2P1P1P1PmPmebadc信息工程大学地理空间信息学院例子：以找出直线段P1P2上离点P1最远的可见点

算法步骤：P1P2S2S1P2P2P2P1P1P1PmPmebadc（1）检验直线段P1、P2是否完全被排斥在窗口之外。如果是，过程结束且无输出线段（如图线段b）；否则继续执行下一步。信息工程大学地理空间信息学院（2）检验点P2是否可见。如果是，则点P2就是离点P1最远的可见点，过程结束（图线段a）。如果点P2是不可见的（如图线段c或线段d），那么继续执行下一步。P1P2S2S1P2P2P2P1P1P1PmPmebadc信息工程大学地理空间信息学院（3）分割直线段P1P2于中点Pm。如果线段PmP2被完全排斥在窗口之外，那么原估计不足（如图线段d），便以P1Pm线段作为新的线段从算法的第一步重新开始执行。反之，则以线段PmP2作为新的线段（如图线段c）从算法的第一步重新开始执行。P1P2S2S1P2P2P2P1P1P1PmPmebadc反复执行上述三步，直至找到离点P1最远的可见点。信息工程大学地理空间信息学院算法特点：

中点分割算法是编码裁剪算法的硬件版本。中点分割裁剪法只需用到加法和除2运算，而除2在计算机中可以简单地用右移一位来完成，从而提高了算法的效率，用硬件实现既简单又有效。信息工程大学地理空间信息学院3、多边形的裁剪

多边形定义：是由若干直线段围成的平面封闭图形。裁剪的结果，应是一个封闭的图形。平面多边形和窗口之间存在的三种位置关系：信息工程大学地理空间信息学院基本思路：多边形裁剪是以线段裁剪为基础，如果重复利用直线段的裁剪方法，对多边形进行裁剪，其结果出现问题？问题1、边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？信息工程大学地理空间信息学院问题2、凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？信息工程大学地理空间信息学院多边形裁剪首要解决两个问题：封闭多边形经裁剪后一般不再是封闭的需要用窗口边界适当部分来封闭；矩形窗口的四个角点在裁剪中是否要与其它交点连线；逐边裁剪法双边裁剪法分区编码裁剪法信息工程大学地理空间信息学院（1）逐边裁剪法逐边裁剪法是萨瑟兰德和霍德曼在1974年提出。基本思路：依次用窗口的一条边裁剪多边形，每次形成一个新的多边形。最后裁剪出来的多边形就是所需多边形。信息工程大学地理空间信息学院信息工程大学地理空间信息学院 具体步骤：(1)将多边形表示为顶点表，即｛P1，P2，…

…

Pn-1，Pn

｝,并生成边表P1P2，P2P3，…

…

Pn-1Pn，PnP1

(2)用窗口边裁剪原多边形，生成中间多边形(3)对中间多边形重复步骤(2)，直至被窗口所有边裁剪完为止信息工程大学地理空间信息学院

分割处理：

第一次分解：将多边形关于矩形窗口的裁剪分解为它 关于窗口四边所在直线的裁剪；

第二次分解：将多边形关于一条直线的裁剪分解为多 边形各边关于该直线的裁剪；

流水线过程(左上右下)：前边的结果是后边的输入。信息工程大学地理空间信息学院裁剪后的多边形的顶点序列如何组成？考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧。根据多边形的各条边与裁剪线位置关系决定输出几个顶点到多边形的顶点表中。多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种：信息工程大学地理空间信息学院情况（1）仅输出顶点P（S作为前一条终点输出）；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I；情况（4）输出线段SP与裁剪线的交点I和终点P信息工程大学地理空间信息学院裁剪多边形的顶点由两部分组成： 落在多边形内侧的原多边形的顶点； 多边形的边与裁剪边的交点；只要将这两部分顶点顺序连接起来，就得到裁剪结果多边形。信息工程大学地理空间信息学院算法特点：1、改进后的算法是通用的裁剪算法，任一多边形无论是凸多边形还凹多边形均可用这一算法进行剪取。2、算法简单，易于程序实现，但计算量较大，需要比较大的存贮区来存放剪取过程中待剪取的多边形。3、裁剪算法采用流水线方式，适合硬件实现。信息工程大学地理空间信息学院4、其它图形的裁剪（1）曲线的裁剪基本思