Contributing vertices-based Minkowski sum computation of convex polyhedra

Minkowski sum is an important operation. It is used in many domains such as: computer-aided design, robotics, spatial planning, mathematical morphology, and image processing. We propose a novel algorithm, named the Contributing Vertices-based Minkowski Sum (CVMS) algorithm for the computation of the Minkowski sum of convex polyhedra. The CVMS algorithm allows to easily obtain all the facets of the Minkowski sum polyhedron only by examining the contributing vertices—a concept we introduce in this work, for each input facet. We exploit the concept of contributing vertices to propose the Enhanced and Simplified Slope Diagram-based Minkowski Sum (ESSDMS) algorithm, a slope diagram-based Minkowski sum algorithm sharing some common points with the approach proposed by Wu et al. [Wu Y, Shah J, Davidson J. Improvements to algorithms for computing the Minkowski sum of 3-polytopes. Comput Aided Des. 2003; 35(13): 1181-92]. The ESSDMS algorithm does not embed input polyhedra on the unit sphere and does not need to perform stereographic projections. Moreover, the use of contributing vertices brings up more simplifications and improves the overall performance. The implementations for the mentioned algorithms are straightforward, use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library. More examples and results of the CVMS algorithm for several convex polyhedra can be found at http://liris.cnrs.fr/hichem.barki/mksum/CVMS-convex.     

Algorithm to calculate the Minkowski sums of 3-polytopes based on normal fans

Prompted by the development of algorithms for analysing geometric tolerancing, this article describes a method to determine the Minkowski sum for 3-dimensional polytopes. This method is based exclusively on intersection operations on normal cones, using the properties of the normal fan of a Minkowski sum obtained by common refinement of the normal fans of the operands. It can be used to determine from which vertices of the operands the vertices of the Minkowski sum derive. It is also possible to determine to which facets of the operands each facet of the Minkowski sum is oriented. The basic properties of the algorithms can be applied to n-polytopes.First, the main properties of the duality of normal cones and primal cones associated with the vertices of a polytope are described. Next, the properties of normal fans are applied to define the vertices and facets of the Minkowski sum of two polytopes. An algorithm is proposed, which generalises the method. Lastly, there is a discussion of the features of this algorithm, developed using the OpenCascade environment.     

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.     

Map segmentation for geospatial data mining through generalized higher-order Voronoi diagrams with sequential scan algorithms

Segmentation is one popular method for geospatial data mining. We propose efficient and effective sequential-scan algorithms for higher-order Voronoi diagram districting. We extend the distance transform algorithm to include complex primitives (point, line, and area), Minkowski metrics, different weights and obstacles for higher-order Voronoi diagrams. The algorithm implementation is explained along with efficiencies and error. Finally, a case study based on trade area modeling is described to demonstrate the advantages of our proposed algorithms.     

基于双群双域四向水平倾角最小化圈绕的凸壳并行新算法

本文针对现行凸壳算法(诸如:串行类的卷包裹凸壳算法、格雷厄姆凸壳算法等,并行类的折半分治凸壳算 法、快速凸壳算法等)效率不高的缺点,根据同构化凸壳构造基本定理,利用工作站机群优点,提出了效率更高的双群(即:其机群分为2个子机群)、双域(即:其数据分布域分为2个子分布域)、四向(即:其每个子分布域内凸壳顶点的寻找方向均各自为顺时针、逆时针2个寻找方向)水平倾角最小化圈绕的凸壳并行新算法.     

基于方向包围盒投影转换的轮廓线拼接算法

基于轮廓线拼接算法重构三维模型时,由于拼接对象的复杂性,任何一种拼接方法都不能完全涵盖所有情况。为此,提出一种基于方向包围盒(OBB)投影转换的轮廓线拼接算法：首先判断多边形的顶点凹凸性,对于凹顶点,将其转换到对应的凸包上;然后计算凸包的方向包围盒,旋转平移矩形包围盒,并求包围盒内接椭圆,将每个顶点都按比例投影此椭圆上;基于投影后的点进行轮廓线拼接,寻找相邻轮廓线顶点之间的对应关系;最后还原实际坐标,进行原始模型的三维重构。     

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

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

基于代数视角的凸壳及其特性同构化研究

现行凸壳算法通常是基于凸壳几何特性的视角来求解凸壳顶点,主要适用于求解低维几何空间凸壳问题.因高维空间凸壳的几何关系极为复杂,故研究、设计、提高求解高维几何空间凸壳的算法效率难度较大.考虑到几何与代数有着天然的本质联系,进而基于代数视角来研究凸壳问题,并给出了凸壳顶点的代数定义,研究了凸壳顶点若干代数性质;从而,为探索从代数视度来研究和设计求解高维几何空间凸壳算法提供某些基础理论与创新思路.     

海量数据凸壳快速优化算法研究

分析描述加速凸壳算法的基本思想.在分析传统的加速凸壳算法的基础上,根据加速算法剔除内点的时机将加速算法分成静态加速算法和动态加算法.同时阐述了动态加速算法的应用条件,并将动态加速算法应于金字塔凸壳算法之中.通过大量实验数据对比说明动态加速算法对提高平面海量散乱点集的生成速度非常有效。     

Continuous penetration depth computation for rigid models using dynamic Minkowski sums

We present a novel, real-time algorithm for computing the continuous penetration depth (CPD) between two interpenetrating rigid models bounded by triangle meshes. Our algorithm guarantees gradient continuity for the penetration depth (PD) results, unlike conventional penetration depth (PD) algorithms that may have directional discontinuity due to the Euclidean projection operator involved with PD computation. Moreover, unlike prior CPD algorithms, our algorithm is able to handle an orientation change in the underlying model and deal with a topologically-complicated model with holes. Given two intersecting models, we interpolate tangent planes continuously on the boundary of the Minkowski sums between the models and find the closest point on the boundary using Phong projection. Given the high complexity of computing the Minkowski sums for polygonal models in 3D, our algorithm estimates a solution subspace for CPD and dynamically constructs and updates the Minkowski sums only locally in the subspace. We implemented our algorithm on a standard PC platform and tested its performance in terms of speed and continuity using various benchmarks of complicated rigid models, and demonstrated that our algorithm can compute CPD for general polygonal models consisting of tens of thousands of triangles with a hole in a few milli-seconds while guaranteeing the continuity of PD gradient. Moreover, our algorithm can compute more optimal PD values than a state-of-the-art PD algorithm due to the dynamic Minkowski sum computation.     

基于当前基线垂直落差最大化的凸壳递归新算法

本文依据同构化凸壳构造基本定理,率先发现并证明了凸壳顶点的分布域性态与垂直落差特性;首次给出当前基线垂直落差最大化的二维点集凸壳算法构造创新思想,提出了比迄今最优秀凸壳算法之一的快凸壳算法效率更高的、基于当前垂直落差最大化的凸壳递归新算法,指出了它具有进一步改造为并行算法的潜力.该新算法的主要特点是:1)找出初始点分布域的所有最外点(其个数,下限为3,上限为8),作为所求凸壳的初始顶点.2)删除这些最外点所构成最外点凸多边形(其边数,下限为3,上限为8)所覆盖的凸壳内点后,把所剩点分布域,分为若干个初始子分布域(其个数,下限为0,上限为4).3) ①对各个非空初始子分布域顺次调用本新算法的递归过程子算法,分别在各初始子分布域中找出其当前基线垂直落差最大点(其个数,下限为1,上限为2),并作为其各初始子分布域内凸壳的新顶点;②删除当前基线与垂直落差最大点所构成基线凸多边形(其边数,下限为3,上限为4)内的凸壳内点后,把所剩点分布域,分为多个更小的子分布域(其个数,下限为0,上限为2);③对各个更小的当前子分布域,分别递归调用过程子算法,以找出其当前基线的垂直落差最大点作为凸壳新顶点.     

Sorting helps for voronoi diagrams

It is well known that, using standard models of computation, Ω(n logn) time is required to build a Voronoi diagram forn point sites. This follows from the fact that a Voronoi diagram algorithm can be used to sort. However, if the sites are sorted before we start, can the Voronoi diagram be built any faster? We show that for certain interesting, although nonstandard, types of Voronoi diagrams, sorting helps. These nonstandard types of Voronoi diagrams use a convex distance function instead of the standard Euclidean distance. A convex distance function exists for any convex shape, but the distance functions based on polygons (especially triangles) lead to particularly efficient Voronoi diagram algorithms. Specifically, a Voronoi diagram using a convex distance function based on a triangle can be built inO (n log logn) time after initially sorting then sites twice. Convex distance functions based on other polygons require more initial sorting.     

Range free localization technique under erroneous estimation in wireless sensor networks

Minkowski timespace has the capability to overcome the limited accuracy of L₂-norm based range-free localization methods. This paper proposes the concept of Minkowski triangulation uncertainty (MTU) in wireless sensor networks (WSNs) for localization of unknown target. To set up a localization framework, triangulation uncertainty parameter is defined using Lemma 3.1. A two-stage estimation algorithm is then presented: countLocalized and countAnchor. countLocalized computes the number of localized sensor nodes by leveraging the uncertainty strategy based upon indeterminate independent measurement. countAnchor designates the anchor nodes to triangulate the unknown target by formulating a convex hull model. The convex hull is the Minkowski sum of the actual and projected positions of the two vector node positions. The proposed MTU technique establishes that the number of triangulations formed by Minkowski method is inclusive of the triangulations formed by conventional L₂-norm range of sensor nodes in a WSN. Measurement strategies such as angle, distance and positioning error are compared in the simulation. The said technique links Minkowski space to localization by ensuring efficiency in large target areas and number of nodes in manifolds. Results confirm that the MTU technique is better than the existing models by at least 12%, 50%, 5.5% and 24% in terms of localization ratio, localization error, neighbour anchor nodes and network connectivity, respectively.

     

基于随机投影的快速凸包分类器

传统的基于核函数的分类方法中核矩阵运算复杂度较高,无法满足大规模数据分类的要求.针对这一问题,提出基于随机投影的快速凸包分类器(FCHC-RP).首先,使用随机投影的方法将样本投影到多个二维子空间,并将子空间数据映射到特征空间;其次,根据数据分布的几何特征得到凸包候选集;再次,基于凸包的定义计算出特征空间中的凸包向量;最后,使用与凸包向量对应的原始样本及其权值训练支持向量机.此外,FCHC-RP还适用于不平衡数据的分类问题,根据两类样本的不平衡程度选择不同的参数,可以得到规模相当的两类样本的凸包集,实现训练数据的类别平衡.理论分析和实验结果验证了FCHC-RP在分类性能和训练时间上的优势.     

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.     

基于最大基线倾角智能逼近的凸壳新算法

本文评述了有代表性的折半分治递归凸壳算法，并利用同构化凸壳基本定理提出效率更高的最大倾角智能逼近凸壳新算法。本新算法的同构化特点是：1）找出给定二维点集最外点（指最左、最右、最高、最低点），即其X轴、Y轴坐标值最大、最小的四个初始极点；2）用该初始极点，把原二维点集分布域划分为四个子分布域；3）分别在这四个子分布域中，各基于自身最新所得极点依次动态构造其基线倾角最大的当前极点，并用这些极点作凸边，来逐步智能逼近和最终生成该给定二维点集的凸壳。     

Measurement and calculation of crown projection area and crown volume of individual trees based on 3D laser-scanned point-cloud data

Forest inventory parameters such as crown projection area and crown volume are critical to the study of single-tree biomass and 3D green biomass. The objective of this study is to develop highly precise measurement and calculation methods for crown projection area and volume of single trees based on a terrestrial 3D laser scanning system. A total of 20 sample trees with different species (Pinus tabuliformis, Larix gmelinii, Betula platyphylla, Picea asperata, Fraxinus mandschurica) were selected, and 3D laser scanning system was used to capture the initial point-cloud data of all of the sample trees. A series of processing including point-cloud registration, denoising, and extraction was carried out to obtain the final point-cloud data of single trees. Finally, the proposed improved convex hull algorithms were used to calculate the crown projection area and crown volume of the single trees and compared with the results obtained by the traditional method and the geometrical simulation method. The results indicated that traditional measurement had significant fluctuation compared with the other two methods due to human-induced factors during measurement. The crown projection area (or crown volume) obtained by different methods was strongly correlated, especially for the geometric simulation and improved convex hull algorithms. With regard to the improved convex hull algorithms, the mean of absolute difference in the percentage of geometrical simulation-based results was 4.31% for crown projection area and 4.59% for crown volume, respectively. Meanwhile, the time consumed by the improved algorithms was significantly reduced, which took only 21% of the time required by the traditional measurement method, and 38% of the geometrical simulation method. Therefore, the proposed method can acquire the crown projection area and crown volume of a single tree effectively and quickly, which is of great significance for the application of 3D laser scanning technology in forestry practice.     

Convex set symmetry measurement using Blaschke addition

In this paper we state a new way for measuring symmetry of convex sets. The measures introduced are based on the Blaschke sum. This operation has some important properties, and is a natural way for combining convex objects when represented by their extended gaussian image. Different kinds of symmetry are considered and their properties outlined. To form the Blaschke sum, it is necessary to solve the Minkowski reconstruction problem. We study the method of reconstruction and give some improvements to make the scheme more efficient.     

一种基于凸壳的压缩域运动对象快速分割算法

目前在H.264/AVC压缩域分割领域中现有的方法存在时间复杂度高,且分割运动对象不完整的问题,提出一种新的基于凸壳的压缩域运动对象快速分割(CHSTF)算法。该方法主要利用码流中的运动矢量场信息进行分割,即首先利用后向迭代累积对MV进行归一化处理,再利用时空域滤波(STF)算法对运动矢量场进行滤波得到稳定MV场,然后对滤波MV场求解凸壳并对其进行区域填充,最后对其进行优化掩膜达到分割运动对象的效果。本方法着重于快速求得整体运动对象,并获得较好分割精准度。实验表明,通过本方法能够较好地解决上述问题,并且在运动场严重缺失的环境下,相比传统方法,本方法能获得更好的效果。     

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

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