平面点集凸壳的快速算法

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

Improvements to algorithms for computing the Minkowski sum of 3-polytopes

A Minkowski sum is a geometric operation that is equivalent either to the vector additions of all points in two operands or to the sweeping of one operand around the profile of the other without changing the relative orientation. Applications of Minkowski sums are found in computer graphics, robotics, spatial planning, and CAD. This paper presents two algorithms for computing Minkowski sum of convex polyhedron in three space (3-polytopes). Both algorithms are improvements on current ones found in the literature. One is based on convex hulls and the other on slope diagrams. The original convex hull based Minkowski algorithm is costly, while the original slope diagram based algorithms require the operation of stereographic projection from 3D to 2D for merging the slope diagrams of the two operands. Implementation of stereographic projection is complicated which increases the computation time and reduces the accuracy of the geometric information that is needed for constructing the resultant solid. This paper reports on improvements that have been made to these two algorithms and their implementation. These improvements include using vector operations to find the interrelations between points, arcs and regions on a unit sphere for the slope diagram algorithm, and addition of a pre-sorting procedure before constructing convex hull for convex hull based Minkowski sum algorithm. With these improvements, the computation time and complexity for both algorithms have been reduced significantly, and the computational accuracy of the slope diagram algorithm has been improved. This paper also compares these two algorithms to each other and to their original counterparts. The potential for extending these algorithms to higher dimensions is briefly discussed.     

A fast convex hull algorithm with maximum inscribed circle affine transformation

This paper presents a fast convex hull algorithm for a large point set. The algorithm imitates the procedure of human visual attention derived in a psychological experiment. The merit of human visual attention is to neglect most inner points directly. The proposed algorithm achieves a significant saving in time and space in comparison with the two best convex hull algorithms mentioned in a latest review proposed by Chadnov and Skvortsov in 2004. Furthermore, we propose to use an affine transformation to solve the narrow shape problem for computing the convex hull faster.     

基于超球外壳的凸包改进算法

根据凸集中只有最外围的点才有可能是凸点而中心附近的点不可能成为凸点的特性,提出了一种基于超球外壳的凸包改进算法。首先选取给定凸集点的中心,计算所有点与该中心的距离,并对该距离进行归一化处理,使所有的点都映射到一个单位超球体内;其次,选取合适的参数,提取单位超球体的外壳,用外壳中的点构造其凸包。     

Efficient geometric algorithms on the EREW PRAM

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM     

基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

利用正负划分性求平面点集凸包的最优算法

求平面点集的凸包是计算几何的一个基本算法。目前的算法较多,但这些算法均较复杂,为降低算法复杂性,首先从分析直线的正负划分性入手,利用其来对平面点集进行分类,以简化点到直线的距离计算;然后进一步详细地给出了一种改进的求平面任意散乱点集凸包的新算法。该算法在搜索凸包时,较目前流行的算法中所采用的前瞻回溯法既简单又速度快,该算法较传统的算法更是优越,尤其他不需要计算角度和欧氏距离。结果表明,利用该算法求任意平面散乱点集凸包不仅计算准确,而且计算过程中仅仅用到加、减、乘、比较运算。这样不仅使算法的每一步骤的时间复杂性大大降低,而且也使得整个算法的时间复杂性大大降低。经过分析,该算法也是一个最优的算法。     

Geometric algorithms for digitized pictures on a mesh-connected computer

Although mesh-connected computers are used almost exclusively for low-level local image processing, they are also suitable for higher level image processing tasks. We illustrate this by presenting new optimal (in the O-notational sense) algorithms for computing several geometric properties of figures. For example, given a black/white picture stored one pixel per processing element in an n × n mesh-connected computer, we give ?(n) time algorithms for determining the extreme points of the convex hull of each component, for deciding if the convex hull of each component contains pixels that are not members of the component, for deciding if two sets of processors are linearly separable, for deciding if each component is convex, for determining the distance to the nearest neighboring component of each component, for determining internal distances in each component, for counting and marking minimal internal paths in each component, for computing the external diameter of each component, for solving the largest empty circle problem, for determining internal diameters of components without holes, and for solving the all-points farthest point problem. Previous mesh-connected computer algorithms for these problems were either nonexistent or had worst case times of ?(n2). Since any serial computer has a best case time of ?(n2) when processing an n × n image, our algorithms show that the mesh-connected computer provides significantly better solutions to these problems.     

An efficient algorithm for minimum zone flatness based on the computation of the largest inscribed ball in a symmetric polyhedron

This paper presents an algorithm for the minimum zone flatness tolerance of a finite point set, which is defined to be the minimum Euclidean distance between two parallel planes that sandwich the point set. The algorithm is based on the observation that the flatness tolerance is equal to the radius of the largest inscribed ball in the convex hull of the Minkowski difference of the point set and itself, which is a symmetric polyhedron with respect to the origin. Then, an iterative procedure is developed to adaptively grow another symmetric polyhedron inside the convex hull of the Minkowski difference such that the radius of its inscribed ball monotonically increases and converges to the flatness tolerance. The algorithm is guaranteed to compute the globally minimum solution within finite iterations. Moreover, there is no need to compute the Minkowski difference or the convex hull of the point set, so the proposed algorithm is very fast and takes only several milliseconds for hundreds of thousands of points on a normal computer, such as a desktop computer with an Intel Xeon 3.70 GHz CPU and 16GB RAM used in this work.     

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.     

人体重心动摇轨迹包络面积的快速算法

传统的人体重心动摇轨迹包络面积计算方法是先确定包络所有点的凸包形状,再计算凸包的面积,其最优时间复杂度接近O(nlbn)。针对上述问题给出一种近似凸包计算方法,通过计算点集在不同旋转角度下的坐标,查找X轴和Y轴的最大最小极值点,快速标定构成凸包点,确定凸包形状。算法的时间复杂度接近于O(n)。实际应用证明,该算法能满足精度要求,提高人体重心动摇轨迹包络面积计算速度。     

On the ultimate convex hull algorithm in practice

Kirkpatrick and Seidel [13,14] recently proposed an algorithm for computing the convex hull of n points in the plane that runs in O(n log h) worst case time, where h denotes the number of points on the convex hull of the set. Here a modification of their algorithm is proposed that is believed to run in O(n) expected time for many reasonable distributions of points. The above O(n log h) algorithmsare experimentally compared to the O(n log n) ‘throw-away’ algorithms of Akl, Devroye and Toussaint [2, 8, 20]. The results suggest that although the O(n Log h) algorithms may be the ‘ultimate’ ones in theory, they are of little practical value from the point of view of running time.     

平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法，第一个算法是利用平面扫描的思想，当扫描线达到事件点时，处理事件点，即将事件点与已被扫描的某些点连接，这样便将已扫描的区域三角剖分，当扫描线达到最左边的事件点时，处理该事件点，就完成了平面线段集的三角剖分，第二个算法基于逐层计算凸壳，并将凸壳改变为多边形，这样便便形成嵌套的多边形层，这些多边形覆盖线段集凸壳内的区域，然后三角剖分每个多边形，即完成平面线段集的三角剖分，两个算法的时间复杂性分别为O（nlogn),O(mnlogn)，其中n为线段集中线估的数目，m为凸壳的层数。     

Efficient planar convex hull algorithm

A new algorithm for computing the convex hull of a planar set of points is presented. The method of determining the set of suitable candidates is compared with previous algorithms. The algorithm is also compared with other algorithms in terms of running time and storage requirements, and experiments indicate that it is at least as good in terms of space and generally better in terms of running time.     

改进的三维点集凸包求取算法

为提高三维点集凸包的求取效率,提出充分利用凸包极值点和性质改进的三维点集凸包求取算法.首先,求出三维点集中的极值点,并由它们形成初步凸包;其次,根据初步凸包与点的位置关系,排除其内部点;最后,依次考察其外部点,求出符合要求的点集、棱边集和面集,并对凸包进行扩展,得到凸包的点集、棱边集和面集.与普通算法进行时间的复杂度分析比较及实验表明,该算法效率较高.     

Spark平台下的凸包问题研究

随着移动互联网时代的到来,越来越多的含地理位置信息的空间数据需要处理,如何在海量的空间数据中进行常见的几何查询成为一个挑战,凸包问题因其在模式识别、图像处理、统计学、地理信息系统、博弈论、图论等领域中被广泛应用成为近些年研究的一个热点。凸包问题的研究始于单机版的算法,进而过渡到Hadoop等基于硬盘的分布式系统,但是受限于单节点的计算存储能力的瓶颈以及Hadoop平台基于硬盘的特性,其计算性能尚不能达到人们的在线实时计算的需求。研究基于内存的分布式计算框架Spark下的凸包问题,给出基于Spark平台的凸包查询整体框架,框架从查询接口、语法解析和物理执行等多方面结合SparkSQL引擎。随后,给出基于Andrew单调链算法的单机算法CHStand,分析单机算法并行度上的问题后,提出基于Spark的CHSpark算法,进一步优化算法并提出一种Spark平台下的优化算法CHGeom。通过实验对比说明三种算法的相对性能提升,实验发现Spark平台下的解决方案相对传统的单机平台下的解决方案有着较大的性能提升,所提算法具有良好的拓展性和广泛的实际应用价值。     

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

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

论二维点集或线段集凸壳生成算法改进与优化的同构化方向

本文指出了迄今为止的现行二维点集或线段集（包括：多边形、封闭折线、半封闭折线、开放线段集等）凸壳生成算法的共同弱点；提出了可改进与优化凸壳算法的同构化凸壳构造基本定理。进而，基于同构化凸壳构造基本定理，阐明了有限二维点集或线段集凸壳生成算法改进与优化的同构化方向，应当是：第一，使凸壳极点（或称顶点）分布域极小化，即让包含凸壳极点的判定区域尽可能小；使极点判定对象直接化，即让所判定对象尽可能接近当前所寻极点。第二，尽力对有可改造潜力的优秀串行凸壳算法施以并行化改造和创新。     

一种改进的构建凸包的分治算法

本文为构建离散点的凸包提出了一种改进的分治算法，它在查找每一个凸包顶点的同时，通过去除若干非凸包顶点来迅速减小问题的规模。本文对该算法的正确性给出了严格的证明。     

一种高效的平面点集凸包递归算法

凸包是计算几何的基本结构, 在许多图形图像相关领域得到了广泛应用. 本文提出了一种简单快速的平面点集凸包算法, 使用了主成分分析法(Principle component analysis, PCA)对点集进行预处理, 并研究了适用的排序规则和凸包边缘点判定原则. 该算法已成功应用于一光栅投影三维形貌快速测量系统,对相位干涉图中密集残留点所形成的最小凸包进行提取. 系统将提取的凸包区域进行掩码标记, 从而避免密集残留点造成相位展开错误, 保证了三维形貌重构的准确性. 实验结果表明, 该算法准确可靠, 并且运行效率较高.