矢量图形的填充方法和矢量图形的填充装置

摘要

本发明提供了一种矢量图形的填充方法和矢量图形的填充装置，其中，所述矢量图形的填充方法包括：对待填充图形的多个矢量进行扫描求交处理，以获取所述多个矢量的线段描述数据；根据所述多个矢量中的与扫描线相交的矢量的所述线段描述数据，生成线上交点表；根据所述多个矢量的所述线段描述数据，得到所述多个矢量中的每个矢量的投影矢量，并将所述投影矢量插入到线间矢量链表中；根据所述线间矢量链表判断是否存在丢点的矢量，并根据判断结果对所述线上交点表进行更新；根据更新后的线上交点表输出所述待填充图形的点阵数据。通过本发明的技术方案，在填充图形时避免出现丢点，从而提高图形的显示效果。

说明书

技术领域

本发明涉及计算机图形处理技术领域，具体而言，涉及一种矢量图形的填充方法和一种矢量图形的填充装置。

背景技术

矢量图形是印前领域中大量使用的一种页面描述对象，由于它具有在坐标变换下的高度保真性，因而可以较为精确地还原出描述者的本来意图。文字是印前领域中大量使用的另一种页面描述对象，它的内部描述数据也是基于矢量图形的，因此，矢量图形的光栅化是整个印前输出系统的核心部件。矢量图形光栅化的主要工作是将用户坐标空间下的矢量描述数据转换为设备坐标空间下的点阵信息，其中最重要及最关键的一步，是对组成矢量图形对象的每一个路径按照一定的规则进行填充，得到相应的内部像素点阵描述信息。

一个路径由一个或多个子路径构成，一个子路径由一组首尾互相连接的直线矢量或曲线矢量构成，子路径所形成的轮廓是封闭的。对于单个的不自交的子路径，全部区域被其剖分而成的内部和外部十分明确，填充区域(即子路径所围的内部区域)一目了然；但对其他情形，则由于子路径本身可能存在自交，子路径与子路径之间也可能存在包含或相交的关系，内部与外部不再显而易见，因此必须考虑填充的缠绕规则，以便在子路径发生包含或相交的情况时据之确定填充区域。对于全部区域上的任意一点，以之为起点任意作一条通往无限远处的射线，该点有一个初始值为0的缠绕数，当路径中的某一子路径从左向右穿越该射线时，缠绕数加1，当路径中的某一子路径从右向左穿越该射线时，缠绕数减1，当计算完该路径与该射线所有的穿越情况之后，即得到该点最终的缠绕数，为此，可以定义两种缠绕规则：非零规则和奇偶规则。非零规则就是将那些缠绕数不等于0的点定义为内部点，其组成的区域为填充区域。奇偶规则则是将那些缠绕数为奇数的点定义为内部点，其组成的区域为填充区域。对于简单的路径，这两种缠绕规则定义的填充区域是相同的，填充结果自然也完全一样。但对于复杂的路径，这两种缠绕规则定义的填充区域就会产生差别，填充结果也会不一样。例如，有三个路径，分别构成五角星、内外同向圆环和内外异向圆环的形状，用非零规则填充的结果如图1A所示，用奇偶规则填充的结果如图1B所示。两种规则各有其方便适宜的应用领域，一种完善的矢量图形的填充方法需要正确处理这两种缠绕规则。

对一个路径进行填充的过程，可视为将该路径所围成的封闭区域内部的设备空间上的像素进行涂黑的过程。当一个像素完全落在填充区域内部时，毫无疑问该像素应当被涂黑；当一个像素完全落在填充区域外部时，毫无疑问该像素不当被涂黑；当一个像素一部分落在填充区域内部、一部分落在填充区域外部时，该像素是否应当被涂黑则是一个需要仔细考虑的问题，不同的处理规则可能会产生不同的填充结果，从而直接影响到最终结果的质量。对于较大尺寸的路径或者较高分辨率的情况，设备空间上的像素相对较多，路径的各个细节部分都包含了足够多的像素，因而无论采取何种像素涂黑规则，都能够得到满意的填充结果。(在高分辨率下填充字符“$”的路径，结果如图2A所示)一种常见的像素涂黑规则是“任意相交”，即只要一个像素的任意部分与填充区域内部相交就涂黑该像素，亦即当一个像素一部分落在填充区域内部、一部分落在填充区域外部时，涂黑该像素。采用任意相交的像素涂黑规则，可以保证不会出现丢点的现象，其实现也相对容易，然而，对于较小尺寸的路径或者较低分辨率的情况，设备空间上的像素相对较少，完全落在路径所围成的封闭区域内部的像素也相对减少，而部分落在路径所围成的封闭区域内部的像素则相对增多，此时采用任意相交的像素涂黑规则就会使得众多这样的路径边缘像素被涂黑，从而导致填充结果中细节大量丢失，图形畸变严重，特别地，基于矢量图形描述的小文字的填充结果会出现大量笔划粘连，变得难以辨识。(在低分辨率下用任意相交的像素涂黑规则填充字符“$”的路径，结果如图2B所示)为此，另一种像素涂黑规则应运而生，这就是“中心覆盖”规则，即只涂黑那些中心点被填充区域内部覆盖的像素，亦即当且仅当一个像素的中心点落在填充区域内部时，涂黑该像素。采用中心覆盖的像素涂黑规则可以有效地解决上述低分辨率下填充结果出现大量像素粘连、细节丢失、严重畸变从而导致可辨识性大大降低的问题。(在低分辨率下用中心覆盖的像素涂黑规则填充字符“$”的路径，结果如图2C所示)然而，单纯采用中心覆盖规则，也会产生新的问题，那就是当路径中存在较细的区域时，这些区域有可能会因为无法覆盖到任何像素中心而被丢失，由此将导致填充结果中出现丢点、断线甚至丢线等情况，特别地，基于矢量图形描述的小文字的填充结果会出现笔划的局部或整体性缺失，从而大大降低了文字的可辨识性。(在低分辨率下单纯用中心覆盖的像素涂黑规则填充较细字体的字符“$”的路径，结果如图2D所示)。

如何恰当地避免丢点是基于中心覆盖规则的矢量图形的填充方法面临的一大难题。在现有技术中，主要通过下列几种方式来应对这一难题：一、增加对丢点的弥补机制，当出现路径中的轮廓矢量以不同方向穿越某相邻两像素中心之间的连线(水平或竖直)并且该两个像素中心都未被路径的填充区域覆盖时，即认为发生了丢点，需要对上述两个像素之一进行涂黑以弥补丢点；这一方式主要对文字有效，因为文字的矢量路径描述相对比较规则，而对于一般图形的矢量路径描述，则当路径中存在一个子路径的所有轮廓矢量都不与任意相邻两像素中心之间的连线相交时，该子路径就会被丢失，因此丢点的问题仍然存在。二、利用反走样机制，对丢点在一定程度上进行弥补，但这种弥补只能是相对的，当丢点所对应的填充区域小到一定程度时，反走样就无法对其进行弥补了。可以看出，上述方式都各自存在较大的局限性，并不能彻底杜绝丢点的发生，因而无法忠实地还原图形矢量描述的意图。

因此，如何在填充图形时避免出现丢点，从而提高图形的显示效果成为亟待解决的技术问题。

发明内容

本发明正是基于上述技术问题，提出了一种新的技术方案，在填充图形时避免出现丢点，从而提高图形的显示效果。

有鉴于此，本发明的第一方面，提出了一种矢量图形的填充方法，包括：对待填充图形的多个矢量进行扫描求交处理，以获取所述多个矢量的线段描述数据；根据所述多个矢量中的与扫描线相交的矢量的所述线段描述数据，生成线上交点表；根据所述多个矢量的所述线段描述数据，得到所述多个矢量中的每个矢量的投影矢量，并将所述投影矢量插入到线间矢量链表中；根据所述线间矢量链表判断是否存在丢点的矢量，并根据判断结果对所述线上交点表进行更新；根据更新后的线上交点表输出所述待填充图形的点阵数据。

在该技术方案中，通过对待填充图形的多个矢量进行扫描求交处理，以生成线上交点表和线间矢量链表，然后根据线间矢量链表和线上交点表输出点阵数据，从而利用精致与简洁的算法和数据结构，快速而高效地发现可能出现的丢点，避免出现丢点，这样，一方面能够大大改善低分辨率下矢量图形途径的填充质量，另一方面又不遗漏待填充图形的任何一个矢量，从而最大限度地提高了待填充图形在设备空间的点阵结果中呈现出的效果。

在上述技术方案中，优选地，根据所述多个矢量的所述线段描述数据，得到所述多个矢量中的所述每个矢量的所述投影矢量的步骤，具体包括：将所述多个矢量中的与所述扫描线相交的矢量作为非线间矢量，将所述多个矢量中的与所述扫描线不相交的矢量作为线间矢量；根据所述线间矢量的所述线段描述数据，得到所述线间矢量在竖直或水平方向的投影，并将所述线间矢量在竖直或水平方向的投影作为所述投影矢量；以及获取所述非线间矢量被所述扫描线分割而成的矢量，根据所述非线间矢量的所述线段描述数据，得到被分割而成的矢量在竖直或水平方向上的投影，并将所述被分割而成的矢量在竖直或水平方向上的投影作为所述投影矢量。

在该技术方案中，通过将线间矢量的投影作为投影矢量加入到线间矢量链表中，以及将非线间矢量的被扫描线分割而成的每一部分的投影作为投影矢量插入到线间矢量链表中，从而根据线间矢量链表更加准确地确定是否发生丢点。

其中，若扫描线为水平方向的扫描线，将线间矢量在竖直方向的投影作为投影矢量，将被扫描线分割而成的每一部分在竖直方向的投影作为投影矢量；若扫描线为竖直方向的扫描线，将线间矢量在水平方向的投影作为投影矢量，将被扫描线分割而成的每一部分在水平方向的投影作为投影矢量。

在上述任一技术方案中，优选地，获取所述多个矢量的所述线段描述数据的步骤，具体包括：将所述非线间矢量与所述扫描线的交点信息记录到与所述非线间矢量对应的所述线段描述数据内；将所述线间矢量的端点坐标信息记录到与所述线间矢量对应的所述线段描述数据内。

在该技术方案中，非线间矢量的线段描述数据包括：非线间矢量与扫描线的交点信息，例如非线间矢量与扫描线交点的坐标值，线间矢量的线段描述数据包括：线间矢量的端点坐标信息。

在上述任一技术方案中，优选地，将所述投影矢量插入到所述线间矢量链表中的步骤，具体包括：判断所述线间矢量链表中是否存在指定矢量，其中，所述指定矢量的右端点比所述投影矢量的左端点靠右，或者所述指定矢量与所述投影矢量重合；若存在所述指定矢量，根据所述投影矢量和所述指定矢量的坐标信息，将所述投影矢量插入到所述线间矢量链表中；若不存在所述指定矢量，将所述投影矢量插入到所述线间矢量链表的表尾处。

在该技术方案中，在将投影矢量插入到线间矢量链表中时，通过判断线间矢量链表中矢量的右端点是否比投影矢量的左端点更靠右、或者与投影矢量重合，来确定投影矢量插入到线间矢量链表中的位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，根据所述投影矢量和所述指定矢量的坐标信息，将所述投影矢量插入到所述线间矢量链表中的步骤，具体包括：根据所述投影矢量的左端点相对于所述指定矢量的相对位置，确定所述投影矢量插入到所述线间矢量链表中的目标位置，并在所述目标位置处插入所述投影矢量；其中，所述相对位置包括以下之一：所述投影矢量的左端点在所述指定矢量的左端点的左边，所述投影矢量的左端点与所述指定矢量的左端点重合，所述投影矢量的左端点位于所述指定矢量的内部，所述投影矢量的左端点与所述指定矢量的右端点重合。

在该技术方案中，若线间矢量链表中指定矢量的右端点比投影矢量的左端点更靠右、或者与投影矢量重合，通过比较投影矢量的左端点相对于指定矢量的相对位置，确定投影矢量插入到线间矢量链表中的目标位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，将所述投影矢量插入到所述线间矢量链表中的步骤之后，包括：获取所述线间矢量链表中的在所述投影矢量之后的且与所述投影矢量相邻的另一矢量；根据所述投影矢量的右端点相对所述另一矢量的位置，对所述线间矢量链表进行相应的更新。

在该技术方案中，在将投影矢量插入到线间矢量链表之后，根据投影矢量之后的且与投影矢量相邻的另一矢量(即线间矢量链表中投影矢量的下一个矢量)与该投影矢量的右端点的位置，对线间矢量链表进行相应的更新。

在上述任一技术方案中，优选地，根据所述线间矢量链表判断是否存在丢点的矢量，并根据所述判断结果对所述线上交点表进行更新的步骤，具体包括：将所述线上交点表转换为线上交点链表；检查所述线间矢量链表中是否存在方向值为0的结点；若存在方向值为0的结点，判定所述方向值为0的结点对应的矢量发生了丢点，将所述方向值为0的结点对应的矢量的端点坐标信息添加到所述线上交点链表中；对所述线上交点链表中结点的坐标信息进行取整，并将取整后的坐标信息保存至所述线上交点表中。

在该技术方案中，通过将线上交点表转换为线上交点链表，使得对线上交点链表进行处理时更加方便，提高了数据处理的速度。然后通过依次检查线间矢量链表中的结点的方向值是否为0，若方向值为0，说明方向值为0的结点对应的矢量发生了丢点，则将该矢量的端点坐标信息添加到线上交点链表中，从而避免出现丢点。由于线上交点表中的坐标信息为正数，因此，在将线上交点链表中结点的坐标信息保存至线上交点表中之前，将结点的浮点数类型的坐标信息转换成整数类型的坐标信息。

在上述任一技术方案中，优选地，根据所述更新后的线上交点表输出所述待填充图形的所述点阵数据的步骤，具体包括：根据所述更新后的线上交点表中的数据，确定所述待填充图形的第一类型像素和第二类型像素的起始位置、终止位置和长度；根据所述第一类型像素和所述第二类型像素的起始位置、终止位置和长度，输出所述点阵数据。

在该技术方案中，第一类型像素和第二类型像素为黑段像素和白段像素，当然，在显示屏上显示图形时，第一类型像素和第二类型像素为亮像素和暗像素。

在上述任一技术方案中，优选地，线上交点表和线间矢量链表均以线为单位。

在上述任一技术方案中，优选地，对多个矢量进行扫描求交处理时，沿竖直方向用水平的扫描线进行扫描。

在上述任一技术方案中，优选地，在对多个矢量进行扫描求交处理的同时动态将投影矢量插入到线间矢量链表中。

在上述任一技术方案中，优选地，线间矢量链表使用完毕之后，清除线间矢量链表，以节省所占用的内存空间。

在上述任一技术方案中，优选地，以行为处理单位输出点阵数据。

本发明的第二方面，提出了一种矢量图形的填充装置，包括：第一获取单元，用于对待填充图形的多个矢量进行扫描求交处理，以获取所述多个矢量的线段描述数据；生成单元，用于根据所述多个矢量中的与扫描线相交的矢量的所述线段描述数据，生成线上交点表；处理单元，用于根据所述多个矢量的所述线段描述数据，得到所述多个矢量中的每个矢量的投影矢量，并将所述投影矢量插入到线间矢量链表中；第一更新单元，用于根据所述线间矢量链表判断是否存在丢点的矢量，并根据判断结果对所述线上交点表进行更新；输出单元，用于根据更新后的线上交点表输出所述待填充图形的点阵数据。

在该技术方案中，通过对待填充图形的多个矢量进行扫描求交处理，以生成线上交点表和线间矢量链表，然后根据线间矢量链表和线上交点表输出点阵数据，从而利用精致与简洁的算法和数据结构，快速而高效地发现可能出现的丢点，避免出现丢点，这样，一方面能够大大改善低分辨率下矢量图形途径的填充质量，另一方面又不遗漏待填充图形的任何一个矢量，从而最大限度地提高了待填充图形在设备空间的点阵结果中呈现出的效果。

在上述技术方案中，优选地，所述处理单元具体用于，将所述多个矢量中的与所述扫描线相交的矢量作为非线间矢量，将所述多个矢量中的与所述扫描线不相交的矢量作为线间矢量，根据所述线间矢量的所述线段描述数据，得到所述线间矢量在竖直或水平方向的投影，并将所述线间矢量在竖直或水平方向的投影作为所述投影矢量，以及获取所述非线间矢量被所述扫描线分割而成的矢量，根据所述非线间矢量的所述线段描述数据，得到被分割而成的矢量在竖直或水平方向上的投影，并将所述被分割而成的矢量在竖直或水平方向上的投影作为所述投影矢量。

在该技术方案中，通过将线间矢量的投影作为投影矢量加入到线间矢量链表中，以及将非线间矢量的被扫描线分割而成的每一部分的投影作为投影矢量插入到线间矢量链表中，从而根据线间矢量链表更加准确地确定是否发生丢点。

其中，若扫描线为水平方向的扫描线，将线间矢量在竖直方向的投影作为投影矢量，将被扫描线分割而成的每一部分在竖直方向的投影作为投影矢量；若扫描线为竖直方向的扫描线，将线间矢量在水平方向的投影作为投影矢量，将被扫描线分割而成的每一部分在水平方向的投影作为投影矢量。

在上述任一技术方案中，优选地，所述第一获取单元包括：存储单元，用于将所述非线间矢量与所述扫描线的交点信息记录到与所述非线间矢量对应的所述线段描述数据内，以及将所述线间矢量的端点坐标信息记录到与所述线间矢量对应的所述线段描述数据内。

在该技术方案中，非线间矢量的线段描述数据包括：非线间矢量与扫描线的交点信息，例如非线间矢量与扫描线交点的坐标值，线间矢量的线段描述数据包括：线间矢量的端点坐标信息。

在上述任一技术方案中，优选地，所述处理单元包括：判断单元，用于判断所述线间矢量链表中是否存在指定矢量，其中，所述指定矢量的右端点比所述投影矢量的左端点靠右，或者所述指定矢量与所述投影矢量重合；插入单元，用于当存在所述指定矢量时，根据所述投影矢量和所述指定矢量的坐标信息，将所述投影矢量插入到所述线间矢量链表中，当不存在所述指定矢量时，将所述投影矢量插入到所述线间矢量链表的表尾处。

在该技术方案中，在将投影矢量插入到线间矢量链表中时，通过判断线间矢量链表中矢量的右端点是否比投影矢量的左端点更靠右、或者与投影矢量重合，来确定投影矢量插入到线间矢量链表中的位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，所述插入单元具体用于，根据所述投影矢量的左端点相对于所述指定矢量的相对位置，确定所述投影矢量插入到所述线间矢量链表中的目标位置，并在所述目标位置处插入所述投影矢量；其中，所述相对位置包括以下之一：所述投影矢量的左端点在所述指定矢量的左端点的左边，所述投影矢量的左端点与所述指定矢量的左端点重合，所述投影矢量的左端点位于所述指定矢量的内部，所述投影矢量的左端点与所述指定矢量的右端点重合。

在该技术方案中，若线间矢量链表中指定矢量的右端点比投影矢量的左端点更靠右、或者与投影矢量重合，通过比较投影矢量的左端点相对于指定矢量的相对位置，确定投影矢量插入到线间矢量链表中的目标位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，所述处理单元还包括：第二获取单元，用于获取所述线间矢量链表中的在所述投影矢量之后的且与所述投影矢量相邻的另一矢量；第二更新单元，用于根据所述投影矢量的右端点相对所述另一矢量的位置，对所述线间矢量链表进行相应的更新。

在该技术方案中，在将投影矢量插入到线间矢量链表之后，根据投影矢量之后的且与投影矢量相邻的另一矢量(即线间矢量链表中投影矢量的下一个矢量)与该投影矢量的右端点的位置，对线间矢量链表进行相应的更新。

在上述任一技术方案中，优选地，所述第一更新单元包括：转换单元，用于将所述线上交点表转换为线上交点链表；检查单元，用于检查所述线间矢量链表中是否存在方向值为0的结点；所述第一更新单元具体用于，若存在方向值为0的结点，判定所述方向值为0的结点对应的矢量发生了丢点，将所述方向值为0的结点对应的矢量的端点坐标信息添加到所述线上交点链表中，对所述线上交点链表中结点的坐标信息进行取整，并将取整后的坐标信息保存至所述线上交点表中。

在该技术方案中，通过将线上交点表转换为线上交点链表，使得对线上交点链表进行处理时更加方便，提高了数据处理的速度。然后通过依次检查线间矢量链表中的结点的方向值是否为0，若方向值为0，说明方向值为0的结点对应的矢量发生了丢点，则将该矢量的端点坐标信息添加到线上交点链表中，从而避免出现丢点。由于线上交点表中的坐标信息为正数，因此，在将线上交点链表中结点的坐标信息保存至线上交点表中之前，将结点的浮点数类型的坐标信息转换成整数类型的坐标信息。

在上述任一技术方案中，优选地，所述输出单元包括：确定单元，用于根据所述更新后的线上交点表中的数据，确定所述待填充图形的第一类型像素和第二类型像素的起始位置、终止位置和长度；所述输出单元具体用于，根据所述第一类型像素和所述第二类型像素的起始位置、终止位置和长度，输出所述点阵数据。

在该技术方案中，第一类型像素和第二类型像素为黑段像素和白段像素，当然，在显示屏上显示图形时，第一类型像素和第二类型像素为亮像素和暗像素。

在上述任一技术方案中，优选地，线上交点表和线间矢量链表均以线为单位。

在上述任一技术方案中，优选地，对多个矢量进行扫描求交处理时，沿竖直方向用水平的扫描线进行扫描。

在上述任一技术方案中，优选地，在对多个矢量进行扫描求交处理的同时动态将投影矢量插入到线间矢量链表中。

在上述任一技术方案中，优选地，线间矢量链表使用完毕之后，清除线间矢量链表，以节省所占用的内存空间。

在上述任一技术方案中，优选地，以行为处理单位输出点阵数据。

通过以上技术方案，利用精致与简洁的算法和数据结构，快速而高效地发现可能出现的丢点，避免出现丢点，从而提高图形的显示效果。

附图说明

图1A示出了相关技术中的采用非零规则填充五角星和圆环状路径的效果示意图；

图1B示出了相关技术中的采用奇偶规则填充五角星和圆环状路径的效果示意图；

图2A示出了相关技术中的在高分辨率下填充字符“＄”的效果示意图；

图2B示出了相关技术中的在低分辨率下采用任意相交的像素涂黑规则填充字符“＄”的效果示意图；

图2C示出了相关技术中的在低分辨率下采用中心覆盖的像素涂黑规则填充字符“＄”的效果示意图；

图2D示出了相关技术中的在低分辨率下采用中心覆盖的像素涂黑规则填充较细字符“＄”的效果示意图；

图3示出了根据本发明的一个实施例的矢量图形的填充方法的流程示意图；

图4示出了根据本发明的一个实施例的线间矢量链表插入方法的流程示意图；

图5至图43示出了根据本发明的一个实施例的线间矢量链表插入过程的原理示意图；

图44示出了根据本发明的一个实施例的矢量图形的填充装置的框图。

具体实施方式

为了能够更清楚地理解本发明的上述目的、特征和优点，下面结合附图和具体实施方式对本发明进行进一步的详细描述。需要说明的是，在不冲突的情况下，本申请的实施例及实施例中的特征可以相互组合。

在下面的描述中阐述了很多具体细节以便于充分理解本发明，但是，本发明还可以采用其他不同于在此描述的其他方式来实施，因此，本发明的保护范围并不受下面公开的具体实施例的限制。

图3示出了根据本发明的一个实施例的矢量图形的填充方法的流程示意图。

如图3所示，根据本发明的一个实施例的矢量图形的填充方法，包括：

步骤302，对待填充图形的多个矢量进行扫描求交处理，以获取所述多个矢量的线段描述数据；

步骤304，根据所述多个矢量中的与扫描线相交的矢量的所述线段描述数据，生成线上交点表；

步骤306，根据所述多个矢量的所述线段描述数据，得到所述多个矢量中的每个矢量的投影矢量，并将所述投影矢量插入到线间矢量链表中；

步骤308，根据所述线间矢量链表判断是否存在丢点的矢量，并根据判断结果对所述线上交点表进行更新；

步骤310，根据更新后的线上交点表输出所述待填充图形的点阵数据。

在该技术方案中，通过对待填充图形的多个矢量进行扫描求交处理，以生成线上交点表和线间矢量链表，然后根据线间矢量链表和线上交点表输出点阵数据，从而利用精致与简洁的算法和数据结构，快速而高效地发现可能出现的丢点，避免出现丢点，这样，一方面能够大大改善低分辨率下矢量图形途径的填充质量，另一方面又不遗漏待填充图形的任何一个矢量，从而最大限度地提高了待填充图形在设备空间的点阵结果中呈现出的效果。

在上述技术方案中，优选地，根据所述多个矢量的所述线段描述数据，得到所述多个矢量中的所述每个矢量的所述投影矢量的步骤，具体包括：将所述多个矢量中的与所述扫描线相交的矢量作为非线间矢量，将所述多个矢量中的与所述扫描线不相交的矢量作为线间矢量；根据所述线间矢量的所述线段描述数据，得到所述线间矢量在竖直或水平方向的投影，并将所述线间矢量在竖直或水平方向的投影作为所述投影矢量；以及获取所述非线间矢量被所述扫描线分割而成的矢量，根据所述非线间矢量的所述线段描述数据，得到被分割而成的矢量在竖直或水平方向上的投影，并将所述被分割而成的矢量在竖直或水平方向上的投影作为所述投影矢量。

在该技术方案中，通过将线间矢量的投影作为投影矢量加入到线间矢量链表中，以及将非线间矢量的被扫描线分割而成的每一部分的投影作为投影矢量插入到线间矢量链表中，从而根据线间矢量链表更加准确地确定是否发生丢点。

其中，若扫描线为水平方向的扫描线，将线间矢量在竖直方向的投影作为投影矢量，将被扫描线分割而成的每一部分在竖直方向的投影作为投影矢量；若扫描线为竖直方向的扫描线，将线间矢量在水平方向的投影作为投影矢量，将被扫描线分割而成的每一部分在水平方向的投影作为投影矢量。

在上述任一技术方案中，优选地，获取所述多个矢量的所述线段描述数据的步骤，具体包括：将所述非线间矢量与所述扫描线的交点信息记录到与所述非线间矢量对应的所述线段描述数据内；将所述线间矢量的端点坐标信息记录到与所述线间矢量对应的所述线段描述数据内。

在该技术方案中，非线间矢量的线段描述数据包括：非线间矢量与扫描线的交点信息，例如非线间矢量与扫描线交点的坐标值，线间矢量的线段描述数据包括：线间矢量的端点坐标信息。

在上述任一技术方案中，优选地，将所述投影矢量插入到所述线间矢量链表中的步骤，具体包括：判断所述线间矢量链表中是否存在指定矢量，其中，所述指定矢量的右端点比所述投影矢量的左端点靠右，或者所述指定矢量与所述投影矢量重合；若存在所述指定矢量，根据所述投影矢量和所述指定矢量的坐标信息，将所述投影矢量插入到所述线间矢量链表中；若不存在所述指定矢量，将所述投影矢量插入到所述线间矢量链表的表尾处。

在该技术方案中，在将投影矢量插入到线间矢量链表中时，通过判断线间矢量链表中矢量的右端点是否比投影矢量的左端点更靠右、或者与投影矢量重合，来确定投影矢量插入到线间矢量链表中的位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，根据所述投影矢量和所述指定矢量的坐标信息，将所述投影矢量插入到所述线间矢量链表中的步骤，具体包括：根据所述投影矢量的左端点相对于所述指定矢量的相对位置，确定所述投影矢量插入到所述线间矢量链表中的目标位置，并在所述目标位置处插入所述投影矢量；其中，所述相对位置包括以下之一：所述投影矢量的左端点在所述指定矢量的左端点的左边，所述投影矢量的左端点与所述指定矢量的左端点重合，所述投影矢量的左端点位于所述指定矢量的内部，所述投影矢量的左端点与所述指定矢量的右端点重合。

在该技术方案中，若线间矢量链表中指定矢量的右端点比投影矢量的左端点更靠右、或者与投影矢量重合，通过比较投影矢量的左端点相对于指定矢量的相对位置，确定投影矢量插入到线间矢量链表中的目标位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，将所述投影矢量插入到所述线间矢量链表中的步骤之后，包括：获取所述线间矢量链表中的在所述投影矢量之后的且与所述投影矢量相邻的另一矢量；根据所述投影矢量的右端点相对所述另一矢量的位置，对所述线间矢量链表进行相应的更新。

在该技术方案中，在将投影矢量插入到线间矢量链表之后，根据投影矢量之后的且与投影矢量相邻的另一矢量(即线间矢量链表中投影矢量的下一个矢量)与该投影矢量的右端点的位置，对线间矢量链表进行相应的更新。

在上述任一技术方案中，优选地，步骤308具体包括：将所述线上交点表转换为线上交点链表；检查所述线间矢量链表中是否存在方向值为0的结点；若存在方向值为0的结点，判定所述方向值为0的结点对应的矢量发生了丢点，将所述方向值为0的结点对应的矢量的端点坐标信息添加到所述线上交点链表中；对所述线上交点链表中结点的坐标信息进行取整，并将取整后的坐标信息保存至所述线上交点表中。

在该技术方案中，通过将线上交点表转换为线上交点链表，使得对线上交点链表进行处理时更加方便，提高了数据处理的速度。然后通过依次检查线间矢量链表中的结点的方向值是否为0，若方向值为0，说明方向值为0的结点对应的矢量发生了丢点，则将该矢量的端点坐标信息添加到线上交点链表中，从而避免出现丢点。由于线上交点表中的坐标信息为正数，因此，在将线上交点链表中结点的坐标信息保存至线上交点表中之前，将结点的浮点数类型的坐标信息转换成整数类型的坐标信息。

下面详细说明上述技术方案：

对线上交点表中的数据根据交点坐标值(交点坐标信息)进行排序，同时根据缠绕规则确定出每个交点的黑白段类型。缠绕规则包括但不限于：非零规则和奇偶规则，根据缠绕规则可以确定线上交点表中的每个交点为内部点还是外部点，其中，内部点表示黑段类型，外部点表示白段类型；

将线上交点表转换为线上交点链表，依次检查线间矢量链表中的结点，若存在方向值为0的线间矢量，说明发生了竖直方向上的丢点，将其端点坐标加入线上交点链表，具体过程如下：

(1)若当前线上交点表为空，且之前为白段类型，则将当前线间矢量链表中的丢点线段以黑段形式直接加入当前线上交点表中，结束处理。

(2)否则，将当前线上交点表转换为线上交点链表，对线间矢量链表作如下循环处理：

(2.1)取线间矢量链表中的下一个丢点线段D(Dl，Dr)；

(2.2)到线上交点链表中找到水平坐标不大于Dl的最大结点l(Xl，Cl)，将线上交点链表的当前指针设置为l的下一个结点；

(2.3)到线上交点链表中找到水平坐标不大于Dr的最大结点r(Xr，Cr)，将线上交点链表的当前指针设置为r的下一个结点；

(2.4)若Xl等于Dl，此时无需新增结点，只需将l结点的黑白类型修改为黑；否则，在线上交点链表中l结点之后插入新结点nl(Dl，黑)；

(2.5)若l等于r，则在线上交点链表中Xnl结点之后插入新结点nr(Dr，Cr)；否则：

(2.5.1)若Xr等于Dr，此时无需新增结点，维持r结点不变；否则，将r结点修改为nr(Dr，Cr)，即令Xr为Dr；

(2.5.2)删除线上交点链表中从l到r之间(不包含端点)的结点；

对线上交点链表中的数据进行转换，将浮点数类型的坐标值取整转换为整数类型的坐标值，并在转换的同时判断出其中存在的水平方向上的丢点线段，根据相邻线段的填充情况对其进行弥补，将转换之后的结果保存回线上交点表，具体过程如下：

(1)对线上交点链表作如下循环处理：

(1.1)若线上交点链表的任一结点的黑白段类型与任一结点的上一个结点的黑白段类型相同，则丢弃此结点，不再保存到线上交点表中；

(1.2)若任一结点是黑点，则：

(1.2.1)丢弃任一结点之后的黑点，直至找到任一结点之后的下一个白点；

(1.2.2)若任一结点与其之后的下一个白点位于同一个设备像素之内，说明发生了水平方向上的黑色丢点，则弥补该丢点，将任一结点的坐标值取整后保存到线上交点表中；

(1.2.3)否则，进行非黑色丢点线段的坐标值取整转换，保存到线上交点表中；

(1.3)否则(即任一结点是白点的情况)：

(1.3.1)丢弃任一结点之后的白点，直至找到任一结点之后的下一个黑点；

(1.3.2)若任一结点与其之后的下一个黑点位于同一个设备像素之内，说明发生了水平方向上的白色丢点，则丢弃该丢点，不再保存到线上交点表中；

(1.3.3)否则，进行非白色丢点线段的坐标值取整转换，保存到线上交点表中。

在上述任一技术方案中，优选地，步骤310具体包括：根据所述更新后的线上交点表中的数据，确定所述待填充图形的第一类型像素和第二类型像素的起始位置、终止位置和长度；根据所述第一类型像素和所述第二类型像素的起始位置、终止位置和长度，输出所述点阵数据。

在该技术方案中，第一类型像素和第二类型像素为黑段像素和白段像素，当然，在显示屏上显示图形时，第一类型像素和第二类型像素为亮像素和暗像素。

在上述任一技术方案中，优选地，线上交点表和线间矢量链表均以线为单位。

在上述任一技术方案中，优选地，对多个矢量进行扫描求交处理时，沿竖直方向用水平的扫描线进行扫描。

在上述任一技术方案中，优选地，在对多个矢量进行扫描求交处理的同时动态将投影矢量插入到线间矢量链表中。

在上述任一技术方案中，优选地，线间矢量链表使用完毕之后，清除线间矢量链表，以节省所占用的内存空间。

在上述任一技术方案中，优选地，以行为处理单位输出点阵数据。

图4示出了根据本发明的一个实施例的线间矢量链表插入方法的流程示意图；图5至图43示出了根据本发明的一个实施例的线间矢量链表插入过程的原理示意图。

如图4所示，根据本发明的一个实施例的线间矢量链表插入方法，在该实施例中，将投影矢量Vn(Pnl，Pnr，Dn)插入到线间矢量链表中，投影矢量的左端点坐标为Pnl、右端点坐标为Pnr、方向值为Dn(取值为+1或者-1)，将Vn插入到线间矢量链表的具体过程包括：

步骤402，判断是否存在线间矢量链表？在判断结果为是时，进入步骤404，否则，进入步骤406；

步骤404，若存在线间矢量链表，从线间矢量链表中依次读取矢量，查找右端点比Vn左端点更靠右边或者重合的矢量V1(Pll，Plr，Dl)；

步骤406，若不存在线间矢量链表，创建线间矢量链表VBLL，将Vn直接插入到创建的线间矢量链表中；

步骤408，判断V1是否存在？在判断结果为是时，进入步骤412，否则，进入步骤410；

步骤410，若V1不存在，说明Vn比当前线间矢量链表VBLL中所有矢量都更靠右边且不相交，则将Vn插入到线间矢量链表的表尾处，如图5所示；

步骤412，根据Vn左端点与V1的位置关系进行相应处理，分以下情况处理：

(1.1)若Pnl<Pll，即Vn左端点在Vl左端点的左边，此时又分以下情况处理：

(1.1.1)Pnr<Pll，即Vn右端点在Vl左端点的左边，此时Vn完全位于Vl左边且不相交，则新增矢量Vnn(Pnl，Pnr，Dn)，插入线间矢量链表VBLL中Vl之前的位置，结束处理(如图6所示)；

(1.1.2)Pnr＝Pll，即Vn右端点与Vl左端点重合：

(1.1.2.1)若Dn＝Dl，说明两者可以合并，则令Pll为Pnl，其余不变，结束处理(如图7所示)；

(1.1.2.2)否则，新增矢量Vnn(Pnl，Pnr，Dn)，插入线间矢量链表VBLL中Vl之前的位置，结束处理(如图8所示)；

(1.1.3)Pll<Pnr<Plr，即Vn右端点位于Vl内部：

(1.1.3.1)若Dl＝0，则新增矢量Vnn(Pnl，Pnr，Dn)，插入线间矢量链表VBLL中Vl之前的位置；令Pll为Pnr，结束处理(如图9所示)；

(1.1.3.2)否则，新增矢量Vnnl(Pnl，Pll，Dn)和Vnnr(Pll，Pnr，Dl+Dn)，依次插入线间矢量链表VBLL中Vl之前的位置；令Pll为Pnr，结束处理(如图10所示)；

(1.1.4)Pnr＝Plr，即Vn右端点与Vl右端点重合：

(1.1.4.1)若Vl的下一个矢量Vm(Pml，Pmr，Dm)存在，且Plr＝Pml，Dm＝Dl+Dn，说明计算方向值之后的Vl和Vm可以合并，则令Pml为Pll；令Plr为Pll，Pll为Pnl，Dl为Dn，结束处理(如图11所示)；

(1.1.4.2)否则，若Dl＝0，则令Pll为Pnl，Dl为Dn，结束处理(如图12所示)；

(1.1.4.3)否则，新增矢量Vnn(Pnl，Pll，Dn)，插入线间矢量链表VBLL中Vl之前的位置，令Dl为Dl+Dn；结束处理(如图13所示)；

(1.1.5)Pnr>Plr，即Vn右端点在Vl右端点的右边：

(1.1.5.1)若Dl＝0，则令Pll为Pnl，Dl为Dn；设置处理未结束标志(如图14所示)；

(1.1.5.2)否则，新增矢量Vnn(Pnl，Pll，Dn)，插入线间矢量链表VBLL中Vl之前的位置，令Dl为Dl+Dn；设置处理未结束标志(如图15所示)。

(1.2)Pnl＝Pll，即Vn左端点与Vl左端点重合，此时又分以下情况处理：

(1.2.1)Pll<Pnr<Plr，即Vn右端点位于Vl内部：

(1.2.1.1)若Vl的上一个矢量Vk(Pkl，Pkr，Dk)存在且Pkr＝Pll且Dk＝Dl+Dn，说明计算方向值之后的Vl和Vk可以部分合并，则令Pkr为Pnr；令Pll为Pnr，结束处理(如图16所示)；

(1.2.1.2)否则，新增矢量Vnn(Pnl，Pnr，Dl+Dn)，插入线间矢量链表VBLL中Vl之前的位置，令Pll为Pnr，结束处理(如图17所示)。

(1.2.2)Pnr＝Plr，即Vn右端点与Vl右端点重合，此时只需计算方向值，同时检查是否可以与前后相邻的矢量合并：

(1.2.2.1)若Vl的上一个矢量Vk(Pkl，Pkr，Dk)存在且Pkr＝Pll且Dk＝Dl+Dn，说明计算方向值之后的Vl和Vk可以合并，则令Pll为Pkl，令Dl为Dk，从线间矢量链表VBLL中删除Vk；结束处理(如图18所示)；

(1.2.2.2)若Vl的下一个矢量Vm(Pml，Pmr，Dm)存在且Plr＝Pml且Dm＝Dl+Dn，说明计算方向值之后的Vl和Vm可以合并，则令Plr为Pmr，令Dl为Dm，从当前线间矢量链表VBLL中删除Vm，结束处理(如图19所示)；

(1.2.2.3)若不满足上述两种情况，说明计算方向值之后的Vl与前后相邻的矢量不可合并，则令Dl为Dl+Dn，结束处理(如图20所示)；

(1.2.3)Pnr>Plr，即Vn右端点在Vl右端点的右边：

(1.2.3.1)若Vl的上一个矢量Vk(Pkl，Pkr，Dk)存在且Pkr＝Pll且Dk＝Dl+Dn，说明计算方向值之后的Vl和Vk可以合并，则令Pll为Pkl，令Dl为Dk，从当前线间矢量链表VBLL中删除Vk；设置处理未结束标志(如图21所示)；

(1.2.3.2)否则，令Dl为Dl+Dn；设置处理未结束标志(如图22所示)；

(1.3)Pll<Pnl<Plr，即Vn左端点位于Vl内部，此时又分以下情况处理：

(1.3.1)Pnr<Plr，即Vn右端点也位于Vl内部，此时Vn完全位于Vl内部，则新增矢量Vnnl(Pll，Pnl，Dl)和Vnnr(Pnl，Pnr，Dl+Dn)，依次插入线间矢量链表VBLL中Vl之前的位置，令Pll为Pnr，结束处理(如图23所示)；

(1.3.2)Pnr＝Plr，即Vn右端点与Vl右端点重合：

(1.3.2.1)若Vl的下一个矢量Vm(Pml，Pmr，Dm)存在且Plr＝Pml且Dm＝Dl+Dn，说明计算方向值之后的Vl和Vm可以部分合并，则令Plr为Pnl，令Pml为Pnl，结束处理(如图24所示)；

(1.3.2.2)否则，新增矢量Vnn(Pll，Pnl，Dl)，插入线间矢量链表VBLL中Vl之前的位置，令Pll为Pnl，Dl为Dl+Dn，结束处理(如图25所示)；

(1.3.3)Pnr>Plr，即Vn右端点在Vl右端点的右边，则新增矢量Vnn(Pll，Pnl，Dl)，插入当前线间矢量链表VBLL中Vl之前的位置，令Pll为Pnl，Dl为Dl+Dn，设置处理未结束标志(如图26所示)；

(1.4)Pnl＝Plr，即Vn左端点与Vl右端点重合，此时又分以下情况处理：

(1.4.1)若Vl的下一个矢量Vm(Pml，Pmr，Dm)不存在，说明Vl是当前线间矢量链表VBLL表尾：

(1.4.1.1)若Dn＝Dl，说明两者可以合并，则令Plr为Pnr，结束处理(如图27所示)；

(1.4.1.2)否则，新增矢量Vnn(Pnl，Pnr，Dn)，插入线间矢量链表VBLL表尾，结束处理(如图28所示)；

(1.4.2)否则，分以下情况处理：

(1.4.2.1)Pnl＝Pml：说明Vn左端点与Vm左端点重合，则可将Vm视为Vl，采用与(d.2)类似的方式进行处理(如图29所示)；

(1.4.2.2)Pnl<Pml：说明Vn左端点在Vm左端点的左边，则可将Vm视为Vl，采用与(d.1)类似的方式进行处理(如图30所示)；

步骤414，判断V1的下一个矢量Vm存在且处理未结束？在判断结果为是时，进入步骤416，否则进入步骤418；

步骤416，根据Vn左端点与V1及Vm的位置关系进行相应处理，具体处理过程如下：

(2.1)若Pnr<Pml，即Vn右端点在Vm左端点的左边，则：

(2.1.1)若Dn＝Dl，则令Plr为Pnr，结束处理(如图31所示)。

(2.1.2)否则，新增矢量Vnn(Plr，Pnr，Dn)，插入线间矢量链表VBLL中Vm之前的位置，结束处理(如图32所示)。

(2.2)否则：

(2.2.1)处理Vn中间途经的矢量，根据方向值或合并或新增矢量，具体过程如下：

(2.2.1.1)若Plr<Pml，则：

(2.2.1.1.1)若Dn＝Dl，则令Plr为Pml(如图33所示)；

(2.2.1.1.2)否则，新增矢量Vnn(Plr，Pml，Dn)，插入线间矢量链表VBLL中Vm之前的位置(如图34所示)；

(2.2.1.2)令Vl为Vm的上一个矢量；

(2.2.2)分以下情况处理：

(2.2.2.1)Pnr＝Pml，即Vn右端点与Vm左端点重合：

(2.2.2.1.1)若Dl＝Dm，说明更新之后的Vl和Vm可以合并，则令Pml为Pll，从线间矢量链表VBLL中删除Vl(如图35所示)；

(2.2.2.1.2)结束处理，对于未作合并的情况，如图36所示；

(2.2.2.2)Pml<Pnr<Pmr，即Vn右端点位于Vm内部：

(2.2.2.2.1)若Dl＝Dm+Dn，说明计算方向值之后的Vl和Vm可以部分合并，则令Plr为Pnr；令Pml为Pnr；结束处理(如图37所示)。

(2.2.2.2.2)否则，新增矢量Vnnr(Pml，Pnr，Dm+Dn)，插入线间矢量链表VBLL中Vm之前的位置，令Pml为Pnr，结束处理(如图38所示)；

(2.2.2.3)Pnr＝Pmr，即Vn右端点与Vm右端点重合：

(2.2.2.3.1)若Dl＝Dm+Dn，说明计算方向值之后的Vl和Vm可以合并，则令Pml为Pll，从线间矢量链表VBLL中删除Vl(如图39所示)；

(2.2.2.3.2)若Vm的下一个矢量Vs存在且Pmr＝Psl且Ds＝Dm+Dn，说明计算方向值之后的Vm和Vs可以合并，则令Pmr为Psr，从线间矢量链表VBLL中删除Vs(如图40所示)；

(2.2.2.3.3)修改Vm的方向值，令Dm为Dm+Dn，结束处理，对于未作合并的情况，如图41所示；

(2.2.2.4)Pnr>Pmr，即Vn右端点在Vm右端点的右边，此时Vm完全位于Vn内部：

(2.2.2.4.1)若Dl＝Dm+Dn，说明计算方向值之后的Vl和Vm可以合并，则令Pml为Pll，从线间矢量链表VBLL中删除Vl(如图42所示)；

(2.2.2.4.2)修改Vm的方向值，令Dm为Dm+Dn，设置处理未结束标志，对于未作合并的情况，如图43所示。

步骤418，若处理未结束，将Vn合并插入线间矢量链表VBLL表尾，结束处理。

图44示出了根据本发明的一个实施例的矢量图形的填充装置的框图。

如图44所示，根据本发明的一个实施例的矢量图形的填充装置4400，包括：第一获取单元4402、生成单元4404、处理单元4406、第一更新单元4408和输出单元4410，其中，第一获取单元4402用于对待填充图形的多个矢量进行扫描求交处理，以获取所述多个矢量的线段描述数据；生成单元4404，用于根据所述多个矢量中的与扫描线相交的矢量的所述线段描述数据，生成线上交点表；处理单元4406，用于根据所述多个矢量的所述线段描述数据，得到所述多个矢量中的每个矢量的投影矢量，并将所述投影矢量插入到线间矢量链表中；第一更新单元4408，用于根据所述线间矢量链表判断是否存在丢点的矢量，并根据判断结果对所述线上交点表进行更新；输出单元4410，用于根据更新后的线上交点表输出所述待填充图形的点阵数据。

在该技术方案中，通过对待填充图形的多个矢量进行扫描求交处理，以生成线上交点表和线间矢量链表，然后根据线间矢量链表和线上交点表输出点阵数据，从而利用精致与简洁的算法和数据结构，快速而高效地发现可能出现的丢点，避免出现丢点，这样，一方面能够大大改善低分辨率下矢量图形途径的填充质量，另一方面又不遗漏待填充图形的任何一个矢量，从而最大限度地提高了待填充图形在设备空间的点阵结果中呈现出的效果。

在上述技术方案中，优选地，所述处理单元4406具体用于，将所述多个矢量中的与所述扫描线相交的矢量作为非线间矢量，将所述多个矢量中的与所述扫描线不相交的矢量作为线间矢量，根据所述线间矢量的所述线段描述数据，得到所述线间矢量在竖直或水平方向的投影，并将所述线间矢量在竖直或水平方向的投影作为所述投影矢量，以及获取所述非线间矢量被所述扫描线分割而成的矢量，根据所述非线间矢量的所述线段描述数据，得到被分割而成的矢量在竖直或水平方向上的投影，并将所述被分割而成的矢量在竖直或水平方向上的投影作为所述投影矢量。

在该技术方案中，通过将线间矢量的投影作为投影矢量加入到线间矢量链表中，以及将非线间矢量的被扫描线分割而成的每一部分的投影作为投影矢量插入到线间矢量链表中，从而根据线间矢量链表更加准确地确定是否发生丢点。

其中，若扫描线为水平方向的扫描线，将线间矢量在竖直方向的投影作为投影矢量，将被扫描线分割而成的每一部分在竖直方向的投影作为投影矢量；若扫描线为竖直方向的扫描线，将线间矢量在水平方向的投影作为投影矢量，将被扫描线分割而成的每一部分在水平方向的投影作为投影矢量。

在上述任一技术方案中，优选地，所述第一获取单元4402包括：存储单元44022，用于将所述非线间矢量与所述扫描线的交点信息记录到与所述非线间矢量对应的所述线段描述数据内，以及将所述线间矢量的端点坐标信息记录到与所述线间矢量对应的所述线段描述数据内。

在该技术方案中，非线间矢量的线段描述数据包括：非线间矢量与扫描线的交点信息，例如非线间矢量与扫描线交点的坐标值，线间矢量的线段描述数据包括：线间矢量的端点坐标信息。

在上述任一技术方案中，优选地，所述处理单元4406包括：判断单元44062，用于判断所述线间矢量链表中是否存在指定矢量，其中，所述指定矢量的右端点比所述投影矢量的左端点靠右，或者所述指定矢量与所述投影矢量重合；插入单元44064，用于当存在所述指定矢量时，根据所述投影矢量和所述指定矢量的坐标信息，将所述投影矢量插入到所述线间矢量链表中，当不存在所述指定矢量时，将所述投影矢量插入到所述线间矢量链表的表尾处。

在该技术方案中，在将投影矢量插入到线间矢量链表中时，通过判断线间矢量链表中矢量的右端点是否比投影矢量的左端点更靠右、或者与投影矢量重合，来确定投影矢量插入到线间矢量链表中的位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，所述插入单元44064具体用于，根据所述投影矢量的左端点相对于所述指定矢量的相对位置，确定所述投影矢量插入到所述线间矢量链表中的目标位置，并在所述目标位置处插入所述投影矢量；其中，所述相对位置包括以下之一：所述投影矢量的左端点在所述指定矢量的左端点的左边，所述投影矢量的左端点与所述指定矢量的左端点重合，所述投影矢量的左端点位于所述指定矢量的内部，所述投影矢量的左端点与所述指定矢量的右端点重合。

在该技术方案中，若线间矢量链表中指定矢量的右端点比投影矢量的左端点更靠右、或者与投影矢量重合，通过比较投影矢量的左端点相对于指定矢量的相对位置，确定投影矢量插入到线间矢量链表中的目标位置，从而保证线间矢量链表的准确性，进而最大可能地发现可能出现的丢点。

在上述任一技术方案中，优选地，所述处理单元4406还包括：第二获取单元44066，用于获取所述线间矢量链表中的在所述投影矢量之后的且与所述投影矢量相邻的另一矢量；第二更新单元44068，用于根据所述投影矢量的右端点相对所述另一矢量的位置，对所述线间矢量链表进行相应的更新。

在该技术方案中，在将投影矢量插入到线间矢量链表之后，根据投影矢量之后的且与投影矢量相邻的另一矢量(即线间矢量链表中投影矢量的下一个矢量)与该投影矢量的右端点的位置，对线间矢量链表进行相应的更新。

在上述任一技术方案中，优选地，所述第一更新单元4408包括：转换单元44082，用于将所述线上交点表转换为线上交点链表；检查单元44084，用于检查所述线间矢量链表中是否存在方向值为0的结点；所述第一更新单元4408具体用于，若存在方向值为0的结点，判定所述方向值为0的结点对应的矢量发生了丢点，将所述方向值为0的结点对应的矢量的端点坐标信息添加到所述线上交点链表中，对所述线上交点链表中结点的坐标信息进行取整，并将取整后的坐标信息保存至所述线上交点表中。

在该技术方案中，通过将线上交点表转换为线上交点链表，使得对线上交点链表进行处理时更加方便，提高了数据处理的速度。然后通过依次检查线间矢量链表中的结点的方向值是否为0，若方向值为0，说明方向值为0的结点对应的矢量发生了丢点，则将该矢量的端点坐标信息添加到线上交点链表中，从而避免出现丢点。由于线上交点表中的坐标信息为正数，因此，在将线上交点链表中结点的坐标信息保存至线上交点表中之前，将结点的浮点数类型的坐标信息转换成整数类型的坐标信息。

下面详细说明上述技术方案：

对线上交点表中的数据根据交点坐标值(交点坐标信息)进行排序，同时根据缠绕规则确定出每个交点的黑白段类型。缠绕规则包括但不限于：非零规则和奇偶规则，根据缠绕规则可以确定线上交点表中的每个交点为内部点还是外部点，其中，内部点表示黑段类型，外部点表示白段类型；

将线上交点表转换为线上交点链表，依次检查线间矢量链表中的结点，若存在方向值为0的线间矢量，说明发生了竖直方向上的丢点，将其端点坐标加入线上交点链表，具体过程如下：

(1)若当前线上交点表为空，且之前为白段类型，则将当前线间矢量链表中的丢点线段以黑段形式直接加入当前线上交点表中，结束处理。

(2)否则，将当前线上交点表转换为线上交点链表，对线间矢量链表作如下循环处理：

(2.1)取线间矢量链表中的下一个丢点线段D(Dl，Dr)；

(2.2)到线上交点链表中找到水平坐标不大于Dl的最大结点l(Xl，Cl)，将线上交点链表的当前指针设置为l的下一个结点；

(2.3)到线上交点链表中找到水平坐标不大于Dr的最大结点r(Xr，Cr)，将线上交点链表的当前指针设置为r的下一个结点；

(2.4)若Xl等于Dl，此时无需新增结点，只需将l结点的黑白类型修改为黑；否则，在线上交点链表中l结点之后插入新结点nl(Dl，黑)；

(2.5)若l等于r，则在线上交点链表中Xnl结点之后插入新结点nr(Dr,Cr)；否则：

(2.5.1)若Xr等于Dr，此时无需新增结点，维持r结点不变；否则，将r结点修改为nr(Dr，Cr)，即令Xr为Dr；

(2.5.2)删除线上交点链表中从l到r之间(不包含端点)的结点；

对线上交点链表中的数据进行转换，将浮点数类型的坐标值取整转换为整数类型的坐标值，并在转换的同时判断出其中存在的水平方向上的丢点线段，根据相邻线段的填充情况对其进行弥补，将转换之后的结果保存回线上交点表，具体过程如下：

(1)对线上交点链表作如下循环处理：

(1.1)若线上交点链表的任一结点的黑白段类型与任一结点的上一个结点的黑白段类型相同，则丢弃此结点，不再保存到线上交点表中；

(1.2)若任一结点是黑点，则：

(1.2.1)丢弃任一结点之后的黑点，直至找到任一结点之后的下一个白点；

(1.2.2)若任一结点与其之后的下一个白点位于同一个设备像素之内，说明发生了水平方向上的黑色丢点，则弥补该丢点，将任一结点的坐标值取整后保存到线上交点表中；

(1.2.3)否则，进行非黑色丢点线段的坐标值取整转换，保存到线上交点表中；

(1.3)否则(即任一结点是白点的情况)：

(1.3.1)丢弃任一结点之后的白点，直至找到任一结点之后的下一个黑点；

(1.3.2)若任一结点与其之后的下一个黑点位于同一个设备像素之内，说明发生了水平方向上的白色丢点，则丢弃该丢点，不再保存到线上交点表中；

(1.3.3)否则，进行非白色丢点线段的坐标值取整转换，保存到线上交点表中。

在上述任一技术方案中，优选地，所述输出单元4410包括：确定单元44102，用于根据所述更新后的线上交点表中的数据，确定所述待填充图形的第一类型像素和第二类型像素的起始位置、终止位置和长度；所述输出单元4410具体用于，根据所述第一类型像素和所述第二类型像素的起始位置、终止位置和长度，输出所述点阵数据。

在该技术方案中，第一类型像素和第二类型像素为黑段像素和白段像素，当然，在显示屏上显示图形时，第一类型像素和第二类型像素为亮像素和暗像素。

在上述任一技术方案中，优选地，线上交点表和线间矢量链表均以线为单位。

在上述任一技术方案中，优选地，对多个矢量进行扫描求交处理时，沿竖直方向用水平的扫描线进行扫描。

在上述任一技术方案中，优选地，在对多个矢量进行扫描求交处理的同时动态将投影矢量插入到线间矢量链表中。

在上述任一技术方案中，优选地，线间矢量链表使用完毕之后，清除线间矢量链表，以节省所占用的内存空间。

在上述任一技术方案中，优选地，以行为处理单位输出点阵数据。

以上结合附图详细说明了本发明的技术方案，通过本发明的技术方案，利用精致与简洁的算法和数据结构，快速而高效地发现可能出现的丢点，避免出现丢点，从而提高图形的显示效果。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。