The Convex Hull of Freeform Surfaces

We present an algorithm for computing the convex hull of freeform rational surfaces. The convex hull problem is reformulated as one of finding the zero-sets of polynomial equations; using these zero-sets we characterize developable surface patches and planar patches that belong to the boundary of the convex hull.     

A Total Order Heuristic-Based Convex Hull Algorithm for Points in the Plane

Computing the convex hull of a set of points is a fundamental operation in many research fields, including geometric computing, computer graphics, computer vision, robotics, and so forth. This problem is particularly challenging when the number of points goes beyond some millions. In this article, we describe a very fast algorithm that copes with millions of points in a short period of time without using any kind of parallel computing. This has been made possible because the algorithm reduces to a sorting problem of the input point set, what dramatically minimizes the geometric computations (e.g., angles, distances, and so forth) that are typical in other algorithms. When compared with popular convex hull algorithms (namely, Graham’s scan, Andrew’s monotone chain, Jarvis’ gift wrapping, Chan’s, and Quickhull), our algorithm is capable of generating the convex hull of a point set in the plane much faster than those five algorithms without penalties in memory space.     

始于凸包络线的闭主曲线学习算法研究

本文提出了将凸包技术与自组织拓扑映射技术相结合的一种针对封闭曲线特征提取的主曲线学习算法,解决了一般主曲线算法无法有效模拟封闭和较为复杂分布数据集的难题。算法以数据集的凸包络线为起始步,通过分析数据集的全局和局部特征,逐步逼近数据集分布并获得封闭主曲线。算法的关键在于凹点挖掘算法的研究。实验结果表明,对于一般封闭曲线点集,该方法均能在较短的时间步内较好地逼近源数据集。该算法结构简单,复杂性在最坏情况下也不超过Ｏ（n^2）,同时对图像的有界连通区域外部边界特征的提取与图形识别亦将具有较高的应用价值。     

基于区域正交化分割的平面点集凸包算法EI北大核心CSCD

为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快.     

基于凸壳算法的建模算法的研究

基于对当前三维建模方法的研究,提出了基于凸壳算法的物体建模算法。该算法是随机搭建模型产生不规则物体,凸显建模的随机性,对搭建得到不规则物体的顶点集采用凸壳算法进行三角连网,完成随机不规则物体建模,并对模型进行纹理贴图,增强模型的质感。实验证明该算法有良好的操作性。     

基于凸多边形的凸壳算法

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

一种在计算机上生成凸包的算法

在计算机上实现生成凸包的算法很多，笔者设计的这一算法主要是利用了在计算机表示中，任意两个点之间必定是有一定距离的，而数学上两个点之间的距离可以是无限小这一特点。我们总可以在计算机上任意两个点的位置之间插入一个数学上的点，这个点计算机可能无法表示，但它是可以被计算的。利用这一特点设计了本算法。     

Computing the Level Set Convex Hull

Quasiconvex (QC) functions are functions whose level sets are convex. The quasiconvex envelope (QCE) of a given function, g, is the maximal QC function below g. The QCE provides a level set representation for the convex hull of every level set of a given function. We present a nonlocal line solver for computing the QCE of a given function. The algorithm is based on solving the one dimensional problem on lines, which can be done by a fast marching or sweeping method. Convergence of the algorithm is established.     

Projective Evolution of Plane Curves

We show that projectively invariant evolution operators have unavoidable singularities. In particular, we see that there exists no non-singular projective evolution operator well-defined over straight lines nor conics.     

核最近邻凸包分类算法

为了增强最近邻凸包分类器的非线性分类能力,提出了基于核函数方法的最近邻凸包分类算法。该算法首先利用核函数方法将输入空间映射到高维特征空间,然后在高维特征空间采用最近邻凸包分类器对样本进行分类。最近邻凸包分类器是一类以测试点到各类别凸包的距离为相似性度量,并按最近邻原则归类的分类算法。人脸识别实验结果证实,这种核函数方法与最近邻凸包分类算法的融合是可行的和有效的。     

The Implementation of a 2D Convex Hull Algorithm Using Perturbation

This paper discusses the problem of geometric degeneracies and outlines possible solutions when converting geometric algorithms into practice. It concentrates on the application of one of the suggested solutions, a perturbation technique, to a 2D convex hull program. An outline of the relevant theory and its conversion into practice is given. Experimental results are presented and discussed.     

一个改进的简单多边形凸包算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。该文通过给出反例，证明文献[4]提出的简单多边形凸包的双动线检测算法不能正确求出任意多边形的凸包，并分析了其缺点，提出了一个改进的算法。改进的算法解决了线性算法所不能解决的自交问题，且实现简单。     

一种改进的实时凸壳算法

凸壳问题是计算机图形学、图像处理、模式识别等众多领域中的一个基本问题。正切线算法需对新加入的实时点进行实时编号,本文实现了对新加入点的自动编号,且增加一个实时点最多只需对2个单调段进行计算,提高了运算效率,在最坏情况下时间复杂度为。     

最大似然估计ROC凸包曲线算法

采用列联表表示特定阈值下入侵检测系统(IDS)的性能,使用ROC曲线对不同阈值下IDS的总体性能进行评估。在实际应用中,基于样本数据集,通过计算几何的方式得到ROC凸包曲线(ROCCH)。为降低ROCCH的计算复杂度,在曲线下面积(AUC)最大似然估计的条件下,通过保序回归得到最大似然估计ROC曲线(MLE-ROC)算法。实验表明,MLE-ROC算法在降低计算复杂度的同时提高了AUC的近似程度。     

On Shape of Plane Elastic Curves

We study shapes of planar arcs and closed contours modeled on elastic curves obtained by bending, stretching or compressing line segments non-uniformly along their extensions. Shapes are represented as elements of a quotient space of curves obtained by identifying those that differ by shape-preserving transformations. The elastic properties of the curves are encoded in Riemannian metrics on these spaces. Geodesics in shape spaces are used to quantify shape divergence and to develop morphing techniques. The shape spaces and metrics constructed are novel and offer an environment for the study of shape statistics. Elasticity leads to shape correspondences and deformations that are more natural and intuitive than those obtained in several existing models. Applications of shape geodesics to the definition and calculation of mean shapes and to the development of shape clustering techniques are also investigated.     

Normal Parametrizations of Algebraic Plane Curves

In this paper we present a theoretical and algorithmic analysis on the normality of rational parametrizations of algebraic plane curves over arbitrary fields of characteristic zero. If the field is algebraically closed we give an algorithm to decide whether a parametrization is proper and, if not, a normal parametrization is computed. If the field is not algebraically closed the problem is more complicated, and a degenerated situation may appear. We classify the degenerations in strong and weak degenerations, and an algorithm to decide this phenomenon is derived. Furthermore, we prove that if the parametrization is strongly degenerated then the curve cannot be normally parametrized, but weak degenerations can be resolved, and an algorithm to reparametrize the input weakly degenerated parametrization into a non-degenerated one is given. In addition, we show how these results can be applied and improved to the case of real rational curves. In this case, we present an algorithm that decides whether a given real parametrization can be normally parametrized over the reals, and that computes such a parametrization if it exists.     

Planar Convex Hull Algorithms in Theory and Practice

Sequential and parallel planar convex hull algorithms, their applications and some of the problems encountered on implementations are described. Details of Pascal implementations are given for three of the sequential algorithms: Graham's, Floyd-Eddy and the Approximation method. The programs are compared experimentally.     

Convex Hull Ensemble Machine for Regression and Classification

We propose a new ensemble algorithm called Convex Hull Ensemble Machine (CHEM). CHEM in Hilbert space is first developed and modified for regression and classification problems. We prove that the ensemble model converges to the optimal model in Hilbert space under regularity conditions. Empirical studies reveal that, for classification problems, CHEM has a prediction accuracy similar to that of boosting, but CHEM is much more robust with respect to output noise and never overfits datasets even when boosting does. For regression problems, CHEM is competitive with other ensemble methods such as gradient boosting and bagging.     

Fisher鉴别特征的最近邻凸包分类

基于Fisher准则的特征提取方法是模式识别技术的重要分支,其中,Foley-Sammon变换和具有统计不相关性的最佳鉴别变换是这一技术典型代表,本文将它们与一种新型分类器一最近邻凸包分类器相结合,从而实现Fisher鉴别特征的有效分类。最近邻凸包分类器是一类以测试样本点到各类训练集生成类别凸包的距离为分类判别依据的模式分类新方法,具有非线性性,无参性,多类别适用性等特点。实验证实了本文方法的有效性。     

有理参数曲线的近似恰当化

有理参数曲线的恰当性是曲线的基本性质,虽然其在有理系数情况下已经有完备的结果,但在工程和CAGD应用中常常得到带误差浮点系数的有理表示形式.为此,讨论了这类有误差的有理参数曲线,定义了近似非恰当参数形式和近似非恰当指数,并通过半代数系统计算近似非恰当指数;在给出近似非恰当指数的同时,得到近似最大公因子.最后基于最小二乘法给出近似参数有理变换表示,计算出曲线恰当的近似有理参数表示.