一种改进的点在多边形内外判断算法

来源 :计算机工程 | 被引量 : 0次 | 上传用户:petry1989
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
为解决多边形内外算法中BSP树退化为链表的问题,提出一种改进的点在多边形内外的判断算法。在构建水平扫描线的BSP树之前,对水平扫描线按照Y值进行排序,将排好序的水平扫描线按照二分法的顺序插入到BSP树中,其查找时间复杂度为O(lbn)。实验结果表明,该算法在不增加BSP构建时间复杂度的前提下,能够保证BSP树的查找效果总是最优的,且简单易行,具有较好的通用性。
其他文献
通过在英国格拉摩根大学培训学习的体会,从教学过程、教学质量保障体系及辅助设施等几方面,对英国高等教育“以学生为中心”的教学理念进行了探讨,分析了这种教学理念和与之对应
河口地区是河川径流与海洋潮汐两种没波长振动波交会的区域,水位的变化极其复杂,借助频谱分析可在频域内研究它们不同的振动特性和变化规律,并将们分离开来。本文通过对长江口一
自从组织冗余的概念提出后,有关组织冗余作用的争论就一直存在,组织冗余与企业绩效的关系正是其中的焦点问题。组织理论和代理理论从不同角度对组织冗余作用做出了截然相反的
国内外学者对控制权现金流权分离度和公司避税行为的研究已经不胜枚举,但是我们却发现很少有学者去研究控制权现金流权分离度与企业避税行为这两者之间的关系。所以本文总结
20世纪80年代以来,中小企业的快速发展给我们带来了许多的发展契机,随着中小板对我国资本市场影响的逐步加深,广大投资者和公司管理者也越来越关注其公司治理状况。想要充分
马栏河系穿越大连市城区西部的一条较大河流.介绍了如何借用另一条穿越城区的河流--自由河降雨径流实测资料,应用单位线法进行水文分析和设计洪水计算,为整治该河道提供了科
针对近年来氮素化肥施用量大而利用率较低现状,在江苏太湖地区设计田间试验,研究稻麦轮作田全年氮素流失特征。结果表明,在本试验条件下稻季和麦季径流中氮损失量相近,麦季略
据贵州省农委相关部门消息,该省将在茶叶主产县开展茶叶种质资源调查和茶叶种植核心保护区规划,并计划将茶叶种植核心保护区纳人生态保护红线区域管理。今年下半年,贵州省农委、
目的比较左侧卧位、俯卧位胸腹腔镜食管癌切除术后患者肺功能。方法 52例采用胸腹腔镜行食管癌切除术的中下段食管癌患者,随机分成A、B组各26例,A组采用左侧卧位双腔插管,B组
2013年夏季,高温干旱肆虐长江中下游地区。浙江茶区遭遇创记录的持续高温干旱,至8月12日杭州连续40多天基本无雨,最高气温达41.6℃,连续5次破1951年有气象记录以来的历史最高温度,