多边形中的点可见性快速算法

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理"带洞"多边形,而且只对多边形进行局部访问;对于"带洞"多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.

求简单多边形可见点的一种新算法

提出一种求简单多边形可见点的新算法,通过对多边形作预处理,可预先剔除其中部分不可见点,并消除了判断可见点过程中的螺旋状态。将多边形剩余顶点序列分割为四段,每段分别按文中给出的方法找出可见点。算法中对点与线段的位置关系,用点与线段围成的三角形的方向表示。三角形的方向通过极点顺序法确定,避免了使用耗时的叉积法。试验表明,算法准确、高效和稳定。

带权值目标点的可见覆盖求解算法

针对传统的艺术画廊模型及其模型的变形在实际应用中无法处理诸如可用守卫数受限、只需监控离散目标点等情形,提出一种基于带权值目标点的可见覆盖的变形模型及其求解算法.首先利用角扫描技术得到每个目标点的可见多边形,然后通过对这些可见多边形进行几何求交、几何求差操作来得到若干等价目标可见区域,再依据每个区域对应的可见目标点集将所提出的变形模型转化为经典的集合最大权值覆盖问题,最后利用整数线性规划方法对其求解,得到最终需要的守卫数及放置位置.大量的实验结果表明,该算法是正确和有效的.

1991年中国数学奥林匹克试题及解答

1991年中国数学奥林匹克(CMO),即第六届全国中学生数学冬令营,于1991年1月11日至15日在武汉市华中师范大学举行。1月12日及13日上午各用4.5小时进行竞赛考试,与此同步还用同一份试题进行了第二届陈省身杯团体赛(部分省、市、自治区各派出3名营员参赛)。下面是这次竞赛的6道试题及解答。(每题满分21分,最高得分为117分) 第一天 (1991年1月12日上午8:00—12:30) 一、平面上有一个凸四边形ABCD, (1)如果平面上存在一点P。