基于线性方程的凸多边形内外点判别算法研究

多边形内外点判断算法是多个领域相关研究的基础，主要用于检测某点位于给定多边形内部或外部.针对传统射线法的奇异性问题以及角度和法、面积和法误差大、精度要求高等缺点，提出一种基于线性方程的多边形内外点判别新算法.该算法借助求解线性方程的思想，将点与多边形的位置关系判别问题转换为点与直线的位置关系判别问题.经过实验仿真，证明该算法能够正确判别点与凸多边形的位置关系，且能正确处理高精度的地理坐标数据.     

地空导弹武器系统仿真中目标与设定区域(多边形)位置关系判别算法

将地空导弹武器系统仿真中诸多问题抽象为目标与设定区域(多边形)位置关系判别问题。提出旋转函数和相关边的概念,设计了判断目标在多边形内外的新算法。综合运用旋转函数与相关边技术,将目标与多边形之间的位置关系转化为目标与其相关边之间的位置关系,首先找出目标点的相关边,再计算该点与其相关边组成的有向三角形的旋转函数,最后利用旋转函数值的正负性来判断目标与多边形的位置关系。在相关边的寻找过程中设计了算法,避免了大量的求交运算,从根本上提高了算法的效率。新算法还简单有效地解决了传统判别算法——射线法中的临界位置问题。程序验证表明：新算法易于实现,适用于简单多边形,在地空导弹武器系统仿真中具有很强的重用性,对避免重复的仿真研究和开发具有重要意义。     

基于插入法构建油藏剖面图中的多边形图元

为了获取指定剖面上油藏内部参数场的空间分布情况,需要依据剖面与油藏模型间的交点集构建多边形,进而根据不同油藏参数得到相应的剖面图.在研究常用多边形构建算法的基础上,根据交点数据集的特点,提出了基于插入法的多边形构建算法:利用矢量叉积性质,根据点与射线位置关系,确定待排序点在有序顶点集合中的位置,对有序顶点依次连接构成多边形.应用结果表明,该算法能够有效地解决油藏模型剖面可视化中多边形的构建问题.     

判定点与多边形及简单多边形之间的空间关系

空间拓扑关系的分析判断是GIS研究的基础。针对射线法理论判定点与多边形的位置关系中可能出现的问题,提出了相应的补充算法,并由此引申得出了确定两个简单多边形空间关系的解决思路。     

一种判断点与多边形关系的快速算法

采用对多边形各边赋权值的方法,分析射线与多边形相交的不同情况,给出了使用结构化查询语言实现交点个数求解的快速解决方案.结合数据库管理系统提供的优化查询机制,通过执行一次查询求得射线与多边形的交点个数,从而快速地判断出点与多边形的位置关系.与其他改进方法相比,该方法易于理解,计算简单,对于具有多顶点的复杂多边形,其优越性显得更为突出.     

一种基于点表面的尖锐特征绘制方法

针对抛雪球算法不能很好地处理尖锐特征这一问题,对已有的点边混合模型进行了改进,提出了一种通过射线法判断点与裁剪区域关系的裁剪算法,并给出了基于该算法的绘制策略.该算法能够处理多种复杂裁剪情况,包括复杂多边形及非闭合区域,减少了表面边界对表面点采样率的约束,有效避免了原有绘制方法中复杂的增加采样率的预处理过程,简化了整个绘制流程.通过对比不同模型的绘制速度,得出裁剪算法对绘制速度的影响主要取决于每个像素点的裁剪边数.     

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

提出判定点是否在多边形内部的一种算法，其方法是判定射线与多边形边的交点数目以及必要时移动该点的位置，再判定交点的数目，该算法的时间复杂性为Ｏ（ｎ）次四则运算和Ｏ（ｎ）次比较，其中ｎ为多边形的顶点数。     

多边形窗口的矢量图形裁剪算法

在分析原有图形裁剪算法的基础上,具体讨论了改进后的多边形窗口内点、线、面目标的裁剪算法。其中,点目标的裁剪采用射线交叉法。线目标的裁剪是通过计算被裁剪线段和多边形各边真实交点之间各子线段的中点来判断是否对它们实施裁剪。在点、线裁剪的基础上实现了面目标的裁剪。该算法能快速、正确地得到结果。     

基于凸剖分的点在多边形内的高效判定

提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算.     

交互式的多边形变形控制技术

 提出了一种交互式的多边形变形控制算法,能及时地为用户提供反馈,根据用户对约束点的操作轨迹发生变形.用户在原多边形上指定多个约束点,并且改变部分约束点的位置.被移动的约束点在用户给定的位置,未被移动的约束点保持原来的位置.算法根据这样的约束条件构建代价函数求解目标多边形,对用户操作作出实时反馈,达到由用户的交互控制带动整个多边形变化的变形效果.该方法能避免多余形变的发生,保持原多边形边向量的相对关系,得到具有良好变形效果的目标多边形.     

气泡堆积法生成曲线多边形区域非结构化网格及其应用

对气泡堆积法进行改进,发展了一种基于气泡堆积法生成曲线多边形区域非结构化网格的算法,将曲线边界映射为直线完成气泡添加和位置动态调整,再通过弧长参数化的方法将气泡位置映射回曲线边界,避免了移动调整过程中气泡偏离曲线的问题.提出了一种简便的判断点在复杂曲线多边形区域内的方法,简单且易于编程.通过添加不同大小的顶点气泡以及在内部设置人工点源,利用加权平均法实现了网格的局部加密.应用基于非结构化同位网格的SIMPLE算法对环扇形空腔顸盖驱动流进行了数值模拟,不同雷诺数下的计算结果与文献结果吻合较好.     

判断点与多边形位置关系的算法综述

在GIS中,点与多边形位置关系的判断是GIS的重点和难点之一,对于这种关系的判定有很多种方法,本文重点总结在矢量空间中目前常用的几种方法,这些方法都是基于空间的定量计算,最后对这些方法进行了比较.     

多边形的面积及复函数的二重积分

由数论中格点多边形的一个面积公式引出了它的复函数的二重积分表示式,再由多边形面积的解析几何表达式引出了围道积分公式,然后初步探讨了复函数的二重积分.     

基于泰森多边形法的空间品位插值

为使泰森多边形法能够用于三维地质体的空间属性插值,生成规则网格结构化体数据,利用取样数据的空间分布特性,提出了用于空间插值的方案,通过分析泰森多边形的性质,无需真正构造泰森多边形,建立了具有距离相关性的品位插值关系,从而解决了泰森多边形法的空间品位插值问题。实例验证表明,该插值方案是可行的,插值结果是理想的。     

基于顶点凸凹性多边形的核的算法

简单多边形的核是位于多边形内部的一个点集,从其中任意一点可见多边形的全部边界。基于简单多边形各顶点的凸凹性,提出了一个判断核的存在性以及得到核多边形的顶点序列的新算法。利用多边形凹点所在的部分相邻边剖分由多边形凸点组成的初始核多边形,实现了核的顶点坐标的求解。该算法便于实现,可广泛地应用于摄像机定位等涉及可见性的问题。     

一种改进的点定位算法

通过对传统的点定位算法——奇偶法则算法的分析 ,提出了一种改进的奇偶法则的实现算法 .在改进算法中 ,从待判定点引出的射线定义为与 x轴平行且与其同向 ,对射线与区域边界边的相交情况进行了分类处理 .通过分析射线与边界边的位置关系 ,只有少数情况需要计算其交点 ,而大部分情况只需简单比较即可得出相交情况 .当射线穿过两条相邻边界边的交点时 ,根据定义的法则 ,只进行一次相交情况的判定 .因此 ,改进算法减少了计算交点的次数 ,提高了点定位的效率 .最后通过实际应用 ,对传统算法与改进算法在同样条件下的处理时间进行了比较     

二维非结构网格Euler方程高效解法

在非结构网格上应用多重网格技术加速 Euler 方程的收敛,在多重网格中通过聚合法进行粗网格生成,并对粗网格中的多边形网格做了等价面处理.在空间离散上采用 Roe 格式,在时间推进上分别采用了显式和隐式算法.通过对 NA-CA0012 翼型和 RAE2822 翼型的流场模拟,比较了显式多重网格法和隐式多重网格法的计算效率.     

光平面剖切法及其在透视图消隐中应用

研究利用近景摄影测量成果绘制建筑物透视力的消隐问题，提出了光平面剖切的消隐方法，建立了消隐的数学模型；通过数学计算与判断，确定了空间点与面的隐藏关系，将复杂的空间问题转化为平面问题来解决，用C语言实现了该算法，给出了应用实例，实践 证明该方法理论正确，方便实用，并且开拓了消隐算法新途径。