科学直接获取平面形状内连续螺旋状路径的简化算法及其在机械加工等应用中的意义

可在ScienceDirect上获得目录列表计算设计与工程杂志首页：www.elsevier.com/locate/jcde计算设计与工程学报5（2018）348平面形状马丁·赫尔德Universität Salzburg，FB Computerwissenschaften，5020 Salzburg，Austria阿提奇莱因福奥文章历史记录：2017年8月17日收到2017年11月15日收到修订版，2017年2017年11月24日在线发布保留字：类螺旋路径双螺旋复合螺旋中轴线平滑高速加工A B S T R A C T我们简化并扩展了Held和Spielberger [CAD 2009，CAD A 2014]的先前工作，以获得由直线段和圆弧界定的平面形状内部的螺旋状路径：我们使用线性化来导出计算连续螺旋状路径的简单算法，该连续螺旋状路径（1）由直线段组成，（2）没有自交，（3）遵守用户指定的最大跨越距离，以及（4）在形状的内部开始并在形状的边界处结束。然后，我们扩展这个基本算法的双螺旋路径的开始和结束在边界上，并显示这些双螺旋可以用来覆盖复杂的平面形状的复合螺旋路径。我们还讨论了如何提高路径的光滑性和减少曲率变化，以及如何将它们提升到更高的水平的连续性。©2017 计 算 设 计 与 工 程 学 会 Elsevier 的 出 版 服 务 这 是 一 个 在 CC BY-NC-ND 许 可 证 下 的 开 放 获 取 文 章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍1.1. 动机一些应用需要通过沿着路径移动圆盘来覆盖平面形状。在机械加工应用中，盘模拟工具的横截面，而区域模拟所谓的凹穴。类似地，圆盘可以表示由喷嘴覆盖的区域或用于空中监视的相机装置的可见区域。在我们的研究中，平面形状可以由一个外轮廓和可能的一些岛轮廓（包含在外轮廓内），其中每个轮廓由直线段和圆弧形成传统的路径生成策略包括锯齿形图案和使用偏移曲线来形成轮廓平行图案。参见，例如，Held（1991）详细讨论了在型腔加工中的两种策略这些传统策略的共同之处在于所得到的路径包含许多尖角，即，方向的突然改变。由圆盘表示的运动物体的速度或转动惯量越高，这些方向不连续引起的问题就越多。例如，在一个示例中，对于高速加工（HSM）应用，方向的突然改变要求刀具减速到接近零的速度，改变其方向，由计算设计与工程学会负责进行同行评审。*通讯作者。电子邮件地址：held@cosy.sbg.ac.at（M.举行），slorenzo@cosy.sbg.ac.at（S. de Lorenzo）。然后加速，直到再次达到所需的最大速度。在机械加工应用中，尖角也会导致刀具载荷的高度变化。1.2. 先前工作生成平滑连续路径的一种方法是依赖于传统策略，并在后处理步骤中减少尖锐的方向不连续性：Pateloup，Duc和Ray（2004）以及Zhao，Wang，Zhou和Qin（2007），Zhao，Liu，Zhang，Zhou和Yu（2009）采用传统的刀具路径，并通过插入圆形圆角弧对其进行平滑。螺旋 状路径被 广泛认为 是避免尖 锐方向 不连续的 合适手段 。Bieterman和Sandstrom（2002）提出了一种基于偏微分方程（PDE）的方法来计算星形口袋内的螺旋状路径。它的边界轮廓是通过在不同的时间点评估偏微分方程连续向内偏移。然后用径向插值法将这些解线连接起来。Banerjee、Feng和Bordatchev（2012）使用类似的方法并解决椭圆PDE的特征值问题。相邻轮廓基于缠绕角参数化连接。此外，他们还解释了如何处理中心附近的一个岛屿的平面形状。Zhou，Zhao，Li和Xia（2016）提出了一种策略，可以产生平滑的双螺旋，这些螺旋在平面形状的边界处开始和结束。由抛物型偏微分方程导出了一系列等温线。通过在连续的等温线之间插值，产生封闭的螺旋状路径。在初始旋转https://doi.org/10.1016/j.jcde.2017.11.0112288-4300/©2017计算设计与工程学会Elsevier的出版服务这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。M. 赫尔德，S。de Lorenzo/ Journal of Computational Design and Engineering 5（2018）348349þð ÞðÞ-1/4英尺2千克最终形成双螺旋。多个连接的输入形状，即，包含岛的区域被细分为（接近星形的）子形状。一个连接的路径是通过计算每个子形状内的双螺旋，并在其末端将Zhao et al.（2016）提出了空间填充曲线另一种基于空间填充曲线的策略由Romero-Carrillo，Torres-Jimenez，Dorado和Díaz-Garrido（2015）介绍：阿基米德螺旋线通过线性变形变形，并嵌入到凸二维区域中。Abrahamsen（2015）在由直线段限定的平面形状内构造了一个多边形螺旋状路径。在计算增强的中轴树之后，计算均匀分布的波前序列。每个波前由位于中轴边缘的一系列顶点给出。通过操纵这些顶点的位置，可以生成类似螺旋的闭合路径。然后对生成的路径进行平滑处理通过在尖角处插入圆弧。Held和Spielberger（2009年，2014年）为一般的非凸平面形状生成螺旋状路径，无论是否有岛。一系列的圆被放置在中轴上，其半径随着时间的推移而增加。这些圆的一部分被插值和连接由其他圆弧形成G1连续路径。虽然我们自己的工作最初是由我们的工业合作伙伴的HSM应用驱动的，但我们注意到，在CAD/CAM之外也出现了对覆盖特定区域同时避免尖锐方向不连续性的路径的需求：例如，Chandler、Rasmussen和Pachter（2010）将圆角弧插入多边形路径中，以考虑无人机的机动性约束。我们参考Keller（2017）最近对空中监视的平滑路径的详细讨论。1.3. 我们的贡献由于Held和Spielberger（2009，2014）的算法很难进行理论分析，甚至更难可靠地实现，因此在这项工作中，我们采用了他们的基本思想并对其进行了显著简化：输入形状的中轴线的线性化允许提出易于实现的多边形螺旋状路径的算法。(And实际上，该算法的实现已经在我们的工业合作伙伴处商业使用。）该路径是连续的，没有自相交，并遵守用户指定的最大然后通过细化其顶点的位置来平滑该初始路径，这有助于减少曲率变化。它可以被提升到G1-连续或C2-连续的双圆弧或三次B样条逼近。(We使用POWER APX包（Heimlich Held，2008; Held Kaaser，2014）。正如Held和Spielberger（2009，2014）的工作一样，我们的螺旋状路径始于口袋的内部，并在其边界结束。我们的方法的简单性允许推广这个计划，并设计双螺旋路径，开始和结束在边界上的任意点。这使得通过（1）将形状分解成更简单的子区域，（2）计算每个子区域内的（双）螺旋，以及（3）连接各个路径以形成一个连续路径，更容易用一个连续的螺旋状路径覆盖复杂形状。空中监视或搜索救援任务的路径查找算法&。我们的方法在很大程度上依赖于输入的中轴：（1）它是捕获形状几何和计算偏移类曲线的关键工具，这些曲线构成了我们路径的基础。（2）它允许确定“步骤”的上限在螺旋部分之间的距离上。除了其固有的简单性，我们的方法的一个主要优点是它的通用性：它可以处理任意复杂的平面形状，有和没有岛屿，从而保证最大2. 预赛考虑一个由直线段和圆弧界定的平面输入形状，假设我们要在这个形状内移动一个半径为q的圆盘，使圆盘扫过的面积等于形状的（大部分）。如果圆盘在整个运动过程中必须保持在形状内，那么很明显，它的中心永远不会比q更接近形状的边界，即使这个约束导致形状的某些区域被暴露。(E.g.、对于多边形形状，这将发生在该形状的凸顶点处。圆盘中心的所有允许位置的轨迹可以作为形状和以原点为中心的半径为q的圆盘的闵可夫斯基差来获得。(The欧氏空间中两个位置向量集合A;B的闵可夫斯基差A-B平面R2定义为A乙：CR2：cBA.）。我们称这组允许的中心位置为口袋P。(But同样，我们的工作并不一定局限于传统的型腔加工应用。）众所周知，（1）如果初始形状由n条直线段和圆弧围成，则P的边界@P由O n条直线段和圆弧组成，（2）它可以通过基于Voronoi的偏移在O nlogn时间内得到（Held，1991）.我们使用VRONI/ARC V-RONI（Held，2001; Held Huber，2009）软件包来计算Voro- noi图、中轴1和偏移。当然，为了覆盖尽可能多的P，盘将不得不在一次完成过程中沿着P的边界@P在实际的加工应用中，人们可能想要考虑输入形状和半径为qe的盘的闵可夫斯基差，对于某些e>0，因此将@P进一步向内推。这将有助于避免刀具在沿螺旋状路径行进时非常接近输入形状的边界，并且仅沿边界留下少量材料用于精加工刀路。我们假设P是路连通和单连通的。如果P是不连通的，那么我们将对P的每个连通分量分别运行我们的算法。如果P包含岛屿，即，是多连通的-然后我们遵循（Held& Spielberger，2014）并通过引入桥将其转换为单连通区域，见图2。1.一、（不用说，这是一个相当复杂的口袋，很难只通过一个螺旋状路径来覆盖。每个桥对应于两个直线段，这两个直线段具有相反的取向，并且以适当的方式添加到P的边界，使得获得单个边界轮廓。在选择“好”桥（相对于预期应用）时的人工指导很自然地，将绕点r缠绕k次的螺旋线分成k个单独部分的序列，其中每个部分对应于绕r的一整圈。我们把螺旋线的这一部分叫做圈。那么，在圈Li 1的点p处的跨越距离是从p到下一个内圈Li的最小距离，参见 图 二、显然，一般来说，跨越距离必须小于正在移动的盘的直径，以便避免P的未被覆盖的区域。然而，在实践中，使用了相当小的跨越距离对于HSM，1由于没有有效的算法来计算NURBS曲线（或其他自由曲线）的中轴是已知的，任何自由输入边界将不得不近似直线段和圆弧之前，我们的算法的应用。350M. 赫尔德，S。 de Lorenzo/ Journal of Computational Design and Engineering 5（2018）348DDQ马格德堡马格德堡马玉玉马玉玉马丽珍Fig. 1.一个三次B样条曲线，作为一个多连通平面形状内的螺旋状路径，该平面形状通过桥转换为单连通形状（以蓝色显示）。图二.螺旋线的搭接Li<$1上的点p处的局部跨越距离是从p到下一个内搭接Li的最小距离。步进值是直径的相当小的一部分，其取决于刀具的材料以及工件。（它在很大程度上与口袋的几何形状无关。）例如，在一个示例中，对于铝或（非硬化的）钢，典型的最大阶跃由直径的约15%给出在任何情况下，用户都可以控制螺旋路径的最大步距D，这一点很重要。我们注意到，在数学中，“螺旋”一词的意思是从中心点c出发，以单调增加的曲率和距离绕着c弯曲的曲线因此，螺旋的每一圈都位于以c为中心的内圈和外圈之间：每一圈都从内圈开始，绕c一圈后到达外圈。从而到外圆的距离除以我到内圈的di单调减小。在续集中，我们调查的我们的路径也是从一个中心点r开始，并围绕它缠绕。这样的螺旋状路径的每一圈都从一个内边界曲线开始，并在围绕r缠绕一次后到达其外边界曲线，从而也减少了-单调地计算分数d然而，对于我们的螺旋状路径我我们允许一般的嵌套Jordan曲线2代替同心圆作为边界曲线。因此，到r的距离和到内边界曲线的距离以及曲率也可以沿着这样的路径的一圈减小。尽管如此，为了术语的简单起见，我们在本文的其余部分也倾向于将术语“螺旋”应用[2]乔丹曲线是一条简单的闭合曲线，即，它没有自相交。3. 中轴树根据标准定义，袋P的中轴P是P内部的所有点的轨迹，这些点在P的边界上具有多于一个的最近点，参见。图3（a）.已知是P的Voronoi图的子集，并且由直线段和作为边的二次曲线的部分为了简化Held和Spielberger（2009）的算法，我们近似中轴的每个边缘P通过多边形链。这样的多边形链的顶点是通过将均匀分布的采样点放置在边缘上以使得链的段的最大长度小于用户提供的或示意性地确定的值k来获得的。 该过程产生离散的中轴线MA0P。 我们将MAP_0上的采样点和MAP_0上的原始节点称为MAP_0上的节点。像往常一样，0P 是以p为中心的最大圆盘（“间隙圆盘”）的半径，适合P。对于MA0<$P <$的每个节点p， 我们考虑点p1;p2;. ;p k 在间隙圆盘p接触边界的地方@P的P，和构建体的间隙线段第1页;第2页;. ;ppk.如果p恰好是@P的圆弧a的中心，那么我们在a上选择n个均匀间隔的点，间距小于k。请注意，某些间隙线可能共享P的边界@P的相同反射顶点作为起点。我们把所有间隙线段的集合加到MA0P上，得到新的（平面直线图）MA0P。中轴线MAP-P- P形成树是已知的，因为P不包含岛。此属性将延续到00P如果我们把两条不同的间隙线的起点看作不同的节点，即使它们在P的边界的同一个反射顶点上相交。因此，通过选择MA00P的一个（内部）节点r作为根，我们可以将MA00P转换为根树Tr ，即由下式导出的离散中轴树：00 P.（由于我们将在不同的地方以及在数学方程中对P的离散中轴树使用这个符号，因此我们保持符号简单，并且在符号中不明确Tr对P的依赖性。）所有对应于Tr的叶子的点都位于@P上。特别地，@P上的间隙线的每个起点形成Tr的叶节点。由于Tr的所有边都由线段给出，因此很容易计算Tr的两个节点p;q之间沿Tr的唯一路径的（欧几里德）长度dTr<$p;q<$。这允许我们将Tr的节点p的欧氏高度定义为：hTrp：¼maxdTrp;q;其中，最大值取在的子树的所有节点q上，Tr根在p。图三. (a)口袋P的中轴;（b）以r为根的高度平衡离散中轴树Tr，定义r的欧几里得高度hTrr的两个叶子以红色表示，对应的两条径向路径以橙色表示M. 赫尔德，S。de Lorenzo/ Journal of Computational Design and Engineering 5（2018）348351不TT不马玉玉马玉玉¼TTv2Tp不不veveT¼正如Held和Spielberger（2014）中所述，我们假设Tr是高度平衡的：我们假设hTrr由至少两个不同的Tr的叶子。也就是说，我们假设存在k个P2个不同的叶节点v1;v2;. . ;v k，使得hTr rdT rr;v 1dTrr;v2···dTrr;vk：从r到这样一个叶v i的每一条路径称为R. 参见图3。(For为了视觉清晰起见，我们用非常粗略的离散化和（在随后的图中）不切实际的大跨越距离来示出这个玩具示例。如果r中不存在这样的节点r，那么我们在r的边中插入一个新节点，以实现这样一个完美的高度平衡。计算Tr上所有结点的Euclidean高度和平衡高度可以很容易地在时间上与Tr上的边数成线性关系（Held&路径。我们参考Held和Spielberger（2014），详细讨论了起点变化的影响4. 冲量传播类似于Held和Spielberger（2009），我们考虑在时间间隔1/20;1]期间活跃的脉冲，其在时间t：1/40处在离散中轴树Tr的根r处开始，并且在时间t：1/41处在Tr假设我们想让冲量沿r的每一条径向路径匀速运动。那么脉冲必须覆盖在单位时间内，这意味着，沿径向路径的每一条边的脉冲等于hTr r。因此，在“开始时间”到达Tr的径向路径上的节点pH ðr Þ-hðp ÞSpielberger，2014）。特别地，不需要人类交互来选择根r。在后续我们将使用r作为起点t¼TrTr：hTr r我们的螺旋状路径。当然，如果选择高度平衡根r以外的点作为起点，则本文其余部分中解释的算法仍然适用原则上，袋P内部的任何点p都可以被选为螺旋状路径的起点和中轴树的根r。如果p不存在于00P 然后我们考虑p到P的边界@ P上的（最接近的）投影，并在00 P和@ P之间添加该投影的伸长作为虚拟Voronoi边（Held&Spielberger，2009）。但是我们注意到，选择一个不同于高度平衡的根部r的起始点将导致（1）最终螺旋状路径的长度增加，（2）圈数增加，以及（3）圈的间距非常不规则。通过第5节中的算法计算出的MA 00 MIPs上五个不同起始点的样本（多边形）螺旋，见图4。注意，对于所有五个，使用相同的最大跨越距离D这种简单的观察可以以递归方式用于确定脉冲到达特定节点（或甚至Tr的边缘内的任何点）的时间以及Tr的所有边缘的脉冲速度。最初，Tr的径向路径上的所有节点的开始时间是已知的。（回想一下，根r的开始时间tr被设置为tr：¼0。）现在想象从r中去掉所有径向路径的所有边。把这些“最长的树枝”劈开r分解为若干根子树，每个子树的根在一条径向路径的一个结点上，设p是子树Tp的根，用tp表示它的开始时刻。我们在Tp中选择一个离开节点p0，dTrp;p0maxxfdTrp;vg;关系被任意打破。也就是说，从p到p0的路径是Tp中（以及Tr中）从p到Tp的叶子的最长路径。设q是p在这条路上的子项，le表示p和q之间的边e的长度。从p到p0的整个路径的长度dTr<$p;p0<$由lb表示。 由于脉冲必须在时间t：1到达p0，因此脉冲沿着e和从p到p0的路径的所有其他边缘的（恒定）速度由下式给出：ve¼L b1/4hTrq le：1-tp1-tp图四、将螺旋路径的起点从高度平衡的根部r移开可能会对路径的长度及其圈的间距产生重大影响。中间的（较大的）图显示了从r开始的路径。我们得出结论，脉冲在开始时刻达到qtq¼tple：类似地，由于脉冲的速度沿着整个边缘e保持恒定的事实，e内（的相对内部）的点s的开始时间ts简单地由下式给出：tstpdTrp;s：与径向路径上的节点一样，从p到p0的路径上所有其他节点的开始时间也可以很容易地计算出来。一旦所有这些开始时间是已知的，我们从Tp中删除从p到p0的路径的所有边，从而将Tp分成许多子树。然后，我们递归地将该方案应用于这些新生成的子树。注意，我们有v ，e，6，v，其中v是沿径向的速度路径R. 此外，等式V e只有当从r到p0的路径也形成径向路径时，v才成立。这种递归方案允许我们确定所有的边缘速度和开始时间在时间上与r的边缘数成线性关系。很容易证明这个方案保证脉冲在时间t：1/4到达Tr的所有叶。有效地，该方案将r分成多个分支，每个分支具有恒定的脉冲速度。参见图5。我们用B表示这组分支。352M. 赫尔德，S。 de Lorenzo/ Journal of Computational Design and Engineering 5（2018）348不ð Þ¼-简体中文公司简介MX2Xy2Yy2YX2X平凡的）重叠由L1和LM之间的插值形成。每hTr rDS图五. 本文给出了Tr.当脉冲流过Tr时，它覆盖Tr的增加部分。脉冲从r到Tr的某个叶在时间t到达的点称为时间t的顶点。显然，对于任何时间t2½0;1]，存在的顶点最多与Tr中的叶子一样多。通过计算特定时刻的所有顶点，并将它们以当以深度优先方式遍历r时它们出现的顺序排列，可以构建闭合多边形链，即时间t处的所谓波前w t。必须仔细选择波前的间距，以确保遵守用户指定的最大步进D。考虑时间的均匀分解见图6。对于m：1/45，袋内的一系列均匀间隔的波前。波前w t0等于r，而wt5与P的边界重合;两者都没有显示。 在Tr中，r和Tr的叶之间的两个径向路径以橙色示出。意味着径向路径被波前分成长度最多为D的部分。5. 生成一个螺旋我们现在专注于实际螺旋路径的生成，这与Held应用的策略根本不同，t0;t1;.. . ;tm，对于某个（尚不清楚）m2N，其中01。<<<波阵面的顶点由脉冲在时间ti的位置给出，见图12。 六、令tω：ti<$1ti表示两个相邻波前的时间回想一下，两个封闭有界集合X;Y<$R2之间的（对称）豪斯多夫距离H<$X;Y<$R2定义为：.ΣHX;Y：¼max max mindx;y; max mindx;y;Spielberger（2009）. 我们解释并描绘了逆时针方向(CCW)螺旋路径;获得顺时针（CW）螺旋所需的修改是微不足道的。螺旋路径S_P;D_p由m个圈L1;L2;. Lm.此外，我们有L0：r和Lm 1：@P作为两每个圈是一个多边形链，其顶点位于Tr上。简而言之，我们通过在波前之间进行插值来计算最里面的（非平凡的）重叠L1，即，根r 的Tr，和w=1。 同样，L m 由插值法在w_t m-1m和w_t m_t之间，即， @P。 参见图7。所有其他（非其中d <$x;y<$x表示两点的标准欧几里得距离x;y2R2。我们的目标是选择tω，使得Hwti;wti16D为所有i2f0;1;.. . ;m-1g：我们记得，脉冲速度对于Tr的每个边缘都受hTr<$r限制。这意味着脉冲传播的距离最多为s hTr R 随着时间的推移，R.因此，我们可以建立在ws0和ws0s之间的对称Hausdorff距离的上界，其中s02½0;1-s]，as如下：Hws0;ws0 s6s·hTrr：这意味着脉冲沿着最多D的距离如果我们设定秒：¼D ：总结，以确保Hwti;wti16D为所有i2f0;1;. . . ;m-1g，将m设为一圈开始和结束在一个特定的间隙线事件在r。重要的技术问题是以这样的方式生成这些圈，即相邻圈之间的跨越距离不超过用户指定的最大跨越D。我们首先解释L1是如何产生的，见图8。回想一下，wt0退化为r。设q是w∈t1∈t的顶点，这是由间隙线rv 0，所有圈开始结束因此，L1开始于r，结束于q0。我们从q0开始，按CCW顺序对wt1的顶点进行编号。现在考虑w = 1的某个顶点，例如，图8中的q4。设d表示w=1的周长，设d4表示多边形链的长度q0q1. q4，令d4：1/4 dTr r r;q4n，即，从r到q4沿Tr的距离然后，将L1的一个二次角c放置在从q4到r的路径上，距离（沿Tr）为.1-d4次·d从Q4。我们将c存储在Tr的相应边。请注意，w*t1**的某些顶点可能最终将候选角点存储在m：¼，1，：这给tω：1/4作为对应于相邻波前的两个脉冲时间之间的恒定时间距离。注意，这种结构相同的边缘或路径朝向r。这些候选角点被分类为在将权重d设置为@P的周长并让wt m-1的顶点扮演r的角色之后，我们以类似的方式通过从wt m的顶点移动来获得L m的1型候选角点，即，@P，朝向w= m-1的顶点。如果需要的话，我们也可以让L m绕r缠绕不止一次，并让它结束于在@P上的某个点，而不是v 0，通过使d大于cir，@P的引用。4M. 赫尔德，S。de Lorenzo/ Journal of Computational Design and Engineering 5（2018）348353ðÞSunday2f-gð--不不ðÞðÞðÞð-Þ·见图7。(a)第一圈和最后一圈是通过插值相邻波前得到的。(b)从r开始到@P结束的最终螺旋路径。见图8。第一圈从Tr的根r开始，在净空线（以绿色显示）上的wt1的顶点q0结束，所有圈都在净空线上开始和结束。为了实际生成L1，我们以深度优先顺序扫描Tr，从r开始并沿着rv 0移动作为Tr的第一分支。每当遇到L1这种深度优先扫描建立了L1的所有顶点，所需的（CCW）命令。现在，我们开始一个新的深度优先扫描，在L1的每个顶点q处朝向Tr的叶子。深度优先扫描的递归在我们沿着r从q到达距离m1D时停止，或者，如果我们到达边界@P，则停止。在递归的每个这样的停止点然后，从r开始的另一深度优先扫描通过每当遇到Lm的候选角（类型1或类型2）时停止递归来揭示Lm我们的构造包含以下两个距离性质：HL0;L16 D和HL1;Lm6m-1·D：对应于时间i = m - 2的“前i2f1;2;.. . m~2g.通过连接所有非平凡的圈L1;L2;. 我们自然地得到P内的一条多边形路径S_P;D_p。简单地说，S_P;D_p开始于r，结束于@P。此外，P;D不是自相交的，因为我们以严格单调的方式向外移动，从r开始，直到我们到达@P。 并且由于该修正，S/P;D/P尊重最大跨距D：m-2圈L2;. ;Lm-1将至多为1/m-1/m· D的距离（沿Tr）分成至多为D的m-1个长度部分。因此，对于所有i 1; 2;.. m1。我们总结我们的结果如下：HLi;Li16D为所有i2f0;1;.. . ;mg;这解决了我们的螺旋路径S_P;D_p服从用户指定的最大步距D的要求。我们注意到，D形成了真正的最大跨越距离的上限：我们不确定实际的豪斯多夫距离，而只测量沿着P的中轴的边缘（可能是弯曲的）的距离。(AnAlt，Becomods，Blömer（1995）的算法允许在O nlogn时间内计算具有总共n个顶点的多边形曲线之间的一个Hausdorff距离，但是没有明显的方法将该算法应用于生成的螺旋路径的圈6. 改进和平滑螺旋6.1. 脉冲修正回想一下，脉冲在B的每个分支上以恒定速度运动，参见。图五.特别地，它在Tr的每个边缘内是恒定的。因此，脉冲的速度可能在r的某些节点处快速变化。这导致了非常尖锐的角落，螺旋路径。我们现在解释如何通过修改脉冲传播来解决这个问题。为了减轻当一个较短的分支开始时快速变化的速度的影响，我们放弃了使用恒定速度的简单方案，并为B的每个元素分配一个线性速度函数。与第4节一样，r的动态速度被设置为hTrr，其开始时间tr被设置为0。B中的分支，同样，按遍历r以深度优先的方式。假设b是当前被检查的分支，p是它的开始节点，p0是它的结束（叶）节点，lb是它的长度。根据第4节，分配给b的所有边缘的恒定我们现在认为，Lm保证包含在由w tm-1和w tm定义的环中：Lm的每个类型1候选角都位于该环中，因为它是由之间的插值生成的。v平均值Lb¼1-tp;wt m-1和wt m。每个不位于@P上的第2类候选角点沿着Tr与L1的顶点的距离为1/m-1/m·D，因此，与r的距离至少为1/m-1/m·D。然而，wtm-1的所有顶点与r的距离至多为m1D。因此，每个类型2候选角也位于由wm-1和wm-2定义的环内。结果，L m也位于该环中。(More精确地说，除了Lm的起点和终点之外，所有的Lm都位于这个环的内部。特别是，我们得到其中tp表示p处的开始时间。粗略地说，新的想法是，从沿b的初始速度开始，（理想情况下）与冲量到达p时的速度vp相同，并且随着接近@P，线性地减小该速度。当然，即使在这种修改，脉冲将不得不行进lb的距离，在时间1 -tp内。我们定义沿b的起始速度为v. 如果2 vavgP vp，则v p;HLm ;@P/H/Lm;Lm1 106D开始：¼2V平均值否则：作为第三种距离属性。此外，沿b的端部速度v_end被定义为：剩下的L2圈;. 如果我们将一圈视为L1和Lm之间的特殊类型波前的自由度，则可以类似于初始波前的生成来生成Lm-1：vend：¼2vavg-vp如果2vavgPvp;0其他：同样，我们让脉冲沿Tr传播。然而，该修改的脉冲传播在时间t：1/40在对应的线速度函数#b表示沿b由下式给出：L1，并且在时间t：1/4处在Lm的顶点处结束。然后，对于适当选择的速度脉冲的边缘上的Tr，#bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb.354M. 赫尔德，S。 de Lorenzo/ Journal of Computational Design and Engineering 5（2018）348开始— 吉夫开始 — v端（b）M. 赫尔德，S。de Lorenzo/ Journal of Computational Design and Engineering 5（2018）3483552¼ðÞ不（2）1/2（1）。显然，在特定时间t，沿b的速度，其中tpt61，由下式给出：

下载后可阅读完整内容，剩余1页未读，立即下载