加强局部简便计算的点在多边形内的高效判定

论文摘要

点在多边形内的检测是计算几何中的一个基本问题,有着广泛的应用需求。已提出许多方法减少要测试的多边形的边以加速。其中,均匀网格法具有很好的作用,因为各网格中的边很少,而测试点可迅即定位于一个网格。我们曾提出一种均匀网格法,预计算各网格中心点位于多边形内/外的属性,然后将测试点与所在网格的中心点连线,检测该连线与多边形的边的相交情况即可。其预处理和检测的复杂度分别为O（N）和O(N1/2),N为多边形的边数。本文在此基础上进一步改进,预计算网格交点位于多边形内/外的属性,然后将测试点与其邻近网格交点的连线,转换为与坐标轴平行的两条相连直线段,以提高与多边形边求交计算的便捷性。实验结果表明,可将检测速度提高2倍多。

论文目录

文章来源

类型: 期刊论文

作者: 王盛春,王文成,谭雪晗,李静

关键词: 多边形,网格,简便计算,点在多边形内的检测

来源: 图学学报 2019年02期

年度: 2019

分类: 工程科技Ⅱ辑,信息科技,基础科学

专业: 数学,计算机软件及计算机应用

单位: 中国科学院软件研究所计算机科学国家重点实验室,中国科学院大学计算机科学与技术学院,中国科学院动物研究所动物进化与系统学院重点实验室

基金: 国家重点研发计划项目(2017YFB1002700),国家自然科学基金项目(61661146002,61872348)

分类号: TP301.6;O18

页码: 267-273

总页数: 7

文件大小: 1032K

下载量: 49

相关论文文献

• [1].多边形和圆的初步认识[J]. 试题与研究 2019(16)
• [2].地铁车辆车轮多边形问题分析及处理措施探讨[J]. 现代城市轨道交通 2018(04)
• [3].一种任意多边形面积的计算公式[J]. 数学教学通讯 2017(33)
• [4].浅谈如何用“问题”引导数学教学——以《多边形的内角和》教学为例[J]. 高考 2017(30)
• [5].东海边际气田开发多边形FLNG装置技术方案[J]. 船海工程 2019(05)
• [6].一道课本习题的研究与推广[J]. 数学教学通讯 2019(11)
• [7].例谈如何利用旋转解答几何计算题[J]. 数理化学习(初中版) 2017(11)
• [8].彭色列闭合定理的纯几何证明[J]. 中学数学研究(华南师范大学版) 2018(09)
• [9].三维动画多边形建模技术探析[J]. 数码世界 2018(02)
• [10].HX_D1型机车轮对多边形发展趋势探讨[J]. 电力机车与城轨车辆 2017(06)
• [11].“钉子板上的多边形”教学尝试与思考[J]. 小学教学参考 2017(29)
• [12].射线定理的证明和在公安中的运用[J]. 科技与创新 2018(03)
• [13].对称性:从多边形到圆——教育数学研究之六[J]. 教育研究与评论(中学教育教学) 2018(06)
• [14].关于高速动车组轮对多边形问题的研究[J]. 中国战略新兴产业 2018(16)
• [15].小学数学课堂有效问题情境创设探微——以苏教版教材四年级下册“多边形的内角和”教学为例[J]. 小学教学参考 2019(08)

本文来源: https://www.lunwen90.cn/article/914b89d4149099534d21c01b.html