本发明属于计算机制图的3d建模技术领域，主要是一种综合性的轮廓曲线偏置方法。
背景技术：
计算几何中，由已知平面曲线上点，沿其法线方向移动固定距离后所形成的曲线，称为偏置曲线。实际工程中，常将平面轮廓中多条曲线段进行偏置并连接组成新的轮廓，新的轮廓和原轮廓具有形似的特性，称该过程为轮廓曲线的偏置操作。因曲线偏置距离的异同，可分为等距偏置和非等距偏置。等距偏置时，新轮廓上的点到原轮廓的距离均相等。非等距偏置时，新轮廓每条边到原边的距离与另外一条边到原边的距离可能不同。
曲线的偏置作为基础功能，广泛应用于建筑设计、艺术形体设计、数控加工刀轨计算及3d打印等过程。偏置结果的正确性和稳定性，直接影响到设计和加工环节的质量。目前，国内外已有相关的研究成果，主要分为基于直骨架原理的多边形偏置、基于分段求交的曲线偏置和计算解析表达式的广义偏置三个方向。
张勇以stl的多向链表和优先队列数据结构为基础，设计了平面多边形直骨架计算的流程,方法结构简单清晰,通用性强(张勇.平面多边形直骨架及软件实现算法[j].,2012(04):165-166.)。罗恒提出一种基于直骨架的偏置算法，采用多边形单调链分解的方法提高了直骨架计算速度，通过标记偏置分裂、退化点,以堆栈数据结构提取偏置多边形顶点,提高了计算稳定性，解决了偏置算法中效率低、轮廓自相交和互相交等问题(罗恒等.快速成型中基于直骨架原理的轮廓偏置算法[j].,2011,23(11):1908-1914.)。基于直骨架原理的偏置算法，流程简单通用，计算稳定高效，但是仅仅只适用于多边形轮廓的偏置，不能处理曲线的情况。
赵乾胜设计出一种基于原始环的平面闭合曲线偏置算法，算法首先通过顶点偏置法将构成曲线的顶点进行偏置，然后根据偏置后两条正确线段之间错误线段的个数进行分情况处理，获得初步偏置曲线，然后去除无效的自相交环，再去除无效的互相交环，获得实际需要的偏置曲线(赵乾胜等.基于原始环的平面闭合曲线偏置算法[p].cn103257613a,2013-08-21.)。xu-zengliu提出针对直线段和圆弧的偏置算法，通过分段偏置、裁剪连接和自相交处理三个步骤来计算偏置结果(xu-zengliu(2007).anoffsetalgorithmforpolylinecurves.computersinindustry.58.240-254.)。以分段求交为基础的曲线偏置算法，往往难以判断偏置后各曲线段的有效性，为处理各种情况，算法流程异常复杂，容易导致最终计算结果不稳定。
陈雪娟从解析式的角度，定义了一种广义偏置曲线，该曲线保持偏置距离不变,只改变偏置方向。同时研究了广义偏置曲线的正则性、曲率和整体性质等，对推广偏置曲线具有重要的意义(陈雪娟.广义偏距曲线及其性质[j].,2005(03):308-310.)。但该方法目前仍处于理论研究阶段，尚未成熟应用于工程实际中。
由此可知，基于直骨架原理的偏置算法适用面窄，基于分段求交的曲线偏置算法复杂且稳定性差，对非等距偏置的研究甚少。轮廓曲线偏置是计算几何中的核心功能之一，曲线类型的多样性极大地增加等距、非等距偏置操作求解的复杂程度，需要一种高效稳定且普适性强的方法。
技术实现要素：
本发明的目的在于克服现有技术存在的不足，将骨架原理的简单高效性和分段求交偏置算法的普适性相结合，提出一种综合性的轮廓曲线偏置方法，用于计算三维建模中复杂轮廓曲线的偏置结果。本发明以直骨架原理为基础，推导出“曲骨架”，用以简单高效的计算轮廓曲线等距偏置的结果。另外，创新性的提出新的分段求交偏置算法思路，使其能够应用于非等距偏置问题的求解。
本发明的目的是通过如下技术方案来完成的。一种综合性的轮廓曲线偏置方法，将轮廓曲线按照等距偏置和非等距偏置分别进行处理，具体步骤如下：
1)、等距偏置处理：
(1)、计算等分线：将轮廓曲线中相邻的两曲线段间计算出一条等分线，遍历整个轮廓曲线，依次求出所有的等分线；
(2)、合成曲骨架：依次对相邻的等分线进行求交，得到有效的交点，在交点处裁剪等分线，并计算出新的等分线，新的等分线之间再依次求交，直至无新的等分线产生，最终合成出曲骨架；
(3)、求解偏置结果：对于给定偏置距离的等距偏置情况，分别将原始轮廓中的每段曲线进行偏置，得到偏置曲线；再将每段偏置曲线分别和曲骨架求交，用交点裁剪偏置曲线，依据交点的连接关系，提炼得到偏置结果；
2)、非等距偏置处理：
(1)、局部偏置：分别按照给定距离偏置直线段、圆弧段，得到局部偏置结果；
(2)、延长求交：延长局部偏置结果，直线段延长成无限长的直线，圆弧段延长成整圆；求出相邻的直线、整圆之间的交点，如果有交点，选择出有效的交点，如果无交点，则求出原有曲线段之间的最近点对；
(3)、裁剪拼接：用交点、最近点对来裁剪延长后的直线或整圆，依据原始轮廓曲线的顺序，依次连接形成新的轮廓曲线；
(4)、自相交处理：如果新的轮廓曲线存在自相交的情况，即轮廓曲线内部的曲线和曲线之间会相交；则先将新的轮廓曲线两两之间进行求交，并用交点打断；然后，沿着轮廓曲线的方向，搜索出新的闭环、开环；最后，检测闭环的绕组数量windingnumber,得到有效的偏置结果。
作为优选方案，相邻的曲线段类型包括直线段-直线段、直线段-圆弧段、圆弧段-圆弧段。
作为优选方案，所述的轮廓曲线包括封闭或不封闭的轮廓曲线。
作为更进一步的方案，在延长求交步骤中，如果有一个交点，则将该点作为有效的交点；如果有两个交点，则筛选出一个点作为有效的交点；其中筛选规则为：如果是直线和整圆求交的情况，以整圆中心、直线法向做出一条分割线，计算原轮廓曲线中直线段和圆弧段的交点在这条分割线的左侧还是右侧，以此选择同侧的交点；如果是整圆和整圆求交的情况，连接两个圆心做出一条分割线，计算原轮廓曲线中圆弧段和圆弧段的交点在这条分割线的左侧还是右侧，以此选择同侧的交点。
本发明的有益效果为：本发明可以应用于国内某大型在线家装设计平台的户型工具、全屋定制工具中，高效稳定的偏置结果将极大地提高了工具的易用性、使用效率等。明显受益点：
(1)基于曲骨架原理的等距偏置方法，流程简单，稳定性高；
(2)新的分段求交偏置方法，解决了以往不能处理非等距偏置、非闭合轮廓曲线偏置的情况，拓展了适用范围；
(3)目前支持的曲线类型为直线、圆弧，可方便的拓展至更复杂的曲线类型。
附图说明
图1为相邻的曲线段处于直线段-直线段情况下等分线的示意图；
图2为相邻的曲线段处于直线段-圆弧段相切情况下等分线的示意图；
图3为相邻的曲线段处于直线段-圆弧段不相切情况下等分线的示意图；
图4为相邻的曲线段处于圆弧段-圆弧段半径相等情况下等分线的示意图；
图5为相邻的曲线段处于圆弧段-圆弧段半径不相等情况下等分线的示意图；
图6为本发明等距偏置实例示意图；
图7为本发明局部偏置情况下的示意图；
图8为本发明自相交情况下的示意图；
图9为本发明去除自相交情况下的示意图；
图10为本发明不封闭的轮廓曲线偏置情况下的示意图；
图11为本发明非等距偏置实例示意图。
具体实施方式
下面结合附图对本发明的实施例进行详细的说明，本实施例是在以发明技术方案为前提下进行的，给出了详细的实施方式和具体的实现过程，但是本发明的保护范围不限于下述实施示例。
本发明提出的一种综合性的轮廓曲线偏置方法，适用于由平面直线段、圆弧段所组成的轮廓曲线，将等距偏置和非等距偏置分两种情况进行处理，具体步骤如下：
1)、等距偏置处理：实际工程应用中，对封闭的轮廓曲线进行等距偏置操作是比较常见的，其中关键点在于曲骨架的计算，骨架是一种形状特征，是对由一系列曲线段构成的原始形状的拓扑简化表示，骨架上不同位置处的曲线段和原始曲线之间具有形状近似性。由此，参考基于直骨架的多边形偏置算法，将直骨架推导出“曲骨架”，用于计算等距偏置。
(1)、计算等分线：将轮廓曲线中相邻的两曲线段间计算出一条等分线，依次求出所有的等分线；依据相邻的曲线段类型，分为三种情况进行计算：直线段-直线段、直线段-圆弧段、圆弧段-圆弧段。
<1>直线段-直线段
等分线即为两直线段之间的角平分线，也是直线，如图1所示，等分线b为直线段l1和l2之间的角平分线。
<2>直线段-圆弧段
如果直线段和圆弧段相切，则等分线的轨迹为直线，如图2所示。蓝色的直线段b为等分线，b上任意点到直线段l和圆弧段a的距离均相等。b的方向垂直于直线段l，且经过直线段l和圆弧段a之间的公共点v。
如果直线段和圆弧段不相切，则等分线的轨迹为抛物线，如图3所示。设圆弧段a的半径为r，圆心为o，圆心到直线l的距离为d。
对于图3(a)，抛物线轨迹的焦点为圆心o，焦距为f＝(d r)/2。
对于图3(b)，抛物线轨迹的焦点为圆心o，焦距为f＝|(d-r)|/2。
<3>圆弧段-圆弧段
圆弧段和圆弧段连接的时候，等分线的轨迹可能为直线、双曲线和椭圆。设圆弧段a1的半径为r1，圆心为o1，圆弧段a2的半径为r2，圆心为o2，两圆心之间距离为d，详细计算如下表所示。
(2)、合成曲骨架：依次对相邻的等分线进行求交，得到有效的交点，在交点处裁剪等分线，并计算出新的等分线，新的等分线之间再依次求交，直至无新的等分线产生，最终合成出曲骨架；
(3)、求解偏置结果：对于给定偏置距离的等距偏置情况，分别将原始轮廓中的每段曲线进行偏置，得到偏置曲线；再将每段偏置曲线分别和曲骨架求交，用交点裁剪偏置曲线，依据交点的连接关系，提炼得到偏置结果；图6为曲骨架计算等距偏置的示例，曲骨架由三条直线段和两条抛物线组成。
2)、非等距偏置处理：特殊情况下，需要进行非等距偏置，非等距偏置时，轮廓中的每一段曲线可以偏置不同的距离，这样便违背了骨架原理的中值特性，骨架的移动轨迹也不再是基本的二次曲线(椭圆、双曲线和抛物线等)，而是变成更复杂的曲线，计算难度成倍增加。因而不再适合使用“曲骨架”进行计算，本发明采用新的分段求交偏置算法思路，具体步骤如下：
(1)、局部偏置：分别按照给定距离偏置直线段、圆弧段，得到局部偏置结果，如图7所示，圆弧段的偏置距离p为500，其他的偏置距离为0；
(2)、延长求交：延长局部偏置结果，直线段延长成无限长的直线，圆弧段延长成整圆；求出相邻的直线、整圆之间的交点，如果无交点，则求出原有曲线段之间的最近点对；如果有一个交点，则将该点作为有效的交点；如果有两个交点，则筛选出一个点作为有效的交点；其中筛选规则为：如果是直线和整圆求交的情况，以整圆中心、直线法向做出一条分割线，计算原轮廓曲线中直线段和圆弧段的交点在这条分割线的左侧还是右侧，以此选择同侧的交点；如果是整圆和整圆求交的情况，连接两个圆心做出一条分割线，计算原轮廓曲线中圆弧段和圆弧段的交点在这条分割线的左侧还是右侧，以此选择同侧的交点。
(3)、裁剪拼接：用交点、最近点对来裁剪延长后的直线或整圆，依据原始轮廓曲线的顺序，依次连接形成新的轮廓曲线；
(4)、自相交处理：如果新的轮廓曲线存在自相交的情况，如图8所示，即轮廓曲线内部的曲线和曲线之间会相交；则先将新的轮廓曲线两两之间进行求交，并用交点打断；然后，沿着轮廓曲线的方向，搜索出新的闭环、开环；最后，检测闭环的绕组数量windingnumber,得到有效的偏置结果，如图9所示，得到abgh。绕组数量windingnumber常用于判断点是否在多边形或曲线上，给定一条曲线c和一个点p，构造一条从p点出发射向无穷远的射线。找出所有该射线和曲线的交点，并按如下规则统计绕组数量(windingnumber)：每一个顺时针方向(曲线从左向右通过射线)上的交点减1，每一个逆时针方向(曲线从右向左通过射线)上的交点加1。如果绕组总数为0，表示该点在曲线外；否则，该点在曲线内。
另外，本发明中新的分段求交偏置算法还能对不封闭的轮廓曲线进行偏置(如图10所示的轮廓abcd，其中p1为500，p2为400)，偏置后得到不封闭的aed和封闭的ebc，在最终有效的偏置结果中会将封闭的ebc删除。图11为非等距偏置的实例，其中a、c、d为240，b、g处为600，f处为120，e为1000)。
本发明中名词概念：
等分线：两曲线段具有一个公共的端点，从该端点引出一条轨迹线，轨迹线上的点到两曲线段的距离均相等，那么称该轨迹线为两曲线段的等分线。由此可知，若两曲线段均是直线段，则等分线为两直线段之间的角平分线。
骨架：封闭轮廓曲线上的各顶点，等速的向内移动所形成的轨迹，称为轮廓曲线的骨架。骨架是由等分线组成的。
曲骨架：轨迹包含曲线的骨架。
可以理解的是，对本领域技术人员来说，对本发明的技术方案及发明构思加以等同替换或改变都应属于本发明所附的权利要求的保护范围。
1.一种综合性的轮廓曲线偏置方法，其特征在于：将轮廓曲线按照等距偏置和非等距偏置分别进行处理，具体步骤如下：
1)、等距偏置处理：
(1)、计算等分线：将轮廓曲线中相邻的两曲线段间计算出一条等分线，遍历整个轮廓曲线，依次求出所有的等分线；
(2)、合成曲骨架：依次对相邻的等分线进行求交，得到有效的交点，在交点处裁剪等分线，并计算出新的等分线，新的等分线之间再依次求交，直至无新的等分线产生，最终合成出曲骨架；
(3)、求解偏置结果：对于给定偏置距离的等距偏置情况，分别将原始轮廓中的每段曲线进行偏置，得到偏置曲线；再将每段偏置曲线分别和曲骨架求交，用交点裁剪偏置曲线，依据交点的连接关系，提炼得到偏置结果；
2)、非等距偏置处理：
(1)、局部偏置：分别按照给定距离偏置直线段、圆弧段，得到局部偏置结果；
(2)、延长求交：延长局部偏置结果，直线段延长成无限长的直线，圆弧段延长成整圆；求出相邻的直线、整圆之间的交点，如果有交点，选择出有效的交点，如果无交点，则求出原有曲线段之间的最近点对；
(3)、裁剪拼接：用交点、最近点对来裁剪延长后的直线或整圆，依据原始轮廓曲线的顺序，依次连接形成新的轮廓曲线；
(4)、自相交处理：如果新的轮廓曲线存在自相交的情况，即轮廓曲线内部的曲线和曲线之间会相交；则先将新的轮廓曲线两两之间进行求交，并用交点打断；然后，沿着轮廓曲线的方向，搜索出新的闭环、开环；最后，检测闭环的绕组数量windingnumber,得到有效的偏置结果。
2.根据权利要求1所述的综合性的轮廓曲线偏置方法，其特征在于：在等距偏置处理步骤中，相邻的曲线段类型包括直线段-直线段、直线段-圆弧段、圆弧段-圆弧段。
3.根据权利要求1所述的综合性的轮廓曲线偏置方法，其特征在于：所述的轮廓曲线包括封闭或不封闭的轮廓曲线。
4.根据权利要求1所述的综合性的轮廓曲线偏置方法，其特征在于：在延长求交步骤中，如果有一个交点，则将该点作为有效的交点；如果有两个交点，则筛选出一个点作为有效的交点；其中筛选规则为：如果是直线和整圆求交的情况，以整圆中心、直线法向做出一条分割线，计算原轮廓曲线中直线段和圆弧段的交点在这条分割线的左侧还是右侧，以此选择同侧的交点；如果是整圆和整圆求交的情况，连接两个圆心做出一条分割线，计算原轮廓曲线中圆弧段和圆弧段的交点在这条分割线的左侧还是右侧，以此选择同侧的交点。
技术总结