求解简单多边形和平面点集凸包的新算法

沿一定方向遍历凸多边形的边，其内部在边的同一侧。本文依据凸多边形的这一特性，提出求解简单多边形凸包的新算法，进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点，得到极值点间的候选点子集，再求得相邻极值点间的有序凸包点列，最后顺序连接极值点间的有序凸包点列，得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h），其中，n为平面点集的点数，h为平面点集凸包的顶点数。相比相同复杂度的凸包算法，新算法简单、易于实现。又由于是顺序求得凸包上的点，新算法还具有更易于实现基于其上的有效空间算法的优点。     

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

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

平面点集凸包快速构建算法的研究

文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。     

一种确定点集最远点对的最优算法

提出了一种确定点集最远点对的最优算法.对平面内n个点的点集,在求出其凸包后,利用求对跖点对的方法确定凸包的最远点对,从而得到点集的最远点对.整个算法的时间复杂性为O(nlogn).     

点集模型的直接可见性测试与基于视点的绘制

点集模型作为一种新兴的三维几何形体表示形式,近年来备受关注.本文运用点集法向计算与凸包构建等技术,对原始点集模型进行直接可视性计算,并利用可见性计算的结果对点集模型进行基于视点的绘制.算法首先对原始模型进行基于视点的精简,剔除大部分不可见点;再对精简后的模型进行球面对称变换,并构建变换后点集的凸包,进而提取出可见点集;最后运用真实感图形绘制技术实现可见点集的快速绘制.实验证明,本文算法能够快速地计算点集模型中采样点的可见性.该算法可应用于点集模型基于视点的绘制与曲面重建,以及点集模型的阴影绘制等领域.     

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

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

一种平面点集凸包与三角网格综合生成的算法

平面点集作为一种觉数学模型,其上常做的运算是求其凸包和三角网格,目前二者的研究是独立进行的,鉴于在很多情形下这两种处理结果均需要,提出了一种综合算法：在对离散点集进行ｄｅｌａｕｎａｙ剖分的过程中,增加对三角形边界的判别、管理功能,记录其中作为点集凸包边界的线段,使得在实现剖分的同时产生出点集的凸包,从而提高了算法效率,且当该算法实现单一的点集剖分或凸包功能或是用于简单多边形的凸包与剖分时效果也很好     

一种改进的快速三维凸包生成算法及实现

本文阐述一种快速的三维凸包构造新算法,算法吸收了Quick Hull方法中每次选用凸包的极值点(Extremal-Point)来构造新凸包的思想,在此基础上改进为选用二次极值点的方法来构造新凸包,并结合"冲突图"(Conflict-Graph)来更新凸包外的点和当前凸包的拓扑结构关系,从而取得了快速排除凸包的内部点、缩小问题规模、实现高效构建凸包的效果。本文算法的时间复杂度为O(nlgr),通过实验证明本文算法与QuickHull算法相比平均执行消耗时间减少20%,因此本算法具有理论和实际应用价值。     

两维区域三角剖分的新算法

提出一种两维区域三角剖分的新算法,算法首先递归应用求两维点集凸包的Graham扫描法,在原始区域的点集中求出一系列的凸包,同时原始两维区域也被这些凸包划分为多个独立的子区域,然后对相邻两个凸包之间的子区域进行三角剖分,从而实现对整个原始两维区域的三角剖分.和以往得算法相比,提出的算法的时间效率大大提高了,并且在作者参与的军队2110建设项目应用中也体现了良好的效果.     

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

在研究了大量的求平面点集凸包的算法基础上,提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点,构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域;对于一个线段区域上的点只需要找出右侧的点,分别和线段的两个端点连接得到新的多边形链,依次这样处理每个点,直到结束。这样就得到四个简单多边形单调链,然后对单调链求凸点,时间复杂度为O（n）,最后求得的每个凸点就是平面点集的凸壳,此算法总的时间复杂度不超过O（n log n）。     

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

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

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

本文依据同构化凸壳构造基本定理,提出效率更高的双域双向水平倾角最小化圈绕凸壳新算法.本新算法的同构化特点是:1)"初始顶点与双域生成"处理:找出给定二维点集S的最低点和最高点,即Y轴坐标值最小点(若有多个最小点,则只取最左的最小点)和Y轴坐标值最大点(若有多个最大点,则只取最左的最大点),作为凸壳(逆时针围绕的)A向初始顶点、(顺时针圈绕的)B向初始顶点;并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S右、S左.2)在S右内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理:分别过自己的最近新顶点,作X轴正向射线,并A向或B向找出当前点集内对该顶点正向射线(为始边的)倾角最小的点;删除对已得各顶点所构成的子凸壳内点,当所剩当前点集非空时继续作"2)"逐边圈绕,直到为空.3)同理,在子点集S左内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理.     

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

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

双域单向水平倾角最小化圈绕凸壳新算法

本文依据同构化凸壳构造基本定理，提出了效率更高的双域单向水平倾角最小化圈绕二维点集凸壳新算法，实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新。本新算法的同构化特点是：1）“初始顶点与双域生成”处理：找出给定二维点集S的最低点和最高点，即Y轴坐标值最小点（若有多个最小点，则只取最左的最小点）和Y轴坐标值最大点（若有多个最大点，则只取最右的最大点），作为凸壳逆时针圈绕的初始顶点；并以这两个初始顶点为端点的线段，把原二维点集划分为两个独立的子点集S右、S左。2）进行单向“圈绕寻找下一新顶点”：A）在S右内，过逆向次新顶点作X轴正向射线，并找出当前子点集内对该逆向次新顶点正向射线（为始边的）倾角最小的点，此最小点即为S右逆向最新顶点；B）在S左内，过次新顶点作X轴负向射线，并找出当前子点集内对该逆向次新顶点负向射线（为终边的）倾角最小的点，此最小点即为S左逆向最新顶点。3）删除对已得各项点所构成的子凸壳各内点。4）仅当所剩当前点集非空时才从“2）”继续作逐边双域单向圈绕。     

平面点集凸壳的快速算法

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

基于凸壳与有向包围盒的骨架提取方法

为获取三维模型的几何及拓扑信息,提出一种基于凸壳与有向包围盒(OBB)的线性骨架提取方法.首先将三维网格模型进行分割生成多个子网格模型;然后对各子网格中的点集求取凸壳作为该子网格点集的近似,由凸壳顶点的形心构成原始骨架点;再用OBB进行重叠计算求出相交点集,以生成关节骨架点;最后对原始骨架点与关节骨架点进行连接,经冗余检测后形成完整骨架.实验结果表明,该方法快速、有效,提取出的骨架能保证连通性与中心性且能很好地提取关节骨架点,为蒙皮关节动画、模型形状分析等提供有效信息.     

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

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