一种新的求平面点凸壳算法

本文提出了一种新的求平面点凸壳的算法。本算法的基本思想是:首先找出给定的二维点集的所有最外点(即Xmax,Ymax,Xmin,Ymin对应的点),则这些最外点肯定是凸壳上的点。再利用四个最外点将二维点集划分为四个相对的子区域。最后在这四个子区间内分别从一个最外点开始寻找与基准线夹角最大的点,迭代查找,并不断缩小查找区域,直至四个子区间都查找完毕。     

求平面点集凸壳的一个最优算法

本文提出了一个求平面点集凸壳的格雷厄姆方法的一个改进算法。算法首先按照格雷厄姆方法将点集中的点进行分类，将分类后的点连成一个特殊的简单多边形，然后删去简单多边形的单个凹点、连续凹点，产生新的简单多边形，再删去新简单多边形的单个凹点及连续凹点，循环往复，最后得到的凸多边形即为点集凸壳的边界。本算法理论严密，易于理解，易于实现，时间复杂性也是。     

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

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

一种改进的实时凸壳算法

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

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

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

平面点集凸壳的快速算法

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

基于凸壳的高密度点集物碰撞检测算法

提出了一种基于凸壳的高密度点集物碰撞检测算法。根据高密度点集物紧密性好的特点,设计了一种快速的凸壳算法;当极值比较不能确定待检测点集物未碰撞时,用该算法计算待检测点集物的凸壳,并对凸壳进行求交运算,若不相交,两点集物未发生碰撞,否则在两凸壳的交集区域中寻找碰撞点集。算法简单、高效、可靠,在教育、国防、艺术等方面具有一定应用价值。     

求平面点集最近点对的一个改进算法

文中对Ｐｒｅｐａｒａｔａ和Ｓｈａｍｏｓ在１９８５年提出的求平面点集最近点对的一个分治算法进行了改进，使原来 归并时最多需计处３ｎ对点对的距离，改进的为最多只需计算２ｎ     

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

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

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

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

On the approximation of convex hulls of finite grid point sets

The outer or inner approximation of the convex hull of a grid point set may be used to speed up the feature extraction process in a shape analysis system. Some properties of these approximations are given.     

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

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

平面点集凸包的并行算法研究

提出了在基于有序简单多边形的平面点集凸包快速求取算法基础上改进的并行算法，该算法的时间复杂度达到了O（n）。在PC机互连构成的机群（COW）并行计算系统上以消息传递方式执行该算法，通过与原串行算法对比验证了该算法的可行性、正确性和高效性。     

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

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

Graham算法求解凸包问题中的隐私保护

凸包问题是构造其他几何形体的有效工具。保护私有信息的凸包求解问题是一个特殊的安全多方计算问题。基于安全多方计算的基础协议,设计了一个保护私有信息的凸包求解协议,解决了基于隐私保护的凸包求解问题,并讨论和分析了其安全性和正确性。     

Computing simple-path convex hulls in hypergraphs

In a connected hypergraph a vertex set X is simple-path convex (sp-convex, for short) if either |X|?1 or X contains every vertex on every simple path between two vertices in X (Faber and Jamison, 1986 [7]), and the sp-convex hull of a vertex set X is the minimal superset of X that is sp-convex. In this paper, we give a polynomial algorithm to compute sp-convex hulls in an arbitrary hypergraph.     

Clipping algorithms for solving the nearest point problem over reduced convex hulls

The nearest point problem (NPP), i.e., finding the closest points between two disjoint convex hulls, has two classical solutions, the Gilbert-Schlesinger-Kozinec (GSK) and Mitchell-Dem’yanov-Malozemov (MDM) algorithms. When the convex hulls do intersect, NPP has to be stated in terms of reduced convex hulls (RCHs), made up of convex pattern combinations whose coefficients are bound by a μ<1 value and that are disjoint for suitable μ. The GSK and MDM methods have recently been extended to solve NPP for RCHs using the particular structure of the extreme points of a RCH. While effective, their reliance on extreme points may make them computationally costly, particularly when applied in a kernel setting. In this work we propose an alternative clipped extension of classical MDM that results in a simpler algorithm with the same classification accuracy than that of the extensions already mentioned, but also with a much faster numerical convergence.     

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

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