杭州电子科技大学毕业设计（论文）外文文献翻译毕业设计（论文）题目Bézier曲线的细分技术翻译（1）题目Bézier曲线的交集的完整细分算法翻译（2）题目轮廓平滑算法基于Bézier曲线的应用学院计算机学院专业计算机科学与技术姓名郭佳远班级09052314学号09051412指导教师余正生译文一：Bézier曲线的交集的完整细分算法CheeK.YapSCG06Proceedingsofthetwenty-secondannualsymposiumonComputationalgeometryPages217-226CheeK.Yap摘要：我们给第一个完整的细分算法可能与切线相交的两个Bézier曲线F，G，交叉点。我们强大的细分方法算法是基于几何分离的界限，它们使用同一个标准的，用于检测非交叉交点曲线。我们的算法是自适应的，仅根据精确的长浮点数计算。特别是，我们避免操纵代数数字和合成计算。它被设计成与现有的算法竞争哪个是“好”的选择。所有的标准算法假定F，G是互质的-我们的算法需要推广这一点。关键词：计算几何，曲线相交，Bézier曲线,，细分方法，有效的数值算法，精确的几何计算。1介绍代数曲线和曲面的交叉分析在许多几何模型领域是一个根本性的问题[16]。最实用的算法是基于自由曲面的曲线和曲面[8，6]。在本文中，我们考虑一类自由曲线，Bézier曲线。目前所有的交叉贝塞尔曲线算法是不准确的，主要的就是不稳定的问题。让我们看看一个根本原因。一条曲线F是一个有限的曲线段，代表序列P（F）=（P0，...，PM）的控制点[8,6]。让CH（F）表示P（F）中，作为观察的凸包封闭区域。一对（F，G）贝塞尔曲线被称为候选对CH（F）∩CH（G）的非空。标准贝塞尔曲线相交算法是基于两个曲线的想法。首先，使用属性，包含一条曲线F在CH(F)，该算法可以丢弃非候选对。其次，算法的操作主要是细分，曲线F分割成两个代替曲线F0，F1采用DeCasteljau的算法。通用交叉算法候选对维护一个队列Q。只要Q为非空，从Q中提取候选人对（F，G）。如果F∪G的直径小于ε，则输出该对；否则它细分曲线具有较大的直径，来讨论F，把他分成代替曲线F0，F1，并在Q上附加（F0，G）和（F1，G）。该算法依赖于一个常数ε>0：（F，G）对的直径小于ε被视为相交。为显示的目的，这样的常量是合理的。但对于拓扑分析的曲线的安排，我们希望输出（F，G）对代表的独特交集。但通用的算法，输出一对（F，G）没有交集，或有多个交点。让p是F和G的一个交点。在标准假设，F，G有没有共同的组件，然后，p是F∩G的一个孤立的点。在P点的交集可以是切向或横向。这取决于F和G在p点的切线是否或重合。另外，我们可以根据曲线是否彼此交叉的在p或没有，把P作为一个交叉或不相交叉的交点；这相当于交叉点p的重数是奇数还是偶数。不相交的交点，必须相切的，横向交叉点必须是横切的。因此我们有3个可能性，如图1所示。（a）横向的（交叉）（b）切向的（交叉）(C)切线(不相交)图1：交点：（a）横向（b）切向（c）切线可以避免使用ε吗？这似乎也合情合理，如果F和G只有交叉的交点，那么我们可以设计一个不使用任何ε来限制基于细分交叉算法。这不是显而易见，但它是隐含了本文交集算法。在任何情况下，关键的问题是如何检测非交叉的交点。最近，沃伯特[23，22]，解决了非奇异代数曲线的问题。这类曲线，她的地址和本文中提到的那些不具有直接可比性，虽然Bézier曲线是比较特殊的代数曲线，它们可以是单数（参见图5）。她介绍广义Jacobi曲线的技术来检测不相交非奇异的曲线的交点。她还使用细分的空间，以避免操纵代数数字（不同于传统方法的基础上圆柱分解）。但她的做法仍然使用有效的代数工具，如生成物和根隔离。这样代数技术在其他部分的算法是花费很大的和减少的有效性的适应性的。一个最近的一篇论文中，Seidel和沃伯特[20]地址计算平面代数曲线的拓扑安排的；再次，细分和代数方法相结合的被使用。相比之下，我们使用仅有的代数的信息是代数的零界。否则，我们使用长浮点数和原始的几何操作进行纯数字计算，如计算凸壳并相交的用一条线的曲线。这不是明显的先验我们可以只用这样的操作实现我们精确的曲线相交的目标。比如，一个在沃伯特-赛德尔设定中是不知道纯粹的自适应/数值版本。前的细分算法采用各种用于检测的交点的标准。这些部分都是典型的标准：要么拒绝标准，确认非交叉或验收标准，确认交点。一个完整的标准是，既接受和排斥的标准。上面的泛型算法仅使用凸壳准则。由于这是一个拒绝的标准，通用的算法也从来没有肯定的交点。Sederberg和Meyers[19]根据矢端曲线肯定存在的横向交叉点给出了验收标准。但是没有任何已知