代数曲线的有理二次B样条逼近

基于代数曲线的合理分割,给出了曲线段的三角形凸包的描述.提出了以曲线段端点的两条切线确定控制多边形的方案.详细地讨论了代数曲线的分段有理二次B样条逼近算法.逼近曲线保持了原始曲线的一些重要几何性质,如单调性,凹凸性,G1连续性.数值实验表明,该算法提供了代数曲线近似参数化的一条有效途径.     

二阶几何连续的闭合全凸曲线的构建EI北大核心CSCD

针对现有保凸曲线插值算法不能解决过平面凸包点集构建闭合全凸光滑曲线的实际应用问题,提出一种二阶几何连续的闭合全凸曲线的插值算法.该算法以一个平面凸包点集为插值点,以相邻的2个凸包点作为1条3次Bézier曲线的第1个与第4个控制点,根据相邻3次Bézier曲线间的二阶几何连续性条件求解每条3次Bézier曲线的第2个与第3个控制点;然后从理论上证明了曲线的闭合性、全凸性及二阶几何连续性,并提出一种简易有效的曲线构建算法.实验结果表明,该插值曲线具备明确的物理学意义上的解释;将该算法应用于模拟卷尺测量轨迹以提取树干直径的实际场景中,进一步验证了其精确性与实用性.     

二阶几何连续的闭合全凸曲线的构建

针对现有保凸曲线插值算法不能解决过平面凸包点集构建闭合全凸光滑曲线的实际应用问题,提出一种二阶几何连续的闭合全凸曲线的插值算法.该算法以一个平面凸包点集为插值点,以相邻的2个凸包点作为1条3次Bézier曲线的第1个与第4个控制点,根据相邻3次Bézier曲线间的二阶几何连续性条件求解每条3次Bézier曲线的第2个与第3个控制点;然后从理论上证明了曲线的闭合性、全凸性及二阶几何连续性,并提出一种简易有效的曲线构建算法.实验结果表明,该插值曲线具备明确的物理学意义上的解释;将该算法应用于模拟卷尺测量轨迹以提取树干直径的实际场景中,进一步验证了其精确性与实用性.     

一类三次代数曲线的插值和逼近的算法

利用几何与代数相结合的方法,研究一类具有几何约束的三次代数曲线插值和逼近的问题。研究这类三次代数曲线的光滑拼接和保凸性,得到这类三次代数曲线之间的G1、G2光滑拼接定理、保凸性定理及全凸性定理。给出这类代数曲线的插值逼近算法,以及该算法实施的具体步骤和收敛性的证明。通过实例证实了该算法的可行性和有效性,总结了该算法的优点,实例计算结果表明,该算法具有较好的插值和逼近效果。     

三角形拓扑网格上曲面造型的切割磨光法

本文考虑三角形拓扑网格上的自由曲面造型方法.讨论了三角形拓扑网格上的切割磨光方法,研完了生成曲面——TC曲面的性质,给出了生成TC曲面的两种算法,并对算法进行了分析.结果表明,TC曲面具有凸包性、几何连续性、局部性、插值性等许多良好的性质,适合在曲面造型系统中采用.     

函数的分段有理二次B样条插值

通过对函数进行合理分割,给出函数分段三角形凸包的概念。提出了以分段区间端点的两条切线确定控制多边形的方案。详细地讨论了函数的分段参数有理二次B样条插值算法。插值函数保持了原始函数的一些重要几何性质、如单调性、凹凸性、G1连续性。数值实验表明,算法提供了函数近似表示的一条有效途径。     

插值型三次样条及保形插值曲线曲面

为直接混合插值点,生成插值曲线和张量积型插值曲面,讨论了插值型样条函数.为生成保形插值曲线和曲面,分析了其不同于非插值曲线和曲面的凸包和保凸的具体含义.推导出三次C~1插值型样条函数公式,构造三次C~1插值样条曲线,给出了插值样条曲线的分段Bezier表示.所得三次插值曲线曲面具有几何不变性、凸包性质、局部可调性.讨论了插值曲线的保凸性质及关于插值数据点前后顺序的对称性.展示了具有和不具有保形性质插值曲线和张量积型插值曲面的实例.     

函数分段有理三次Bézier插值

根据函数的几何性质,对函数进行适当分段。定义了函数的分段三角形凸包,提出了一种控制顶点和权因子的确定方案。详细地讨论了函数的分段有理三次Bézier插值算法,定义了一种便于计算的新型误差。插值函数保持了原始函数的重要几何性质,如单调性、凹凸性、G1连续性。最后以数值实验结果表明了算法的有效性和可行性,该算法提供了函数近似表示的一条有效途径。     

拟Timmer曲线

三次Timmer曲线能够插值的控制多边形中间控制边的中点,但它却不能保证与该控制边相切,且三次Timmer曲线不具有凸包性。针对于此,提出了一类曲线（称之拟Timmer曲线）,拟Timmer曲线不仅具有与Timmer曲线所类似的性质,而且具有凸包性,且能够插值中间控制边的中点,并与之相切。     

代表性调色板提取及图像重着色EI北大核心CSCD

基于调色板的图像编辑技术是近年的热门研究方向,在海报制作、服装设计、电影、短视频编辑等方向有着广泛的应用.通过计算凸包提取图像调色板是一个较新技术.然而,其目前仍然存在2个问题:一是忽略了凸包内部的颜色分布,使得调色板整体上缺乏代表性;二是插值权重缺乏稀疏性,难以实现针对性的局部编辑.针对上述问题,提出一种新颖的调色板提取算法,并在此基础上实现高效的图像重着色编辑.首先,提取图像在RGB空间的凸包并简化;其次,通过聚类算法捕捉凸包内部的颜色分布,构造代表性调色板;最后,在RGB空间对调色板颜色进行四面体剖分,并对图像像素进行插值.为了验证该算法的有效性,从互联网上获取了40余幅图像组成数据集进行实验,对插值权重的稀疏性、图像重着色效果等进行了对比分析和用户调研.大量实验结果表明,该算法提取的调色板具有更好的代表性,插值权重具有更好的稀疏性,实现了更精确的局部编辑.     

求两个相交凸多边形并的凸包及交的算法

凸多边形交、并求解的难点在于如何维护结果多边形的顶点序列。利用坐标的极值将凸多边形分成几个段,利用凸壳顶点有序性,分段计算凸壳顶点而得到凸壳。两个相交的凸多边形P和Q,求P和Q并的凸壳通过计算它的4个单调段来进行。每个单调段的点是否是凸壳上的点只与2个凸多边形中的同一类型的单调段有关。该算法充分地利用了凸多边形顶点的有序性,使算法的时间复杂度达到最小。     

基于凸多边形的凸壳算法

确定平面点集的凸壳问题在计算机图形学、图像处理、CAD／CAM、模式识别等众多领域中有广泛的应用。本文根据凸多边形的性质构建了一种新的基于凸多边形的凸壳算法，该算法利用X、y坐标的极值将凸多边形分为几个段，应用凸壳顶点有序性，分段计算凸壳的顶点而得到凸壳。理论分析和实验结果表明，该算法运行速度快效率高，具有较强的实用性。     

平面点集凸包快速构建算法的研究

文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。     

基于凸包和网格索引技术的快速TIN生成算法及应用

在原有凸包推进算法的基础上,提出了一种针对散乱点集的快速生成TIN的算法.通过在三角形外接圆的最小网格覆盖中查找点扩展三角形,使得每次查找的点的个数与且只与散乱点的分布有关,而与散乱点集的大小无关;同时利用有向凸包和动态修正前沿圈等技术避免生成重复三角形,从而大大提高了建网的速度.实践证明,该算法具有可操作性和较强的实用性.该算法实现了两类基于不规则三角网数字地面模型的分析应用.     

基于Delaunay三角剖分生成Voronoi图算法

针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。     

Convex hulls of objects bounded by algebraic curves

We present an0(n ·d ^o(1)) algorithm to compute the convex hull of a curved object bounded by0(n) algebraic curve segments of maximum degreed.     

The Convex Hull of Rational Plane Curves

We present an algorithm that computes the convex hull of multiple rational curves in the plane. The problem is reformulated as one of finding the zero-sets of polynomial equations in one or two variables; using these zero-sets we characterize curve segments that belong to the boundary of the convex hull. We also present a preprocessing step that can eliminate many redundant curve segments.