基于凸片段分解和格网的点在多边形中的可见边检测

来源 :计算机辅助设计与图形学学报 | 被引量 : 4次 | 上传用户：zzhijian

【摘要】

：

检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算;然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化

【作者】

：

高天豪王文成朱滨海

【机构】

：

中国科学院软件研究所计算机科学国家重点实验室,中国科学院大学,DepartmentofComputerScience

【出处】

：

计算机辅助设计与图形学学报

【发表日期】

：

2013年08期

【关键词】

：

多边形可见边凸片段格网并行计算 polygon visible edges convex line segments grid~ parallel

【基金项目】

：

国家自然科学基金（60833007,60928006）,中国科学院知识创新工程领域前沿项目.

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

其他文献

面向异构多核系统芯片的高效动态带宽划分方法

针对异构MPSoC中各主设备频繁争抢有限访存带宽、请求相互干扰、严重影响系统性能的问题,提出一种基于限流的动态DRAM带宽分配机制——TDBA.首先实时监测主设备访存特性,通过

期刊

异构多核系统芯片多核应用访存干扰带宽限流HMPSoC multicore application interference bandwidth t

含蜡天然气处理过程脱蜡剂的优选研究

通过对当前脱蜡剂的组分进行分析研究,认为脱蜡剂液相回收率低的原因是轻组分含量高。为了提高脱蜡剂的液相回收率,通过对多种脱蜡剂进行对比分析和模拟计算,得出相同防蜡效

期刊

蜡天然气脱蜡剂回收率凝析油三甲苯waxnatural gasdewaxing agentrecovery ratecondensatetr

三维单目虚实物体球对面碰撞检测算法

为加强增强现实的沉浸感与真实性,实时地进行虚实物体间的碰撞检测至关重要.因此,提出一种基于增强现实和单目视觉的任意形状虚实物体碰撞检测估计算法.通过改进现有的单目二维虚实碰撞检测及响应算法,针对现有碰撞检测算法存在的计算复杂度高的问题,提出一种仅需计算实际物体4个特征点的三维碰撞检测算法;并通过对象分割、特征点提取、碰撞检测和碰撞响应等过程取得与真实世界物理特性一致的三维虚实碰撞响应估计效果.在增

期刊

增强现实碰撞检测碰撞响应无标记注册虚实碰撞augmented reality collision detection collision resp

面向大屏幕手机的单手目标选择方法

针对大尺寸屏幕手机上的远处目标操作困难,且容易产生误操作的问题展开研究.首先通过定性分析考察用户操作手机的习惯,得出拇指自然可及的屏幕区域;然后结合人手的生理结构和

期刊

大屏幕手机目标选择技术单手操作large screen smartphone target selection technique single-ha

创新驱动下机械制图课程的教学改革

“创新驱动”发展战略的提出和计算机辅助设计技术的发展,对机械制图课程的教学内容提出了新要求.以培养高技能创新型人才为目标,结合机械制图课程特点,分析了当前机械制图课

期刊

创新驱动机械制图教学改革innovation-driven mechanical drawing teaching reform

长潭水库水体富营养化状况分析及防治对策

根据近年水质监测结果,着重研究长潭水库的富营养化状况,引入氮磷比的概念,对其富营养化程度及变化趋势进行分析预测,认为水库库区表层水水质指标浓度中氮磷比呈现逐渐增大的

期刊

长潭水库富营养化氮磷比防治对策Changtan Reservoir eutrophication nitrogen and phosphorus r

多特征自适应融合的粒子滤波跟踪算法

针对跟踪过程中目标形态不断变化或部分遮挡导致鲁棒性差的问题,提出一种基于多特征自适应融合的粒子滤波跟踪算法.该算法从视觉特征集中选取了描述能力强的2种特征,并将其按照与目标模型的多尺度相似度进行线性融合;为了减小跟踪漂移,通过计算当前目标模型与初始目标模型的多尺度相似度自适应地更新目标模型.大量仿真实验结果表明,文中算法可以鲁棒地跟踪到部分遮挡和形态变化的运动目标.

期刊

粒子滤波自适应特征融合多尺度相似度(MSBRS)模板更新particle filter adaptive feature fusion mult

35例开放性胫腓骨骨干骨折感染原因分析与处理

我科从1972～1997年共收治131例开放性胫腓骨骨干骨折,其中35例并发感染,感染率为26.72%.现对感染发生的原因进行分析,并提出相关的防治措施,以减少此类并发症的发生.

期刊

胫腓骨骨干骨折开放性骨折感染

水利与环境工程学院前往扶贫结对单位——台州市黄岩区上郑乡接洽扶贫工作

1月22日上午,水利与环境工程学院副院长欧剑、信息工程与艺术设计学院金挺一行人风尘仆仆赶往台州市黄岩区上郑乡,与黄岩区上郑乡乡长林宁乡、党委副书记陈海珍、副乡长吴敏

期刊

扶贫工作工程学院黄岩区台州市单位环境水利水源保护区

响水涧抽水蓄能电站上水库主坝应力变形分析

面板堆石坝的应力变形，尤其是面板的应力变形及周边缝、垂直缝的变形是工程设计施工人员最为关注的部位．以响水涧抽水蓄能电站上水库主坝为例，建立三维有限元模型，计算分析各工况

期刊

面板堆石坝应力变形挠度CFRD stress deformation deflection vertical joints peri

基于凸片段分解和格网的点在多边形中的可见边检测

与本文相关的学术论文