基于包围盒树的多边形裁剪方法、电子设备及存储介质

技术领域

本申请涉及计算机图形处理领域，尤其是涉及一种基于包围盒树的多边形裁剪方法、电子设备及存储介质。

背景技术

多边形裁剪通常是指计算两个多边形内部共同部分的过程，即寻找一个多边形区域位于另一个多边形区域内的部分。前者常称作实体多边形，记作S；而后者常称作裁剪多边形，记作C。多边形裁剪作为一种基本操作，在计算机图形学、计算机辅助设计、地理信息系统等领域被广泛应用。在实际应用中通常需要执行成千上万次的多边形裁剪，而多边形的顶点个数可能达到数十万甚至数百万，同时多边形可能为任意形状，例如凹多边形或者包含孔洞的多边形，所以发展一种快速、通用的多边形裁剪算法具有重要意义。

在多年发展过程中，涌现了多种著名的多边形裁剪算法。其中用于矩形裁剪的算法有Liang和Barsky算法、Mailot算法。Surtherland和Hodgeman算法要求裁剪的多边形是凸多边形。

对于任意多边形裁剪(即参与裁剪的多边形包含孔洞，或者是自相交多边形)，现有方法大致可以分为：Vatti算法以及Martínez算法都采用了平面扫描(plane sweep)的思想，将多边形表示为边(线段)，通过一系列水平(垂直)扫描线扫描多边形，寻找满足特定规则的线段，连接相邻的线段得到结果多边形。Greiner和Hormann算法，它将多边形表示为顶点列表，寻找两个多边形的所有交点，将交点插入多边形顶点列表，根据交点出入性遍历顶点列表得到结果多边形。

但是Vatti算法以及Martínez算法都需要复杂的步骤寻找中间表示，相对来说算法比较复杂；而Greiner和Hormann算法，虽然算法简单易于实现，但是寻找交点的过程比较耗时。

发明内容

为了解决Greiner和Hormann算法寻找交点的过程比较耗时的问题，本申请提供一种基于包围盒树的多边形裁剪方法、电子设备及存储介质。

第一方面，本申请提供的一种基于包围盒树的多边形裁剪方法，采用如下的技术方案：

一种基于包围盒树的多边形裁剪方法，包括以下步骤：

分别建立实体多边形和裁剪多边形的顶点包围盒二叉树，获得实体树和裁剪树；其中，所述实体树和裁剪树的每个节点都是一个包含部分顶点的包围盒；

分别遍历两棵二叉树，每层分别将实体树的节点与裁剪树的节点进行相交判断，寻找交点；然后对有相交节点的子树继续进行遍历，直至结束；

根据实体多边形顶点、裁剪多边形顶点和遍历获得的交点，建立顶点虚拟列表；

遍历所述的顶点虚拟列表，得到裁剪结果多边形。

通过采用以上技术方案，本身请通过利用包围盒二叉树快速查找两个多边形的交点，然后对交点列表处理得到多边形被裁剪区域，具体的说，通过分别建立实体多边形和裁剪多边形的顶点包围盒二叉树，获得实体树和裁剪树；然后分别遍历两棵二叉树，每层分别将实体树的节点与裁剪树的节点进行相交判断，寻找交点；然后对有相交节点的子树继续进行遍历，直至结束，也就是说，在遍历包围盒二叉树寻找交点时，只有相交节点的子节点才需要进一步进行相交判断，这样能够减少对边相交判断的次数，大大提高了寻找交点的效率。

优选的，建立实体多边形和裁剪多边形的顶点包围盒二叉树时，采用自底向上的方法，先将顶点按照预设参数分组(相邻的多个顶点为一组)，每组求解它们的包围盒；然后将相邻的包围盒两两合并，一直到只剩下一个包围盒，则包围盒树构建完成。由于包围盒计算时间复杂度为线性，采用自底向上法建立实体多边形和裁剪多边形的顶点包围盒二叉树比自顶向下法效率更高，从而进一步提高了多边形裁剪的速度。

优选的，具体通过以下方法建立实体多边形或裁剪多边形的顶点包围盒二叉树：

遍历实体多边形或裁剪多边形的所有顶点{p

遍历包围盒序列

重复上一步骤，直至合并得到最后一个包围盒

通过采用以上技术方案(自底向上法)，(相比自顶向下法)从而可以实现更快速的建立实体多边形或裁剪多边形的顶点包围盒二叉树。

优选的，通过以下方法计算二维平面上一组点的包围盒：假定需要计算N个顶点的包围盒，将起点和终点形成的向量

通过以上方法计算二维平面上一组点的包围盒，从而提高了计算包围盒的速度，以及简化了合并子节点包围盒生成父节点包围盒的运算，即同时提高了父节点包围盒的计算速度(而采用最小旋转矩形获得包围盒时，父节点在合并两个包围盒时，不能直接使用两个子节点包围盒的边界顶点计算，而只能使用子节点包含的多边形顶点进行计算，导致的包围盒获取效率低下)，从而快捷地构建包围盒的二叉树，进一步提高了寻找交点的效率；同时该方法也可以克服轴对齐矩形包含“空隙”较多的问题，在对节点进行碰撞检测时能够获得更准确的结果，最终提高寻找交点的效率。

优选的，包围盒二叉树的父节点包围盒通过以下方法计算获得：

将左子节点包含顶点的起点和右子节点包含顶点的终点形成的向量的方向作为父节点的主方向；

将坐标系进行旋转使得横坐标OX与主方向平行(从而将计算近似最小旋转矩形转化为求取轴对齐矩形问题)；

计算包含左右子节点近似最小旋转矩形所有边界顶点的轴对齐矩形；

对所述轴对齐矩形的四个边界顶点进行反向旋转，即计算顶点在原始坐标系下的坐标，从而得到父节点的近似最小旋转矩形，即获得包围盒二叉树的父节点包围盒；

其中，所述的左右子节点的近似最小旋转矩形通过以下方式获得：

假定需要计算N个顶点的包围盒，将起点和终点形成的向量

求轴对齐矩形，然后对其四个边界顶点进行反向旋转，即计算顶点在原始坐标系下的坐标，从而得到近似最小旋转矩形，即N个顶点的包围盒。

通过采用以上的包围盒求解方法，不仅能快速求解任意个数点的包围盒，而且能以固定时间合并两个包围盒形成包含两个包围盒所有点的新包围盒，为构造包围盒树提供了一种高效的方法，也就是说，本申请提出的包围盒求解方法不仅具有线性时间复杂度，而且合并两个包围盒时具有常量时间复杂度，从而进一步提高了多边形裁剪时寻找交点的速度，进而提高了获得裁剪多边形的速度，也提高了计算包围盒的速度。

优选的，分别遍历两棵二叉树时，对两个二叉树进行广度优先遍历，沿着深度方向进行碰撞检测；每层分别将实体树的节点与裁剪树的节点进行相交判断时，交点由叶子节点包含的线段与线段之间进行相交判断得到。从而可以对不相交的边在高层级进行快速剪枝，相交的边才能走到两棵树的最底部到达叶子节点，从而提高了多边形裁剪时寻找交点的效率。

顶点只需要保存坐标信息x，y，而交点额外保存了一些属性，分别描述如下：

entry_exit表示该交点的方向，如果属于入点，则值为true，否则为false。

used表示该交点是否被处理，初始时被赋值为false，遍历虚拟列表时经过该交点被赋值为true。

index0、index1分别表示该交点在实体多边形和裁剪多边形顶点数组中的位置，它由两部分信息综合得到，生成交点的边的起始端点在顶点数组中的下标，加上交点到起始端点的归一化距离(即交点到起始端点的距离与边长度的比)。其实际上相当于指向待插入位置的指针，使得遍历虚拟列表时能够以固定时间将交点插入结果多边形。

next_intersection表示在裁剪多边形中紧随当前交点的那个交点在交点数组中的下标，用于遍历虚拟列表时确定在裁剪多边形中需要经历的顶点。

实体多边形和裁剪多边形直接保存为顶点数组，在裁剪过程中不会发生改变。在寻找交点过程中会得到交点坐标，同时根据生成交点的两条边，可以判断交点的方向和它在多边形顶点数组中的位置

更优选的，通过以下方法寻找交点：

(1)初始化交点数组为空；从实体多边形和裁剪多边形对应二叉树的根节点开始进行碰撞检测；如果两者不相交(说明实体多边形和裁剪多边形不存在交点)，则寻找交点过程结束；否则，记录相交的节点对(由实体树的根节点和裁剪树的根节点构成)形成相交节点对列表，转入步骤(2)；

(2)初始化一个空列表作为结果列表，遍历相交节点对列表，对每个相交节点对进行如下处理：

a)如果相交节点对中两个节点都是叶子节点，则转入步骤b)；否则将叶子节点以及非叶子节点的子节点作为候选节点，分别使用实体二叉树的候选节点和裁剪二叉树的候选节点进行碰撞检测，将检测到的相交节点对加入结果列表；

b)对实体二叉树叶子节点和裁剪二叉树叶子节点所包含的多边形边分别进行相交检测(二叉树叶子节点包含多边形的Q个(最后一个叶子节点可能包含少于Q个)顶点，也就是说Q-1条边(相邻两个顶点的连线称作一条边)；假设实体多边形叶子节点包含p条边，裁剪多边形叶子节点包含q条边，那么将进行p×q次相交比较)，如果没有任何交点，则该相交节点对处理结束；否则，对检测到的每个交点执行步骤c)；

c)新建一个交点数据结构的实例(即创建一个存储交点数据的变量，变量的子成员x、y分别记录了交点的坐标。子成员index0记录了交点在实体多边形顶点列表中的位置；子成员index1记录了交点在裁剪多边形顶点列表中的位置)，用x，y记录交点的坐标；如果实体多边形的边进入了裁剪多边形，则置entry_exit为true，否则置为false；计算交点在实体多边形顶点列表中的位置index0(即先得到交点到起始端点的距离与边长的比值，然后加上起始端点在顶点数组中的下标)以及交点在裁剪多边形顶点列表中的位置index1；将所述交点实例加入交点数组；

相交节点对列表遍历结束后使用结果列表内容作为相交节点对列表；

(3)重复步骤(2)一直到两棵二叉树都遍历完，即相交节点对列表中都是叶子节点，则寻找交点过程结束，获得交点列表(包围盒二叉树从顶到底各层的节点包含顶点个数逐渐减少，而叶子节点包含了多边形边的具体信息，只有两个节点都是叶子节点，才能进行多边形边是否相交的判断。因此，两棵二叉树都遍历到最底层的叶子节点时，才能获得交点列表；交点列表可以以数组、链表、队列等不同数据结构保存)。

通过采用以上技术方案，从而在遍历时不需要回溯操作，遍历速度快，可以大大的提高寻找交点的效率。

优选的，采用不同数据结构表示顶点和交点，并分别保存为数组；然后根据顶点数组和交点数组建立一个顶点虚拟列表。

优选的，通过以下方法建立顶点虚拟列表：

假设交点数组(即交点列表的一种数据结构保存方式)为{ins

迭代{ind

通过采用以上技术方案，该方法设计了一种简洁数据结构，并以此建立了多边形顶点的虚拟列表，在建立虚拟列表时记录交点在顶点列表中应该放置的位置，而不是直接将交点插入顶点列表，从而避免了插入时查询、移动需要的大量操作，在多边形顶点个数较大时能明显提高遍历速度，进而提升了多边形裁剪的效率。

获得交点列表之后，为了得到裁剪后的结果，需要按照一定顺序遍历两个多边形的顶点，并根据交点选择相应的顶点作为结果多边形的顶点。

优选的，所述的根据交点方向遍历所述的顶点虚拟列表，得到裁剪结果多边形，包括：

1)初始化结果多边形顶点列表为空(因为裁剪结果可能包含多个多边形，所以下文中结果多边形顶点列表都是指裁剪结果中当前多边形的顶点列表)；查看交点列表，若当前交点为入点并且未使用(即该交点没有被用于确定多边形顶点的遍历)，则将该交点作为当前结果多边形的第一顶点v；如果未能找到入点，则裁剪过程完成；

2)将所述的第一顶点v作为起始点，并将紧邻其后的一个交点，即出点作为结束点，将它们标记为已使用；根据起始点和结束点在实体多边形顶点列表中的位置index0(起始点和结束点的index0记录了它们在实体多边形顶点中的位置)，计算出起始点之后第一个顶点以及结束点之前第一个顶点的下标(index0记录了交点在实体多边形顶点列表中的位置，前述方法中描述了其计算方法：先得到交点到起始端点的距离与边长的比值，然后加上起始端点在顶点数组中的下标。起始端点在顶点数组中的下标是一个整数，而比值是一个取值[0,1]之间的小数。交点总是位于实体多边形的一条边上，而交点在实体多边形顶点列表中的位置肯定处于该条边起始点和结束点之间。所以这里起始交点之后第一个顶点的下标总是等于index0向上取整(即取比index0大的整数值)，而结束交点之前第一个顶点的下标总是等于index0向下取整(即取比index0小的整数值))；将起始点加入结果多边形顶点列表，然后复制实体多边形中对应的两点之间的所有顶点到结果多边形顶点列表；

3)选择所述出点作为起始点，根据next_intersection的记录，将裁剪多边形中紧邻其后的交点，即入点作为结束点，将它们标记为已处理；根据起始点和结束点的index1(起始点和结束点的index1记录了它们在裁剪多边形顶点中的位置)计算出起始点之后第一个顶点以及结束点之前第一个顶点的下标；将该起始点加入结果多边形顶点列表，然后复制裁剪多边形中对应的两点之间的所有顶点到结果多边形顶点列表；

重复步骤2)至步骤3)，直到回到第一顶点v，这时裁剪结果中当前多边形形成封闭，即产生了一个完整多边形，转到步骤1)。

现有的多边形裁剪算法中大部分都是寻找实体、裁剪多边形边的交点，然后将交点插入到多边形顶点数组或者链表中，最后根据交点的方向(出点、入点)在实体和裁剪多边形顶点数组中不断切换，提取对应的顶点形成结果多边形。但是交点插入顶点数组时需要时间寻找插入位置以及移动数据，在交点个数较大时这个时间开销不容忽视。为了提高算法速度，更快的获得裁剪结果多边形，采用本申请的上述技术方案，没有直接将交点插入多边形顶点数组中，而是建立顶点虚拟列表，即利用交点的index0、index1、next_intersection属性将交点和多边形顶点数组联系起来。这里遍历顶点虚拟列表的方法是由顶点虚拟列表的数据结构决定的，别的方法并不适用顶点虚拟列表。也就是说，建立顶点虚拟列表和遍历顶点虚拟列表是一个整体，目的都是为了避免交点插入多边形顶点数组的时间开销。

第二方面，本申请提供一种电子设备，采用如下的技术方案：

一种电子设备，包括存储器和处理器，所述存储器上存储有能够被处理器加载并执行如前述任一种方法的计算机程序。

第三方面，本申请提供一种计算机可读存储介质，采用如下的技术方案：

一种计算机可读存储介质，存储有能够被处理器加载并执行如前述任一种方法的计算机程序。

综上所述，本申请包括以下至少一种有益技术效果：

1.本申请通过分别建立实体多边形和裁剪多边形的顶点包围盒二叉树，获得实体树和裁剪树；然后分别遍历两棵二叉树，每层分别将实体树的节点与裁剪树的节点进行相交判断，寻找交点；然后对有相交节点的子树继续进行遍历，直至结束，也就是说，在遍历包围盒二叉树寻找交点时，只有相交节点的子节点才需要进一步进行相交判断，这样能够减少对边相交判断的次数，大大提高了寻找交点的效率。

2.通过采用本申请中的顶点虚拟列表的建立方法，该方法设计了一种简洁数据结构，并以此建立了多边形顶点的虚拟列表，在建立虚拟列表时记录交点在顶点列表中应该放置的位置，而不是直接将交点插入顶点列表，从而避免了插入时查询、移动需要的大量操作，在多边形顶点个数较大时能明显提高遍历速度，进而提升了多边形裁剪的效率。

3.本申请提出了一种新的包围盒求解方法，使用该方法不仅能快速求解任意个数点的包围盒，而且能以固定时间合并两个包围盒形成包含两个包围盒所有点的新包围盒，为构造包围盒树提供了一种高效的方法，也就是说，本申请提出的包围盒求解方法不仅具有线性时间复杂度，而且合并两个包围盒时具有常量时间复杂度，从而进一步提高了多边形裁剪时寻找交点的速度，进而提高了获得裁剪多边形的速度。

附图说明

图1是本申请的一种实施例的方法流程图。

图2是本申请的一种实施例中近似最小旋转矩形示意图。

图3是本申请的一种实施例中合并旋转矩形的示意图。

图4是遍历二叉树寻找交点的示意图；图中，实心圆点表示遍历时经过的节点。

图5是多边形裁剪示例中的实体多边形和裁剪多边形示意图。

图6是多边形裁剪示例中建立的顶点虚拟列表示意图。

图7是多边形裁剪示例中裁剪结果顶点列表示意图。

具体实施方式

以下结合附图1-7对本申请作进一步详细说明。

本申请实施例公开一种基于包围盒树的多边形裁剪方法。参照图1，一种基于包围盒树的多边形裁剪方法，包括以下步骤：

S1，分别建立实体多边形和裁剪多边形的顶点包围盒二叉树，获得实体树和裁剪树；其中，所述实体树和裁剪树的每个节点都是一个包含部分顶点的包围盒；

S2,(可从根节点开始)分别遍历两棵二叉树，每层分别将实体树的节点与裁剪树的节点进行相交判断，寻找交点；然后对有相交节点的子树继续进行遍历，直至结束；

S3，根据实体多边形顶点、裁剪多边形顶点和遍历获得的交点，建立顶点虚拟列表；

S4，(可根据交点方向)遍历所述的顶点虚拟列表，得到裁剪结果多边形。

可选的，步骤S1中建立实体多边形和裁剪多边形的顶点包围盒二叉树时，采用自底向上的方法，先将顶点按照预设参数分组(相邻的多个顶点为一组)，每组求解它们的包围盒；然后将相邻的包围盒两两合并，一直到只剩下一个包围盒，则包围盒树构建完成。

建立实体多边形和裁剪多边形的顶点包围盒二叉树时，也可以采用自顶向下的方法，先求解包含所有顶点的包围盒，然后不断将其划分为更小的多个包围盒，一直到包围盒包含的顶点个数小于预设参数。

可选的，所述的自底向上的方法，具体通过以下方法建立实体多边形或裁剪多边形的顶点包围盒二叉树：

遍历实体多边形或裁剪多边形的所有顶点{p

其中，二维平面上的一个具有顶点序列{p

遍历包围盒序列

重复上一步骤，直至合并得到最后一个包围盒

可选的，通过以下方法计算二维平面上一组点的包围盒：假定需要计算N个顶点的包围盒，将起点和终点形成的向量

具体实施时，还可以通过以下方法计算二维平面上一组点的包围盒：求所有点中的最小和最大横纵坐标；由最小横纵坐标和最大横纵坐标构成一个轴对齐矩形，即得到一个包围盒；或者通过求取最小旋转矩形得到包围盒。

可选的，可以通过以下方法计算父节点包围盒：如果包围盒是轴对齐矩形，则父节点包围盒通过求解左右子节点两个包围盒的外接矩形得到；如果包围盒是通过最小旋转矩形计算获得的，则父节点最小旋转矩形(无法直接由子节点最小旋转矩形精确求解)通过遍历两个子节点包含的所有顶点精确求解。

可选的，包围盒二叉树的父节点包围盒还可以通过以下方法计算获得：

如图3所示，将左子节点包含顶点的起点和右子节点包含顶点的终点形成的向量的方向作为父节点的主方向；

将坐标系进行旋转使得横坐标OX与主方向平行(从而将计算近似最小旋转矩形转化为求取轴对齐矩形问题)；

计算包含左右子节点近似最小旋转矩形所有边界顶点的轴对齐矩形；

对所述轴对齐矩形的四个边界顶点进行反向旋转，即计算顶点在原始坐标系下的坐标，从而得到父节点的近似最小旋转矩形，即获得包围盒二叉树的父节点包围盒；

其中，如图2所示，所述的左右子节点的近似最小旋转矩形通过以下方式获得：

假定需要计算N个顶点的包围盒，将起点和终点形成的向量

求轴对齐矩形，然后对其四个边界顶点进行反向旋转，即计算顶点在原始坐标系下的坐标，从而得到近似最小旋转矩形，即N个顶点的包围盒。

可选的，分别遍历两棵二叉树时，对两个二叉树进行广度优先遍历，沿着深度方向进行碰撞检测；如图4所示，每层分别将实体树的节点与裁剪树的节点进行相交判断时，交点由叶子节点包含的线段与线段之间进行相交判断得到。

可选的，通过以下方法寻找交点：

(1)初始化交点数组为空；从实体多边形和裁剪多边形对应二叉树的根节点开始进行碰撞检测；如果两者不相交(说明实体多边形和裁剪多边形不存在交点)，则寻找交点过程结束；否则，记录相交的节点对(由实体树的根节点和裁剪树的根节点构成)形成相交节点对列表，转入步骤(2)；

(2)初始化一个空列表作为结果列表，遍历相交节点对列表，对每个相交节点对进行如下处理：

a)如果相交节点对中两个节点都是叶子节点，则转入步骤b)；否则将叶子节点以及非叶子节点的子节点作为候选节点，分别使用实体二叉树的候选节点和裁剪二叉树的候选节点进行碰撞检测，将检测到的相交节点对加入结果列表；

b)对实体二叉树叶子节点和裁剪二叉树叶子节点所包含的多边形边分别进行相交检测(二叉树叶子节点包含多边形的Q个(最后一个叶子节点可能包含少于Q个)顶点，也就是说Q-1条边(相邻两个顶点的连线称作一条边)；假设实体多边形叶子节点包含p条边，裁剪多边形叶子节点包含q条边，那么将进行p×q次相交比较)，如果没有任何交点，则该相交节点对处理结束；否则，对检测到的每个交点执行步骤c)；

c)新建一个交点数据结构的实例(即创建一个存储交点数据的变量，变量的子成员x、y分别记录了交点的坐标。子成员index0记录了交点在实体多边形顶点列表中的位置；子成员index1记录了交点在裁剪多边形顶点列表中的位置)，用x，y记录交点的坐标；如果实体多边形的边进入了裁剪多边形，则置entry_exit为true，否则置为false；计算交点在实体多边形顶点列表中的位置index0(即先得到交点到起始端点的距离与边长的比值，然后加上起始端点在顶点数组中的下标)以及交点在裁剪多边形顶点列表中的位置index1；将所述交点实例加入交点数组；

相交节点对列表遍历结束后使用结果列表内容作为相交节点对列表；

(3)重复步骤(2)一直到两棵二叉树都遍历完，即相交节点对列表中都是叶子节点，则寻找交点过程结束，获得交点列表(包围盒二叉树从顶到底各层的节点包含顶点个数逐渐减少，而叶子节点包含了多边形边的具体信息，只有两个节点都是叶子节点，才能进行多边形边是否相交的判断。因此，两棵二叉树都遍历到最底层的叶子节点时，才能获得交点列表；交点列表可以以数组、链表、队列等不同数据结构保存)。

具体实施时，遍历两棵二叉树时也可采用深度优先的遍历方法。

可选的，采用不同数据结构表示顶点和交点，并分别保存为数组；然后根据顶点数组和交点数组建立一个顶点虚拟列表。

可选的，通过以下方法建立顶点虚拟列表：

假设交点数组(即交点列表的一种数据结构保存方式)为{ins

迭代{ind

顶点虚拟列表由交点数组、实体多边形顶点数组、裁剪多边形顶点数组三个部分组成。其中实体、裁剪多边形顶点数组顺序保存了多边形原始顶点的坐标x、y。而交点数组的每个元素是一个交点数据结构的实例，除了保存坐标x、y，还有entry_exit、index0、index1、next_intersection。后面这四个值确定了交点在实体/裁剪多边形顶点列表中的位置。建立顶点虚拟列表就是计算出每个交点的这四个值，从而将交点数组和实体多边形数组、裁剪多边形数组联系起来。

如图6所示，建立顶点虚拟列表本质就是建立交点数组和实体、裁剪多边形顶点数组之间的联系。这是通过计算交点的entry_exit、index0、index1、next_intersection属性实现的。前三个值在前面寻找交点过程中已经得到，这里只需要计算next_intersection。排序是为了得到交点在裁剪多边形顶点列表中的顺序。迭代步骤中根据上述顺序寻找在裁剪多边形顶点列表中紧邻当前交点的那个交点。

例如，假设交点数组有3个交点{ins1,ins2,ins3}，排序后交点顺序为{ins2,ins1,ins3}，那么下标序列为{2,1,3}。

迭代时ins2.next_intersection＝1，

ins1.next_intersection＝3,

ins3.next_intersection＝2。

上述方法中，顶点和交点还可采用队列、链表等方式存储。比如现有技术中，顶点列表以链表形式保存，交点插入顶点列表时需要遍历链表，在多边形顶点个数较大时将是不可忽略的时间开销。本申请通过上述方法，在建立虚拟列表时记录交点在顶点列表中应该放置的位置，而不是直接将交点插入顶点列表，从而避免了插入时查询、移动需要的大量操作，提升了多边形裁剪的效率。

可选的，所述的根据交点方向遍历所述的顶点列表，得到裁剪结果多边形，包括：

1)初始化结果多边形顶点列表为空(因为裁剪结果可能包含多个多边形，所以下文中结果多边形顶点列表都是指裁剪结果中当前多边形的顶点列表)；查看交点列表，若当前交点为入点并且未使用(即该交点没有被用于确定多边形顶点的遍历)，则将该交点作为当前结果多边形的第一顶点v；如果未能找到入点，则裁剪过程完成；

2)将所述的第一顶点v作为起始点，并将紧邻其后的一个交点，即出点作为结束点，将它们标记为已使用；根据起始点和结束点在实体多边形顶点列表中的位置index0(起始点和结束点的index0记录了它们在实体多边形顶点中的位置)，计算出起始点之后第一个顶点以及结束点之前第一个顶点的下标(index0记录了交点在实体多边形顶点列表中的位置，前述方法中描述了其计算方法：先得到交点到起始端点的距离与边长的比值，然后加上起始端点在顶点数组中的下标。起始端点在顶点数组中的下标是一个整数，而比值是一个取值[0,1]之间的小数。交点总是位于实体多边形的一条边上，而交点在实体多边形顶点列表中的位置肯定处于该条边起始点和结束点之间。所以这里起始交点之后第一个顶点的下标总是等于index0向上取整(即取比index0大的整数值)，而结束交点之前第一个顶点的下标总是等于index0向下取整(即取比index0小的整数值))；将起始点加入结果多边形顶点列表，然后复制实体多边形中对应的两点之间的所有顶点到结果多边形顶点列表；

3)选择所述出点作为起始点，根据next_intersection的记录，将裁剪多边形中紧邻其后的交点，即入点作为结束点，将它们标记为已处理；根据起始点和结束点的index1(起始点和结束点的index1记录了它们在裁剪多边形顶点中的位置)计算出起始点之后第一个顶点以及结束点之前第一个顶点的下标；将该起始点加入结果多边形顶点列表，然后复制裁剪多边形中对应的两点之间的所有顶点到结果多边形顶点列表；

重复步骤2)至步骤3)，直到回到第一顶点v，这时裁剪结果中当前多边形形成封闭，即产生了一个完整多边形，转到步骤1)。

如图5-图7为一个实体多边形和裁剪多边形进行裁剪的例子，图6是裁剪时建立的顶点虚拟列表，其中en表示该交点是入点，ex表示是出点，index0、index1箭头指向该交点在多边形顶点列表中的位置。

如图7所示，多边形裁剪结果由交点决定，交点数组中包含的交点分为入点和出点两类，而且入点和出点成对出现，也就是说交点数组中相邻两点必然包含入点和出点。

步骤1)检查交点数组中是否有未使用的入点，如果所有入点都已使用，则意味着整个裁剪过程完成。否则，将找到的入点作为当前结果多边形的第一顶点。

步骤2)实际上就是遍历实体多边形顶点。遍历的是当前入点和紧邻其后的出点之间的实体多边形的顶点。

步骤3)则是遍历裁剪多边形顶点，遍历的是前述出点和紧邻其后(next_intersection记录了当前交点后面的交点位置)的入点之间的裁剪多边形的顶点。

重复步骤2)至步骤3)，不断在实体多边形和裁剪多边形之间切换，直到当前交点又是第一顶点，这时得到了一个封闭的结果多边形。

本申请还公开了一种电子设备。一种电子设备，包括存储器和处理器，所述存储器上存储有能够被处理器加载并执行如上述任一种方法的计算机程序。

本申请还公开了一种计算机可读存储介质。一种计算机可读存储介质，存储有能够被处理器加载并执行如上述任一种方法的计算机程序。

本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。

以上均为本申请的较佳实施例，并非依此限制本申请的保护范围，故：凡依本申请的结构、形状、原理所做的等效变化，均应涵盖于本申请的保护范围之内。

另外，本申请的方法已经通过编程实现，并在一台具有i3770 CPU，8G内存的计算机上与Vatti、Greiner及Martinez算法进行比较，具体结果如表1：

表1不同方法运行时间比较

注：表中后三列表示运行时间(单位为毫秒)。

从表1中可以看出，在前面三个测试数据上本申请的方法具有最小运行时间，只有第四个测试数据上比Greiner算法运行时间长，但两者时间很接近。本申请的方法构造包围盒树需要一定时间，当顶点和交点个数很少时，这个时间和暴力寻找交点时间相比具有显著意义，可能使得时间比其它算法长，但是当顶点和交点个数很多时，本申请的获得裁剪多边形的运行时间就会大大缩短。