一种基于道格拉斯-普克算法的图形拟合算法

摘要

本发明涉及图形处理领域，且公开了一种基于道格拉斯‑普克算法的图形拟合算法，包括以下步骤：第一步：通过画笔或者手指在移动端屏幕上绘制，采集触摸点；第二步：对采集到的点用道格拉斯‑普客算法进行简化或者采用最小二乘法，得到图形关键点，保留关键点，得到结果1；第三步：对结果1进行闭合点处理，得到结果2；第四步：对结果2进行类型判定；第五步：根据判定的类型，对结果2中的点集进行矫正，生成点集3；第六步：对点集3中的每个点按照顺序连接，生成拟合图形。

说明书

技术领域

本发明涉及图形处理领域，具体为一种基于道格拉斯-普克算法的图形拟合算法。

背景技术

随着移动端技术的发展，各种学习类的笔记软件层出不穷。用户更加倾向于在移动设备上记笔记、学习以及思考问题。很多时候，用户可能需要绘制一些数学图形，比如三角形、矩形、五角星、多边形、圆、椭圆等，去辅助思考或者是做一些特殊的图形标记。那么精准而又快速的绘制出图形就能大幅度减少额外的时间，提升效率。

现有技术方案：

S1：通过笔触摸移动端屏幕，进行点的采样。

S2：对相邻的两点之间进行连接，生成图形。

S3：将生成的线条实时绘制到屏幕上，从而达到绘制图形的效果。

上述方案在手动绘制图形时会因为手的抖动导致线条出现扭曲，现有技术对于绘制的图形并没有进行智能的矫正，导致绘制出的图形并不精准完美，影响用户分析问题，为此我们提出了一种基于道格拉斯-普克算法的图形拟合算法。

发明内容

(一)解决的技术问题

针对现有技术的不足，本发明提供了一种基于道格拉斯-普克算法的图形拟合算法，通过智能拟合出数学图形，解决了绘制图形时，因手工绘制时抖动，导致生成的图形观感欠佳的问题。

(二)技术方案

为实现上述所述目的，本发明提供如下技术方案：一种基于道格拉斯-普克算法的图形拟合算法，包括以下步骤：

第一步：通过画笔或者手指在移动端屏幕上绘制，采集触摸点；

第二步：对采集到的点用道格拉斯-普客算法进行简化或者采用最小二乘法，得到图形关键点，保留关键点，得到结果1；

第三步：对结果1进行闭合点处理，得到结果2；

第四步：对结果2进行类型判定；

第五步：根据判定的类型，对结果2中的点集进行矫正，生成点集3；

第六步：对点集3中的每个点按照顺序连接，生成拟合图形。

优选的，所述道格拉斯-普客算法需要使用一个比较线段长短的参数，阈值为ε，和一个比较夹角大小的参数，阈值a，阈值为自定义参数。

优选的，所述图形关键点的获取步骤如下：

S1：设置起点以及终点，A为起点，F为终点；

S2：求出各个触摸点距离直线AF的距离，取到直线AF距离最大的那个点，记为点B，点B到直线AF的距离为d(B,AF)，记AB，FB之间的夹角为∠ABF；

S3：如果d(B,AF)>ε，并且∠ABF

S4：对points1和points2重复step1和step2，依次迭代下去。

优选的，所述第三步中如果起点A与终点F距离很近，说明用户此时是想闭合图形的，设置一个参数len，如果D(A,F)>len,则保留F点，否则删除F点。

优选的，所述第四步的判定方法为：

S1：根据关键点数量，对相邻的三个关键点进行分组，且两两连接称为直线，得到不同的角；

S2：如果关键点只有三个点，可以直接判定为三角形；

S3：如果只有四个关键点，角接近90度，即在70度和110度之间，那么判定此图形为矩形；

S4：如果只有五个关键点，角都小于90度，说明用户意图是画一个五角星，如果五个角都是钝角，说明用户意图是画一个五边形；

S5：如果关键点的个数大于6，那么判定此图形为圆。

优选的，所述第五步中矫正方法如下：

S1：找到矩形框rect的中心点，记为center；

S2：然后计算关键点距离中心点center的平均值；

S3：以平均值为半径，center为中心的圆,即为图形的外切圆；

S4：各点分别采用作垂线的方式与外接圆相交，即为点集3。

(三)有益效果

与现有技术相比，本发明提供了一种基于道格拉斯-普克算法的图形拟合算法，具备以下有益效果：

1、该基于道格拉斯-普克算法的图形拟合算法，通过判定用户的绘制意图生成对应的拟合图形，生成的拟合图形支持圆、椭圆、三角形、矩形、五角星、多边形等等，为分析问题和工作带来了效率的提升。

附图说明

图1为本发明流程示意图；

图2为手动绘制图形示意图；

图3为手动绘制图形进行图形拟合后示意图；

图4为屏幕采样的点集示意图；

图5为直线AB的距离示意图；

图6为points2迭代执行step1和step2后的结果示意图；

图7为对结果1进行闭合点处理示意图；

图8为生成包围点集的最小矩形框rect示意图；

图9为五角星的外接圆示意图；

图10为手动绘制的矩形转化成标准矩形的案例示意图；

图11为手动绘制的圆转换成一个标准圆形的示例示意图；

图12为手动绘制的三角形转换成一个标准三角形的示例示意图；

图13为手动绘制的多边形转换成一个标准多边形的示例示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1-13，一种基于道格拉斯-普克算法的图形拟合算法，包括以下步骤：

第一步：通过画笔或者手指在移动端屏幕上绘制，采集触摸点；

第二步：对采集到的点用道格拉斯-普客算法进行简化，保留关键点，得到结果1；

第三步：对结果1进行闭合点处理，得到结果2；

第四步：对结果2进行类型判定；

第五步：根据判定的类型，对结果2中的点集进行矫正，生成点集3；

第六步：对点集3中的每个点按照顺序连接，生成拟合图形。

具体案例下：

图形拟合的过程，即是把手动绘制的类似于图2的图形拟合成类似于图3的图形。

图1是手动在移动端设备上绘制生成的图形，没有经过任何处理，直接对采样点进行顺序连接，生成图形。可以看到图2并不是一个标准意义上的五角星。

图3是对图2中的采样点进行特殊处理后，连接形成的标准五角星。

S1：手动绘制五角星的过程中，移动端设备会采样几十个点。需要对这些点使用道格拉斯-普克算法进行简化处理。下面简述道格拉斯-普克算法的处理过程。

假设用户绘制的过程中，屏幕采样的点集如图4所示(实际中点的数量可能更多)。绘制顺序为图4中标记的1到17。为了方便说明，标注了一些特殊的点：A、B、C、D、E、F。标注的这些点在简化之前并不知道，只是在算法处理的过程中才会出现。

算法需要使用一个比较线段长短的参数，阈值为ε；和一个比较夹角大小的参数，阈值a。阈值为自定义参数。

对于上述手动绘制的五角星图形，假设A为起点，F为终点。

step1：分别求出其余各点距离直线AF的距离，取到直线AF距离最大的那个点。在图3所有点集中，距离最大的为第4个点，记为点B，点B到直线AF的距离为d(B,AF)。记AB，FB之间的夹角为∠ABF。

step2：如果d(B,AF)>ε，并且∠ABFε，并且∠ABF

step3：对points1和points2重复step1和step2。依次迭代下去。

图3中，points1执行step1和step2的过程是，先连接首尾1-4(即直线AB)两点，然后比较2、3两点到直线AB的距离，都小于ε，删除2、3两点。结果如图5所示：

points2迭代执行step1和step2后的结果如图6所示。

图6和图5中的结果之和就是简化点集后的结果1。

S2：对结果1进行闭合点处理。

结果1中包含了A、B、C、D、E、F六个点。其中F点是最后用户手指或者电子笔离开屏幕前的最后一点。因为在手动绘制图形的过程中，一般都倾向于在绘制的终点接近于起点的时候离开屏幕。如果终点与起点的距离很近，说明用户此时是想闭合图形的。设置一个参数len，如果D(A,F)>len,则保留F点；否则删除F点。

那么对于结果1，执行此步骤后，删除了F点。结果1变成了结果2(A，B，C，D，E)。如图7所示。

S3：对结果2进行判定。

如图7所示，一共有5个点A，B，C，D，E。按照顺序取点形成∠ABC，∠BCD，∠CDE，∠DEF，∠EFA五个角。如果五个角都小于90度，说明用户意图是画一个五角星；如果五个角都是钝角，说明用户意图是画一个五边形。根据此步骤，结果2判定为五角星。

S4：对结果2中的点进行矫正。

图7中已经知道结果2每个点对应的位置。需要对其中部分点的位置进行矫正，得到标准的五角星。通过比较每个点的x坐标最小值和最大值，以及y坐标的最小值和最大值，可以生成一个包围该点集的最小矩形框rect。如图8所示。

S1：找到矩形框rect的中心点，记为center。

S2：然后计算点A、B、C、D、E距离中心点center的平均值，[D(A,center)+D(B,center)+D(C,center)+D(D,center)+D(E,center)]/5，记为averageD。

S3：以averageD为半径，center为中心的圆即是五角星的外接圆。如图9所示。

S4：先确定标准五角星中A1、H点的位置。需要根据原来的A、B两点来求得，因为原始的A、B两点决定了标准五角星的旋转角度。

向量center-A为(A.x-center.x,A.y-center.y)，向量center-A的长度len＝sqrt((A.x-center.x)^2+(A.y-center.y)^2),则向量center-A的单位向量unit_center_A＝center-A/len。那么A1点的坐标为，A1.x＝center.x+unit_center_A.x*averageD,A1.y＝center.y+unit_center_A.y*averageD。

向量AB的单位向量unit_AB同理可求。

再确定H点的坐标。五角星中A1H的长度记为A1H_length＝averageD*sin36/cos36。

则向量A1H＝A1H_length*unit_AB。由于A1坐标已求出，那么H坐标为(A1.x+A1H.x,A1.y+A1H.y)。其余各点同理可求。

参阅图10，显示的是手动绘制的矩形转化成标准矩形的案例。

首先采用道格拉斯-普克算法简化成A、B、C、D、E五个点，然后因为A点和E点距离很近，舍弃E点。此时剩下A、B、C、D四个点。

因为有四个点，首先需要判断四个点的顺序是否是顺时针或者是逆时针。设向量AB和BC的叉乘得到的向量为N1，向量BC和向量CD叉乘得到的向量为N2，如果向量N1和向量N2的方向相同，说明A、B、C、D是按照顺时针或者逆时针的顺序生成的。

假设角度误差容忍值为20度，∠ABC、∠BCD、∠CDA、∠DAB接近90度，即在70度和110度之间，那么判定此图形为矩形。

采用图8中的方式找到一个最小包围矩形以及其中心点。算出A、B、C、D各点到中心点的平均值作为矩形A1B1C1D1的外接圆半径。

接下来就是确定A1、B1、C1、D1各点。根据原始的A、B两点确定一条直线，此时直线AB与外接圆有两个交点A1、B1，那么只需要确定出该矩形中的两个点，其余各点分别采用作垂线的方式与外接圆相交就确定出了。

参阅图11，显示的是手动绘制的圆转换成一个标准圆形的示例。

首先采用道格拉斯-普克算法简化成A、B、C、D、E、F、G七个点。

判断七个点的顺序是否是顺时针或者是逆时针。方法同上。

如果点的个数大于6，那么判定此图形为圆。

采用图8中的方式找到一个最小包围矩形以及其中心点。此时需要区分是圆形还是椭圆。假设有个比较值为diff,如果最小包围矩形的长宽之差小于diff，说明用户意图是画一个圆形，否则是一个椭圆。

如果是圆，算出A、B、C、D、E、F、G各点到中心点的距离平均值作为半径，已知中心点和半径，那么圆就确定下来了。

如果是椭圆，算出A、B、C、D、E、F、G各点到中心点的向量，取向量长度最大者作为椭圆的长轴方向，垂直于长轴的方向为短轴的方向，短轴的长度为向量长度最小者。已知长轴、短轴以及中心点，那么椭圆就确定下来了。

图12显示的是手动绘制的三角形转换成一个标准三角形的示例。

首先采用道格拉斯-普克算法简化成A、B、C三个点。

因为只有三个点，可以直接判定为三角形。只需要按照顺序对三点依次连接即可。

参阅图13，显示的是手动绘制的多边形转换成一个标准多边形的示例。

首先采用道格拉斯-普克算法简化成A、B、C、D、E五个点。

判断五个点的顺序是否是顺时针或者是逆时针。方法同上。

假设判断角度误差值为20度，因为正五边形内角为108度，判断五个点之间形成的角是否在88度和128度之间。图13判定为多边形，即五边形。

依次连接A、B、C、D、E五个点即可形成该五边形。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。