一种基于多核架构的计算凸壳的并行算法

摘要

本发明针对上述现有凸壳算法存在的不足，提供了一种基于多核架构的计算凸壳的并行算法，包括以下步骤：（1）找到初始点集合的初始不完全凸壳，其各边用逆时针方向的有向边表示；（2）根据初始不完全凸壳对点集合进行分类，找出各条有向边的所有外点；（3）迭代地并行地生长初始不完全凸壳中的每一条有向边；（4）删除最终所得凸壳上的非凸壳顶点。本发明有效地对原算法进行了优化从而充分节省了运算资源。并对原算法中点集分类过程和迭代过程进行了并行扩展，充分利用了多核处理器的并行计算资源；更进一步通过并行、串行的自适应选择来控制并行任务粒度以控制并行加速比，并消除了可能产生的瓶颈。

说明书

 

技术领域

    本发明涉及计算几何领域，尤其是涉及一种基于多核架构的计算凸壳的并行算法。

背景技术

凸壳是计算几何中最普遍、最基本的一种结构，在计算几何中占有重要的位置。凸壳不仅有许多特性，而且还是构造其他几何形体的有效工具。凸壳也称最小凸包，是包含集合S中所有对象的最小凸集。其中，平面点集凸壳是最重要、最基础的问题，平面线段集合和平面多边形集合的凸壳问题可以转换为平面点集的凸壳问题。平面点集的凸壳问题在计算机图形学、图像处理与模式识别、地理信息系统等众多领域中应用广泛。

求解平面点集的凸壳即是要求得点集的最小凸集，凸壳的边界是一个凸多边形。关于计算凸壳的串行算法，国内外的早期研究成果中主要有卷包裹法、格雷厄姆算法、分治算法、增量算法、实时算法、快速算法等。随着并行计算技术的不断发展，国内外的许多研究人员尝试将并行技术应用到凸壳的计算中。这些并行算法中，绝大多数使用了分治策略，即将原问题分解为若干子问题，并行独立求解这些子问题，然后合并所有子问题的解得到原问题的解。目前，这些并行算法还存在两个主要问题。第一，并行粒度不受控制，负载平衡问题考虑不足，有可能出现瓶颈；第二，为实现并行计算引入了大量额外计算任务，如对原问题进行分解时，通常要对初始点集合进行排序等。

以周培德提出的用分治法求解平面点集凸壳的Z_3-2算法为例，其基本思想是先求出点集中x、y坐标最大值、最小值，然后顺序连接最大值、最小值所对应的点成四边形，该四边形划分点集为5个子集，不考虑位于四边形内的子集，对其他4个子集迭代地删除不是凸壳顶点的点。该算法中首先判断点位于有向线段的哪一侧（即正负划分），再使用欧氏距离找出离有向线段最远的点，算法繁琐，占用了大量的计算资源。

发明内容

本发明针对上述现有凸壳算法存在的不足，在传统的平面凸壳算法的基础上，根据平面凸壳的实时性和海量数据的计算的实际应用要求，提出了一种在多核架构下计算平面点集凸壳的并行算法，提供了一种基于多核架构的计算凸壳的并行算法，摒弃了计算欧氏距离时的除法和开方运算，并将整个计算过程分解成若干相互独立的子任务，尽可能充分利用多核处理器的并行计算资源，提高了算法的执行效率。

本发明在找到点集在x方向、y方向上的极值点之后，得到一个初始不完全凸壳。对点集中的所有的点按照其在这个初始不完全凸壳的各条有向边的外侧进行分类，使得每条有向边都包含其所有外点的数据，同时，删除了在这个初始不完全凸壳内部的所有点。并行地迭代生长所有有向边，并在迭代过程中根据阈值条件继续分解任务粒度较大的生长任务，进行串行和并行运算的智能选择，不断地向初始不完全凸壳中的指定位置插入新的凸壳点，生成新的有向边，并根据新生成的有向边对原有向边外点集合中的点进行分类，如此迭代，直到所有有向边的外点集合均为空。最后还要删除所有凸壳多边形中的非凸点，这些点在该多边形的边上，而不是其顶点。

为了达到上述目的，本发明提供如下技术方案：

一种基于多核架构的计算凸壳的并行算法，包括以下步骤：

（1）    找到初始点集合的初始不完全凸壳，其各边用逆时针方向的有向边表示；

（2）    根据初始不完全凸壳对点集合进行分类，找出各条有向边的所有外点；

（3）    迭代地并行地生长初始不完全凸壳中的每一条有向边；

（4）    删除最终所得凸壳上的非凸壳顶点。

作为一种优选方案，所述步骤（1）的实现方法是：找到沿x坐标、y坐标方向的四个极值点，删除这四个点中相同的点，剩余的点按逆时针方向围成的凸多边形即为初始不完全凸壳，记为LPBCH(S)。

作为一种优选方案，所述步骤（2）的实现方法是：定义行列式                                                               的值为点P(x, y)到向量P₁P₂（P₁(x₁, y₁)、P₂(x₂, y₂)）的颜氏距离，将与初始不完全凸壳的各条有向边的颜氏距离大于0的所有点加入到该有向边的外点集合中，删除点集合中那些不在任何一条有向边右侧的点。

作为一种优选方案，所述步骤（3）的实现方法是：对于不完全凸壳边链中的每一条有向边P_iP_i+1并行地进行迭代生长，所述迭代生长的过程为：

（a）    若有向边P_iP_i+1的外点集合为空，则返回空点列；

（b）    从有向边P_iP_i+1的外点集合中找出到该有向边的颜氏距离最大的点P，该点P必为点集的凸壳点；

（c）    连接点P_i和点P，点P和点P_i+1，生成两条新的有向边P_iP和PP_i+1，对原有向边P_iP_i+1的外点集合按有向边P_iP和PP_i+1重新分类，分别得到有向边P_iP和有向边PP_i+1各自的外点集合；

（d）    若有向边P_iP_i+1的外点集合中点的数量不大于MAXGROW的2倍，则转步骤（f）；

（e）    并行地迭代生长有向边P_iP和PP_i+1分别得到点列L₁和L₂，令点列L={P_i}∪L₁∪{P}∪L₂∪{P_i+1}，转步骤（j）；

（f）    定义链表E来存储若干有向边，将P_iP和PP_i+1插入E；

（g）    对于E中的每条有向边e，若其外点集合不为空，则按照（b）（c）两步的方法得到两条新的有向边e₁和e₂，以及 e₁和e₂的外点集合；从E中删除e，并在原来e的位置插入e₁和e₂，其中e₁与e的起点相同；

（h）    若（g）中任意一条新生成的有向边的外点集合不为空，则转步骤（g）；

（i）    删除E中第一条有向边，并令L为由E中各有向边的起点排列而成的点列；

（j）    将点列L作为结果返回；

其中，（d）中的MAXGROW是进行并行、串行选择的阈值。

作为一种优选方案，步骤（4）的实现方法是：依次遍历步骤(3)得到的凸多边形的每一点，设P为当前遍历点，R为P的前驱（即按逆时针方向排列的上一点），Q为P的后继（即按逆时针方向排列的下一点）；如果R、P、Q三点共线，就从LPBCH(S)中删除点P；经过对LPBCH(S)的一次遍历，删除所有非凸壳顶点的点，就能得到点集的凸壳顶点序列，由这些顶点围成凸多边形就构成了点集的凸壳。

本发明用颜氏距离来判断点与有向线段的位置关系，摒弃了原Z_3-2算法中计算欧氏距离时的采用的除法和开方运算，降低了运算复杂度，有效地对原算法进行了优化从而充分节省了运算资源。其次，对原算法中点集分类过程和迭代过程进行了并行扩展，将耗时较多的任务分解为若干可以并行执行的子任务，去除了子任务之间的耦合性使得各并行子任务之间相互独立执行，充分地利用了多核处理器的并行计算资源；此外，任务分解的过程可以在O(1)的时间复杂度内完成，并行开销小。最后，通过并行、串行的自适应选择来控制并行任务粒度以控制并行加速比，并消除了可能产生的瓶颈，在平面点集凸壳的实时求解和海量数据求解中，发挥比简单串行计算或耦合性较高的并行计算更突出的作用。

附图说明

图1为本发明提供的基于多核架构的计算凸壳的并行算法流程示意图；

图2为算法求解效果图；

图3为原Z_3-2算法，优化后的Z_3-2算法和本发明采用的并行算法执行时间对比图；

图4为本发明采用的算法加速比示意图。

具体实施方式

以下将结合具体实施例对本发明提供的技术方案进行详细说明，应理解下述具体实施方式仅用于说明本发明而不用于限制本发明的范围。

基于多核架构的计算凸壳的并行算法流程如图1所示，具体过程描述如下：

（1）    首先找到初始点集合的初始不完全凸壳，其各边用逆时针方向的有向边表示：找到沿x坐标、y坐标方向的四个极值点，删除这四个点中相同的点，剩余的点按逆时针方向围成的凸多边形即为初始不完全凸壳，记为LPBCH(S)。

LPBCH(S)包括NCP(S)和NCE(S)；将不完全凸壳中的顶点列记为NCP(S)，各顶点用P_i (x_i, y_i)表示，其中1≤i≤n，i为整数，n为点集中的点数，因此NCP(S)中有n个顶点。将每两个顶点间形成的逆时针方向的有向边链记为NCE(S)，各有向边用P_iP_i+1（P_i(x_i, y_i)、P _i+1 (x _i+1, y_i+1)）来表示；其中1≤i≤n，i为整数，n为点集中的点数；当i=n时，P_i+1=P_n+1=P₁，因此NCE(S)中也有n个元素，其中第n条有向边为P_nP_n+1，即P_nP₁，n条有向边围成一个封闭凸多边形。

（2）    对点集合中的所有点按照其在步骤(1)中找到的初始不完全凸壳的哪条有向边的右侧进行分类，找出各条有向边的所有外点：

点集合中的点用P(x, y)来表示，初始不完全凸壳中的有向边用向量P₁P₂（P₁(x₁, y₁)、P₂(x₂, y₂)）来表示；

定义行列式                   的值为点P(x, y)到向量P₁P₂（P₁(x₁, y₁)、P₂(x₂, y₂)）的颜氏距离，记为YD(P,P₁P₂)。对点集合中的所有点按照其是否在步骤(1)中找到的初始不完全凸壳的各条有向边的右侧进行分类，其中，到该有向边的颜氏距离大于0的点在该有向边的右侧。将有向边右侧的所有点加入到该有向边的外点集合中。删除点集合中所有不在任何一条有向边右侧的点，因为它们在初始不完全凸壳的内部，一定不是最终凸壳上的点。

（3）    对于不完全凸壳边链中的每一条有向边P_iP_i+1并行地进行迭代生长。迭代生长的过程为：

（a）        若有向边P_iP_i+1的外点集合为空，则返回空点列；

（b）        从有向边P_iP_i+1的外点集合中找出到该有向边的颜氏距离最大的点P，该点P必为点集的凸壳点；

（c）        连接点P_i和点P，点P和点P_i+1，生成两条新的有向边P_iP和PP_i+1，对原有向边P_iP_i+1的外点集合按有向边P_iP和PP_i+1重新分类，分别得到有向边P_iP和有向边PP_i+1各自的外点集合；

（d）        若有向边P_iP_i+1的外点集合中点的数量不大于MAXGROW的2倍，则转步骤（f）；

（e）        并行地迭代生长有向边P_iP和PP_i+1分别得到点列L₁和L₂，令点列L={P_i}∪L₁∪{P}∪L₂∪{P_i+1}，转步骤（j）；

（f）        定义链表E来存储若干有向边，将P_iP和PP_i+1插入E；

（g）        对于E中的每条有向边e，若其外点集合不为空，则按照（b）（c）两步的方法得到两条新的有向边e₁和e₂，以及 e₁和e₂的外点集合；从E中删除e，并在原来e的位置插入e₁和e₂，其中e₁与e的起点相同；

（h）        若（g）中任意一条新生成的有向边的外点集合不为空，则转步骤（g）；

（i）        删除E中第一条有向边，并令L为由E中各有向边的起点排列而成的点列；

（j）        将点列L作为结果返回。

其中，（d）中的MAXGROW是进行并行、串行选择的阈值，只有在待生长的有向边的外点数量足够多时，才选择并行算法。随着迭代的深入，外点的数量不断减少，当外点数量降至阈值的两倍以下时，并行算法将不再具有优越性，此时将选择串行策略来结束迭代，并在有限次循环内得出结果。该步骤通过并行、串行的自适应选择来控制并行任务粒度以控制并行加速比，并消除了可能产生的瓶颈。

（4）    依次遍历步骤(3)得到的凸多边形中的每一点，设P为当前遍历点，R为P的前驱（即按逆时针方向排列的上一点），Q为P的后继（即按逆时针方向排列的下一点）。如果R、P、Q三点共线，就从LPBCH(S)中删除点P。经过对LPBCH(S)的一次遍历，删除所有非凸壳顶点的点，就能得到点集的凸壳顶点序列，由这些顶点围成凸多边形就构成了点集的凸壳。

利用本发明提供的凸壳并行算法进行融合试验，融合实验采用的是代表我国某省的气象采样点数据，如图2所示，密集点集为气象数据的采样分布，这一分布为该区域内所有降水的站点。图2中的多边形区域为利用本发明提供的的并行算法求得的该点集的凸壳。

如图3所示，将本发明采用的算法与原Z_3-2算法的执行效率进行了对比分析。为进一步测试本发明算法的并行性能，本发明对原Z_3-2算法进行了优化使其与本发明算法具有可比性。对原Z_3-2算法的优化方式为：与本发明算法类似，用颜氏距离代替了欧式距离，用栈结构消除了原Z_3-2算法中的递归，使得优化的Z_3-2算法与本算法串行执行时的性能接近。图3为本发明采用的算法、原Z_3-2算法与优化的Z_3-2算法的执行时间对比图，以区分优化和并行运算分别产生的性能提升。

由图3可知：本发明算法对10⁶数量级的点集的凸壳的求解时间接近200毫秒，充分说明了本算法的高效性；优化后，算法的性能有较大的提高；通过并行计算进一步减少了计算时间。当处理器数目更多时，算法执行时间更短。

图4为本发明算法改进和优化后的加速比，其中，优化加速比指优化前后算法的执行时间比，并行加速比指优化后算法与本发明算法的执行时间比，总加速比指原算法与本发明算法的执行时间比。实验得出算法的平均并行加速比在1.55左右，总体加速比在3.89左右。其中并行加速比在点数较大时收敛于2，这说明了算法的并行开销较小。从图4还可以看出随着运算点数的增加，并行加速比有较为稳定的趋势，而优化加速比抖动较大。这是因为算法的优化过程改变了算法的基本数据结构和执行流程，而并行化的过程不改变算法自身结构。由图4可知，本算法对原Z_3-2算法有较强的加速作用，从而大幅节约了运算资源，提升整体性能。

本发明方案所公开的技术手段不仅限于上述技术手段所公开的技术手段，还包括由以上技术特征任意组合所组成的技术方案。