无线传感器网络中基于Convexhull的能量空洞避免路由算法

提供了一种绕过无线传感器网络"能量空洞"的方法(CHA方法),可以用来找到绕过能量空洞的最优节点路由路径。在数据包从源节点传递到目的节点的过程中,通过遇到能量空洞,先勾勒出空洞范围,再基于凸壳(Convex hull)找到绕过能量空洞的最优节点路由路径。仿真结果表明,该算法优化了能量空洞绕洞路由路径,有效提高了无线传感器网络传输效率,减少了无线传感器能量损耗和信息传递的延迟。

A new algorithm for computing the convex hull of a planar point set

When the edges of a convex polygon are traversed along one direction,the interior of the convex polygon is always on the same side of the edges. Based on this characteristic of convex polygons,a new algorithm for computing the convex hull of a simple polygon is proposed in this paper,which is then extended to a new algorithm for computing the convex hull of a planar point set. First,the extreme points of the planar point set are found,and the subsets of point candidate for vertex of the convex hull between extreme points are obtained. Then,the ordered convex hull point sequences between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O(nlogh) ,which is equal to the time complexity of the best output-sensitive planar convex hull algorithms. Compared with the algorithm having the same complexity,the new algorithm is much faster.

A novel method for virtual clearance computation of high-speed train based on model integration and convex hull

The 3D clearance of a high-speed train(HST) is critical to ensure the safety of railway transportation. Many studies have been conducted on the inspection of the clearance profile in railway operation based on the vision system, but few researchers have focused on the computation of the 3D clearance in the design phase of an HST. This paper summarizes the virtual 3D clearance computation of an HST based on model integration and the convex hull method. First, both the aerodynamic and kinetic analysis models of the HST are constructed. The two models are then integrated according to the corresponding relationship map, and an array of transformation matrixes of the HST is created to drive the designed model simulating the physical railway motion. Furthermore, the convex hull method is adopted to compute the 3D envelope of the moving train. Finally, the Hausdorff metric is involved in the measurement of the minimum clearance model and the 3D envelope model. In addition, the color map of the Hausdorff distance is established to verify that the designed shape of the HST meets the national standards. This paper provides an effective method to accurately calculate the 3D clearance for the shape design of an HST, which greatly reduces the development cost by minimizing the physical prototype that must be built.

On Constructing Approximate Convex Hull

The algorithms of convex hull have been extensively studied in literature, principally because of their wide range of applications in different areas. This article presents an efficient algorithm to construct approximate convex hull from a set of n points in the plane in O(n+k) time, where k is the approximation error control parameter. The proposed algorithm is suitable for applications preferred to reduce the computation time in exchange of accuracy level such as animation and interaction in computer graphics where rapid and real-time graphics rendering is indispensable.

Group Target Tracking in WSN Based on Convex Hulls Merging

When a mass of individual targets move closely, it is unpractical or unnecessary to localize and track every specific target in wireless sensor networks (WSN). However, they can be tracked as a whole by view of group target. In order to decrease the amount of energy spent on active sensing and communications, a flexible boundary detecting model for group target tracking in WSN is proposed, in which, the number of sensors involved in target tracking is adjustable. Unlike traditional one or multiple individual targets, the group target usually occupies a large area. To obtain global estimated position of group target, a divide-merge algorithm using convex hull is designed. In this algorithm, group target’s boundary is divided into several small pieces, and each one is enclosed by a convex hull which is constructed by a cluster of boundary sensors. Then, the information of these small convex hulls is sent back to a sink. Finally, big convex hull merged from these small ones is considered as the group target’s contour. According to our metric of precision evaluation, the simulation experiments confirm the efficiency and accuracy of this algorithm.

Drug discrimination of Near Infrared spectroscopy based on the scaled convex hull classifier

Near Infrared spectroscopy(NIRS)has been widely used in the discrimination(classification)of pharmaceutical drugs.In real applications,however,the class imbalance of the drug samples,i.e.,the number of one drug sample may be much larger than the number of the other drugs,deceasesdrastically the discrimination performance of the classification models.To address this classimbalance problem,a new computational method--the scaled convex hull(SCH)-basedmaximum margin classifier is proposed in this paper.By a suitable selection of the reductionfactor of the SCHs generated by the two classes of drug samples,respectively,the maximalmargin classifier bet ween SCHs can be constructed which can obtain good classification per-formance.With an optimization of the parameters involved in the modeling by Cuckoo Search,a satisfied model is achieved for the classification of the drug.The experiments on spectra samplesproduced by a pharmaceutical company show that the proposed method is more effective androbust than the existing ones.

Secure planar convex hull protocol for large-scaled point sets in semi-honest model

Efficiency and scalability are still the bottleneck for secure multi-party computation geometry(SMCG).In this work a secure planar convex hull(SPCH) protocol for large-scaled point sets in semi-honest model has been proposed efficiendy to solve the above problems.Firstly,a novel privacy-preserving point-inclusion(PPPI) protocol is designed based on the classic homomorphic encryption and secure cross product protocol,and it is demonstrated that the complexity of PPPI protocol is independent of the vertex size of the input convex hull.And then on the basis of the novel PPPI protocol,an effective SPCH protocol is presented.Analysis shows that this SPCH protocol has a good performance for large-scaled point sets compared with previous solutions.Moreover,analysis finds that the complexity of our SPCH protocol relies on the size of the points on the outermost layer of the input point sets only.

一种基于流形的机械臂动作构型知识压缩表达方法

针对在机械臂分拣任务中,存在物体形状各异、大小不一、训练神经网络成本过高的问题,提出一种基于流形空间的机械臂快速分拣方法。通过自主设计的一款简易实验装置模拟代替机械臂进行实验。对高维数据进行压缩,结合三维快速凸包求解算法,对体积大小不同的同类物体的流形空间进行分割,以凸包形式将稳定性较高的点集包裹起来。实验结果表明,体积大小不同的同类物体的高稳定流形子空间是一致的。该方法可以通过对一种物体的流形子结构进行尺度放缩,得到不同大小的同类物体的高稳定分拣区域,用于生成高效、可靠的机械臂分拣任务中的6D位姿构型,以提高分拣作业的工作效率。

A COUNTER－EXAMPLE TO A FAST ALGORITHM FOR FINDING THE CONVEX HULL OF A SIMPLE POLYGON

A linear-time algorithm was recently published (International Conference Proceedings ofPacific Graphics' 94/CADDM' 94, August 26-29 , 1994 , Beijing , China) for computing the convexhull of a simple polygon. In this note we present a counter-example to that algorithm by exhibiting afamily of polygons for which the algorithm discards vertices that are on the convex hull.

A NEW CONVEX HULL ALGORITHM FOR ANY POLYGON

A new algorithm for finding convex hull of a polygon is proposed. An example is given to show the effectiveness and the simplicity of the algorithm.

基于机器视觉的芯片字符区域分割和定位算法

芯片表面的字符对分选具有重要意义,对字符的定位是分选工作的关键步骤。为了提高分选工作定位效率和定位精度,提出了一种基于改进的区域生长算法和凸包检测算法分割和定位芯片表面字符区域方法。首先,对采集图像进行预处理操作,利用改进的Canny算法获取无干扰图像边缘,将图像边缘作为区域生长法的种子点并以图像自适应阈值作为生长准则分割图像,使用最大内接矩形算法粗定位字符区域;其次,采用Harris角点检测算法获取字符角点分布位置;最后,筛选角点并提取关键点,利用一种改进的凸包检测算法定位字符区域。经过实验验证,所设计的算法能够完整的分割和定位芯片表面字符区域,定位精度和效率较原有方法提升5.3%和15.4%,满足实际工业生产的要求。

乡村聚落边界形态生成方法研究

聚落的边界由建筑部分的实边界与建筑之间空隙部分的虚边界连接而成。文章基于建筑外部空间理论与凸包原理,提出了一种求取聚落边界的新方法。首先利用Delaunay三角网求取聚落建筑之间的影响距离,继而绘制建筑节点网络图,以此求取聚落内两两之间具有直接可视空间关联的建筑之间的凸包,并叠加得出该聚落的公共空间,其外轮廓即为聚落的虚边界。综合实、虚两部分边界,得到完整的聚落边界图形。文章提出的新方法充分考虑了聚落内部建筑的疏密程度对聚落边界设定的影响,其结果更符合真实的空间感受,也更具科学性与合理性。

一种基于激光点云数据的微距栅格体积算法

针对规则格网算法难以满足激光点云模型高精度体积计算的问题,提出了一种基于激光雷达点云数据的微距栅格体积算法。该方法首先运用葛立恒凸包算法提取凸包点集,然后运用微距格网划分、高程插值和网格体积累加的方法计算体积。与规则格网法不同,这种算法充分利用激光雷达数据高密度点云特征,采用格网微分和增大插值半径的方法改善模型表面的连续性,进而提高计算精度。实验结果表明,微距栅格体积算法具有较好的时间复杂度和较高的计算精度,适宜于激光点云模型高精度体积计算。

基于自适应特征选择k子凸包的滚动轴承故障诊断

滚动轴承故障诊断中往往将特征选择和分类器的设计分别进行研究,从而难以获得满意的分类精度。将特征选择和分类器寻优结合起来,提出了一种自适应特征选择k子凸包(Adaptive Feature Selection K-sub Convex Hull, AFSKCH)的分类模型,从而实现了故障特征自适应选择和分类的一体化。首先,利用凸包距离函数保持数据流形上的局部邻域结构,通过交替构造k子凸包得到特征权值矩阵;其次,采用线性规划接近度方法求解k子凸包距离,利用乘子交替方向法得到自适应特征空间;最后,根据测试点到k子凸包的最小重构距离进行分类。滚动轴承故障振动信号分析结果表明,该方法特征选择性能优于其他特征选择方法,且具有较高的分类精度。

仿生凸包起垄刀表面特征参数优化设计

起垄机在作业时发现起垄刀粘附严重,为了解决在黏性土壤环境下起垄刀粘附问题,以土壤动物蜣螂头部表面非光滑凸包结构为仿生对象,通过白光干涉仪获得凸包微观结构的特征参数完成仿生起垄刀设计。基于EDEM仿真分析仿生凸包起垄刀的减粘脱附效果,探索凸包减粘机理,通过田间试验验证仿真分析的有效性。试验结果表明:仿生凸包起垄刀减粘脱附效果由小到大依次为Ⅰ、Ⅲ、Ⅱ,试验结果与EDEM仿真中得到的结果相一致,验证了仿真的可靠性。其中,仿生起垄刀Ⅱ的减粘性能最好,在18.73%、22.91%、26.87%含水率下的平均粘附量相对于原型刀具分别减少了12.45%、24.64%、6.19%。研究结果可为起垄机减粘脱附仿生设计提供可行的研究方法。

基于凸包理论的含风电电力系统负荷恢复方案优化

大停电事故后,合理的负荷恢复策略对加快电力系统恢复、减少停电损失具有重要意义。针对标准交流潮流方程的非凸性导致负荷恢复模型求解效率低的问题,提出了基于凸包理论的含风电电力系统负荷恢复方案优化方法。首先,简要介绍了凸包理论以及非线性函数的凸包构建方法。其次,针对风电出力的不确定性,采用条件风险价值理论处理风电波动带来的风险,进而建立了直角坐标系下基于凸包理论的电力系统负荷恢复二阶锥优化模型,其中,交流潮流方程中的非线性项采用凸包表达。针对无法精确确定凸包参数的问题,提出了基于迭代更新的参数优化方法,减少因凸包引入的松弛误差。所提出的模型为混合整数二阶锥规划模型,可采用商业求解器高效求解。最后,采用IEEE 39节点系统和改进的广东电力系统验证了所提出模型的有效性。

采用Hull树的贪婪地理位置路由算法的设计

地理位置路由算法是指借助节点获得的地理位置信息进行无线传感网络中的路由发现与数据转发工作。本文提出一种基于Hull树的贪婪地理位置路由算法——Greedy Hull Tree Geographic Routing(GHTGR)。通过图形学中凸包的概念,在网络初始阶段分布式地在各节点上建立Hull树以探查网络局部拓扑结构;同时在数据分组的路由转发阶段,通过Hull树内的搜索,寻找下一跳转发节点,完成数据分组的转发传输。通过仿真实验表明,与现有地理位置路由算法相比,该算法能够正确地寻找数据转发路径,有效地减少网络能耗,提高网络传输性能。

基于无人机倾斜摄影的三维绿量估算

精准、快速、高效的绿化效果评估是现代林业发展的重要要求.针对传统方法绿地覆盖率无法反映绿化空间垂直结构的缺点,提出基于切片凸包算法利用倾斜摄影点云估测三维绿量的新方法,以河南农业大学文化路校区为研究区域,通过三种方法估算不同树种及树形的三维绿量,对比不同方法的测算精度,探索最优估算方法.利用无人机进行多光谱成像和倾斜摄影成像,通过面向对象的方法在数字正射影像基础上提取林木,结合实测33个树种的冠径、冠高等信息,分别利用冠径-冠高方程法(D-H)、实景三维模型法(3D)和基于切片凸包算法的点云体积测算法(PC)进行三维绿量测算.结果表明,三种方法测算值与实测值拟合的回归方程R2分别为0.84、0.92、0.94,RMSE分别为168.85、90.74、78.46 m^(3),精度分别为62.67%、87.26%、90.19%;优势树种悬铃木三维绿量最大,龙爪槐值最小;PC法测算水杉和球形树的相对误差最小,分别为0.56%和1.27%.利用倾斜摄影点云的切片凸包算法测算三维绿量具有可行性且最精准,为筛选不同树种及树形的三维绿量估算方法的选择上提供科学依据.

广义多边形凸包弹性线递支模拟算法

针对诸多领域涉及的平面弯曲图形的凸包计算,提出弹性线递支模拟算法用于计算简单闭广义多边形的弹性包络线。所提算法基于物理模型,通过判断各支点是否受力平衡来判别其是否为弹性包络线上的平衡支点,并据此分别进行前进、回弹和跳跃等操作,直至计算出所有平衡支点进而求出其弹性包络线。3种典型的简单闭广义多边形的对比测算表明:所提算法可实时稳健地求解平面任意简单闭广义多边形的弹性包络线,具有高效性和普遍适用性。

小龙虾识别与度量关键技术研究与应用

小龙虾的表型性状是水产养殖和遗传育种中非常重要的经济依据,为了精准实现对小龙虾的视觉检测与定位,并对其主体躯干表型特征进行测量。首先提出了一种基于Mask RCNN实例分割模型检测小龙虾的方法,不仅能快速识别小龙虾,还能对其进行实例分割,生成高质量的二值掩膜图。然后在此基础上,提出一种新的小龙虾度量算法:通过提取小龙虾的轮廓曲线,获取其中轴线,采用分区法提取小龙虾的特征区域,再利用凸包和凸包缺陷算法获取小龙虾的特征点,实现对其全长、体长、头胸甲、腹部、尾扇等主要部位的无接触度量计算。结果表明:Mask RCNN模型在小龙虾数据集上具有很好的泛化性能,模型分割准确率达到了94.6%,目标识别的平均检测精度达到了98.7%。各测量指标的平均绝对误差均在5 mm之内,比人工手动测量难度大大减小,并且稳定高效,重复性更好。该方法将有利于生产和选育过程中小龙虾的鉴别及结构尺寸的快速获取。