简单多边形集凸包的快速算法

提出了一个简单多边形集凸包的快速算法。先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线。应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包。算法的时间复杂度为线性O(n),并且给出一个例子进行了验证。

基于格网的多边形集合级联求并算法

与传统的多边形集合求并算法相比,级联求并法基于STR-Tree索引优先对相邻的多边形进行求并,提高多边形集合的求并效率,但在数据密度高畸变区域的性能较差。针对该问题,提出一种基于格网的多边形集合级联求并算法。该算法利用格网划分多边形集合,缩小数据密度高畸变区域的范围,进一步提高级联求并法的效率。实验结果表明,该算法有效可行。

带岛屿多边形Delaunay三角剖分算法

提出一种适用于任意多边形(含岛屿或不含岛屿)的统一Delaunay三角剖分算法.该算法首先将带岛屿多边形的所有顶点统一构建基于多边形边约束的Delaunay不规则三角网(CD-TIN);基于三角形顶点绕向,提出了多边形域外三角形的判定法则,剔除CD-TIN中的域外三角形,实现了带岛屿多边形的三角剖分.实验表明,该算法在含有大量岛屿的带岛屿多边形三角剖分中具有很高的时间效率和很强的鲁棒性,并成功将其应用到基于剖面的三维矿体建模与可视化系统中,解决了含有夹石或孔洞的矿体剖面多边形三角剖分问题,具有一定的实际应用价值.

基于轮廓线匹配的2D碎片物体复原方法

目的 为了快速地进行2D碎片物体的复原。方法 采用一种基于轮廓线匹配的2D碎片物体的复原方法,轮廓线用多边形逼近表示。这一表示在旋转和平移变换下是不变的。将多边形的本质参数连接点作为匹配的特征集,并采用对特征集排序方法提高了匹配速度。结果 所给出的匹配算法有效,有一定的实用价值。结论 基于保持几何属性和拓扑属性的特征选取,使得多边形的匹配变为1D字符的匹配,从而使得2D碎片物体的复原简单、快速。

一种多边形区域运算的改进算法

本文简述了利用两多边形的交点出入性质进行区域运算的方法，重新定义了一区域中有向边与另一区域的进出关系，给出了两多边形区域存在部分顶点或边界重合时交点出入性质的判别原则。改进后的算法适于任何非凸多边形（含孔洞）的区域运算。

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

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

简单快速的平面散乱点集凸包算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用．传统点集凸包算法和简单多边形凸包算法平行发展，互不相干．文中将简单多边形凸包算法应用于散乱点集凸包问题中，提出了新的点集凸包算法．新算法不仅达到了Ｏ（ｎｌｏｇｎ）的理论时间复杂度下限，而且极其简单，易于实现．该算法已应用于工厂设计软件ＰＤＳＯＦＴ中。

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

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

基于二分法判定点集是否在多边形内部的算法

提出一种基于二分法判定点集是否在多边形内部的算法 ,根据多边形 L的顶点和边分布的情况 ,分割平面为一组平面区域的有序集合 R,判定 R中每个区域是否在多边形 L内部 ;对于点集 S中的点 p,用二分法搜索 R,找到点 p所属的平面区域 ,从而判定出点 p是否在多边形内部 .该算法在最坏情况下的时间复杂性为 max(O(n log m) ,O(tm log m) ) ,其中 n为点集 S的点数 ,m为多边形 L的顶点数 ,t为多边形 L所有顶点的 X坐标的不同取值个数 .在一般情况下该算法比已有的算法效率更高 .

基于连接点的3D多角弧匹配

为了满足实际应用的要求 ,快速地进行多角弧匹配是必要的 ,因此 ,提出了一种快速的 3D多角弧表示和匹配的方法。该方法是在分析多角弧几何形状基础上 ,引入连接点的概念 ,同时 ,通过在连接点处建立局部直角坐标系来得到每一连接点处的球面坐标。并用连接点的球面坐标集表示多角弧 ,因这一表示在旋转和平移变换下是不变的 ,所以可取该球面坐标集作为多角弧匹配的特征集 ,用该特征集可保持多角弧的几何属性和拓扑结构。这样3D多角弧匹配就降为 1D数值串匹配 ,从而使使匹配变得简单快速。其测量函数为对应连接点间的均方差。实验结果表明 ,该匹配算法效果良好 ,并且对于数值污染具有健壮性。

逐行(列)扫描判定点集是否在多边形内部的算法

提出一种基于点集排序 ,逐行 (或逐列 )扫描平面点集 S,判定点集 S中的点是否在多边形 L内部的算法 .该算法的时间复杂性在最坏情况下为 :max( O( n log n) ,O( km log m) )次比较和 O( km)次乘法 .其中 n为点集 S的点数 ,m为多边形 L的顶点数 ,k=min( u,v) ,其中 u,v分别为点集 S中的点分布的行数和列数 .该算法思路简单 ,易实现 ,且在一般情况下 。

两个复杂多边形求交的矢量算法

基于计算几何和集合的基本理论 ,提出了任意两多边形求交的一种矢量算法 .该算法并非时间和复杂度最优 ,但总体较优 。

平面点集凸壳的快速算法

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

基于三角形构造的Trimmed曲面三角化算法

本文提出了一种新的雕塑曲面三角化算法，算法基于构造三角形的思想，能防止裂缝和覆盖现象的产生，并能保证所生成的三角形网格在空间中保持良好的性态，该算法已经成功地应用于作者开发的曲面造型系统ＳＣＡＤ１．０中。

基于连接点的二维多角弧匹配

多角弧匹配问题的关键是 ,其既能反映多角弧的几何性质 ,又能反映多角弧拓扑结构的特征选取 .在分析了多角弧几何形状的基础上 ,引入了连接点的概念 ,并用连接点集表示多角弧 ,这一表示在旋转和平移变换下是不变的 .进一步取该连接点集作为匹配的特征集 ,给出了特征集之间匹配的算法 .该算法是将连接点间的距离积分作为测量函数 ,使二维多角弧的匹配由连接点的匹配来决定 .给出的模拟试验结果表明 ,该算法效果良好 ,并且对于数值污染具有健壮性 .

二阶多智能体系统的跟随者-多领导者聚集控制

针对二阶连续时间多智能体系统的跟随者-多领导者集合聚集控制问题,假设每个领导者的运动速度为同一常数且它们之间没有通信,基于邻居原理,对网络没有通信限制(零通信时延)和有通信时延的情形,分别提出了一个新的控制协议;利用频域分析、矩阵理论和Nyquist稳定性判据,对零通信时延和有通信时延的情形,分别得到所有的跟随者都能够聚集于由多个动态领导者组成的凸多边形区域的充分条件;最后,通过数值仿真验证了文中所提控制协议的有效性和可行性.

判定点集是否在多边形内部的算法

本文提出了判定ｎ个点的点集Ｓ是否落入多边形Ｌ内部的算法，该算法的复杂性为：ｍａｘ（Ｏ（ｍｎ），Ｏ（ｌｎｌｏｇｎ））次比较和Ｏ（ｌｎ）次乘法，其中ｍ是Ｌ的顶点数，ｌ为Ｓ的凸包层数．

连接不相交线段成简单多边形(链)的算法及其实现

提出一个如何连接平面上 n条线段成一简单多边形或者简单多边形链的实际问题 ,并证明了连接平面上线段集 S成一简单多边形链的一个充分条件—— S中有一条线段连接凸壳 CH(S)中不相邻顶点 .提出了连接平面上线段集 S成一简单多边形或者简单多边形链的算法 ,其基本思想是首先逐层计算线段集 S的凸壳 ,并将这些凸壳改变为简单多边形 ;然后计算各多边形之间的交点 ,进而删去这些交点 ;最后合并若干个简单多边形为一个简单多边形 .当 S中线段数目 n较大时 ,用分治思想设计分治算法 ,较好地求解了这个问题 .

三层前向神经网络的一致逼近性(英文)

近年来 ,前向神经网络泛逼近的一致性分析一直为众多学者所重视。本文系统分析三层前向网络对于拟差值保序函数族的一致逼近性 ,其中 ,转换函数σ是广义 Sigmoidal函数。并将此一致性结果用于建立一类新的模糊神经网络 (FNN) ,即折线 FNN.研究这类网络对于两个给定的模糊函数的逼近性 ,相关结论在分析折线 FNN的泛逼近性时起关键作用。