基于凸壳技术求解二维点集对称轴的方法

通过物体的对称性,人们可以推断物体的结构并估计它的形状,从而恢复被遮挡或丢失部分的信息。针对二维点集,提出了一种新的求解信息完整和不完整点集对称轴的方法。首先根据凸壳算法求出点集的凸壳,对于信息完整点集,点集的对称轴必是凸壳的对称轴,因此可以借助求解凸壳的对称轴来求解点集的对称轴;对于信息不完整点集,当遗失的点为凸壳内部点时,点集的对称轴也必为凸壳对称轴,当凸壳上的点有遗失时,则可通过求凸壳边的中垂线,以及长度相等两邻边组成角的角平分线来确定点集的对称轴。该方法解决了现有算法只能求解封闭和信息完整图形的对称轴的不足,实验结果表明该方法是高效、可行的。     

一种平面点集凸壳的快速算法

文章提出了一种对平面离散点集凸壳的快速算法,该算法首先对离散点进行扫描线方式排序,构造初始凸壳,然后把剩下的离散点加入到已有的凸壳中生成新的凸壳.实验表明该算法具有很好的效率.     

海量平面点集凸壳的快速算法

提出并证明了凸壳的城堡定理，设计并实现了城墙的快速搜索算法。该算法可以作为海量平面点集凸壳计算的数据预处理过程。在计算海量平面点集凸壳时，可以先用该算法从点集中筛选出一小部分点作为候选点集，再用其他凸壳算法就可以很快地计算出整个点集的凸壳。     

计算平面点集凸壳的两种新方法

平面上有限点集的凸壳在土木工程及其它许多领域均有很多重要应用,计算几何中的很多应用问题都与凸壳有关.现有多种求平面上点集凸壳的方法,但这些方法要么算法非常复杂,要么编码及实现非常困难.介绍了两种求平面点集凸壳的新方法,它们具有算法思想简单且易于编码实现的优点.     

平面点集凸壳的一种近似算法

提出了一种计算海量平面点集凸壳的快速近似算法——点集坐标旋转法(PSCR)。该算法采用点集不断旋转并求X(Y)坐标极值的方法得到平面点集的近似凸壳。它充分利用了成熟的数据库技术,能够在比较短的时间内计算出海量平面点集的近似凸壳。它不需要空间索引的支持,并能获得比较理想的近似效果。     

求平面多边形集凸壳的方法

提出一种计算平面多边形集凸壳的快速算法。将多边形集的凸壳根据极值点划分为右上、左上、左下、右下四段,同时对集合中多边形利用其极值点提取右上、左上、左下、右下四个点列段,凸壳的每一段仅受多边形同一类点列段的影响。根据多边形集合的极值点确定四个矩形区域对四类点列段进行筛选,再按给定规则在矩形区域中进行初始找点,可求出四段凸壳初始点列,它们按顺序可确定一平面多边形,求出到此多边形的凸壳即为所求多边形集的凸壳。算法通过分段、分类、筛选等措施提高了计算效率,并且易于实现,其时间复杂度为O（N）。     

平面点集凸壳的快速算法

提出一种计算平面点集凸壳的快速算法。利用极值点划分出四个矩形,它们包含了所有凸壳顶点,通过对矩形中的点进行扫描,排除明显不是凸壳顶点的点,剩余的点构成一个简单多边形。再利用极点顺序法判断多边形顶点的凹凸性并删除所出现的凹顶点,最终得到一个凸多边形即为点集的凸壳。整个算法简洁明了,避免了乘法运算（除最坏情况外）,从而节省计算时间。     

平面海量散乱点集凸壳算法

凸壳作为计算几何的一种基本的结构,对GIS的数据分析有着重要作用。在分析传统的凸壳算法的基础上,提出新的凸壳算法,即金字塔算法。同时采用3种快速算法提高执行效率。通过大量实验数据对比说明,算法对求平面海量散乱点集的凸壳非常有效,点集为10^7数量级的执行时间在主频为2．00GHz计算机上仅为3s～4s。     

基于栅格划分构建平面点集凸壳的算法研究

提出了一个构建平面点集凸壳的新算法.该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳.由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率.在最坏情况下该算法的时间复杂度为O(NlogN).     

基于栅格划分构建平面点集凸壳的算法研究

提出了一个构建平面点集凸壳的新算法。该算法用栅格阵列将待处理点集划分成若干个子集,这样凸壳可以由部分位于点集边缘的子集确定;然后按逆时针顺序逐步处理这些子集,得到一个包含待处理点集的简单多边形,删除凹顶点后就得到待处理点集的凸壳。由于只对点集边缘的点进行局部处理,从而提高了构建凸壳的效率。在最坏情况下该算法的时间复杂度为O(NlogN)。     

刚体在软体对象环境中的碰撞检测的研究

刚体在软体对象环境中的碰撞检测在虚拟现实的研究领域具有很大的普遍性 ,但以往的研究较少 .文中给出了一种基于固定方向凸包 (FDH)包围盒树的碰撞检测方法 ,并着重论述了利用线性规划的思想以解决刚体自由运动后包围盒树的更新以及通过一种自底向上的方法解决软体对象变形后包围盒树的更新 .实验表明 ,该方法不仅能较好地解决刚体间的碰撞检测 ,而且能有效地解决刚体与软体间的碰撞检测     

Finding the intersection of n half-spaces in time O(nlogn)

Given a set of n half-spaces in three dimensional space, we develop an algorithm for finding their common intersection in time O(n log n). The intersection, if nonempty, is presented as a convex polyhedron. The algorithm is summarized as follows: (i) the half-spaces are placed in two sets depending upon whether they contain or do not contain the origin; (ii) the half-spaces in each of these sets are dualized to points, and the convex hulls of the dualized sets are obtained in time O(n log n); (iii) since the half-space intersection is nonempty if and only if these two convex hulls are disjoint, a separating plane is found, also in time O(n log n); (iv) after applying a linear spatial transformation which maps the separating plane to infinity, the convex hull of the union of the two transformed convex hulls is the transformed intersection of the half-spaces. Since the letter can be found in time O(n), the overall running time of the procedure is O(n log n). A significant consequence of this result is that a three-variable linear, or convex, programming problem can be asymptotically solved faster than by the Simplex algorithm, in the worst case.     

Two parallel algorithms for the convex hull problem in a two dimensional space

Two parallel algorithms for determining the convex hull of a set of data points in two dimensional space are presented. Both are suitable for MIMD parallel systems. The first is based on the strategy of divide-and-conquer, in which some simplest convex-hulls are generated first and then the final convex hull of all points is achieved by the processes of merging 2 sub-convex hulls. The second algorithm is by the process of picking up the points that are necessarily in the convex hull and discarding the points that are definitely not in the convex hull. Experimental results on a MIMD parallel system of 4 processors are analysed and presented.     

连接不相交线段成简单多边形(链)的算法及其实现

提出一个如何连接平面上n条线段与一个简单多边形或者简单多边形链的实际问题，并证明了连接平面上线段集S成一简单多边形链的一个充分条件——S中有一条线段连接凸壳CH（S）中不相领顶点。提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先农层计算线段集S的凸壳，并将这些凸壳改变为简单多边形；然后计算各多边形之间的交点，进而删去这些交点；最后俣并若干个简单多边形为一个简单多边形。当S中线段数目n较大时，用分治思想设计分治算法，较好地求解了这个问题。利用计算机求解这个问题具有实际应用价值。     

基于类边界壳向量的快速SVM增量学习算法

为进一步提高SVM增量训练的速度,在有效保留含有重要分类信息的历史样本的基础上,对当前增量训练样本集进行了约简,提出了一种基于类边界壳向量的快速SVM增量学习算法,定义了类边界壳向量。算法中增量训练样本集由壳向量集和新增样本集构成,在每一次增量训练过程中,首先从几何角度出发求出当前训练样本集的壳向量,然后利用中心距离比值法选择出类边界壳向量后进行增量SVM训练。分别使用人工数据集和UCI标准数据库中的数据进行了实验,结果表明了方法的有效性。     

Convex sets as prototypes for classifying patterns

We propose a general framework for nonparametric classification of multi-dimensional numerical patterns. Given training points for each class, it builds a set cover with convex sets each of which contains some training points of the class but no points of the other classes. Each convex set has thus an associated class label, and classification of a query point is made to the class of the convex set such that the projection of the query point onto its boundary is minimal. In this sense, the convex sets of a class are regarded as “prototypes” for that class. We then apply this framework to two special types of convex sets, minimum enclosing balls and convex hulls, giving algorithms for constructing a set cover with them and for computing the projection length onto their boundaries. For convex hulls, we also give a method for implicitly evaluating whether a point is contained in a convex hull, which can avoid computational difficulty for explicit construction of convex hulls in high-dimensional space.     

基于样本选择的最近邻凸包分类器

最近邻凸包分类算法是一种以测试点到各类别样本凸包的距离为分类度量的最近邻分类算法。然而,该算法的凸二次规划问题优化求解的较高的计算复杂度限制了其在较大规模数据集上的应用。本文提出一种样本选择方法——子类凸包生长法。通过迭代,选择距离选出样本凸包最远的点,直到满足终止条件,从而实现数据集的有效约简。ORL数据库和MIT-CBCL人脸识别training-synthetic库上的实验结果表明,子类凸包生长法选出的少量样本生成的凸包能够很好的表征训练集,在不降低最近邻凸包分类器性能的同时,使得算法的计算速度大为提高。     

判断两个凸多面体是否相交的一个快速算法

在机器人路径规划中,碰撞检测算法占有十分重要的地位.在智能机器人仿真系统中,碰撞检测耗用的时间在整个路径规划过程所用时间中占有相当大的比例.于是,如何进一步提高碰撞检测的速度在智能机器人路径规划系统中就起到了非常关键的作用.而碰撞检测问题最终转化为判断三维空间中两个凸多面体是否相交的问题.就这一问题,给出了一种新的算法,其思想是取一个从一个凸多面体指向另一个多面体的向量,根据两个多面体中的面与这一向量的相对位置关系来寻找相交的平面.即有两个多面体的交点位于这一平面,若能找到一个相交平面则可以断定两个多面体     

Bezier surface/surface intersection

The computational requirements and accuracy of two methods for finding the intersection of Bezier surfaces are examined. In both methods, the existence of an intersection curve is confirmed by using the convex hull property of such surfaces. The first method evaluates the intersection by recursive subdivision of two patches with overlapping hulls. The second method detects a point on the intersection curve and then incrementally traces the intersection in the parametric spaces of the two surfaces. With both methods, the intersection of a pair of first-order planar patches must be solved analytically. The intersection is approximated by first-order Bezier patches in the first case and by planar triangles in the second. Overall, the method of incremental tracing is shown to give more accurate results than the method of recursive subdivision     

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

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