| 基于凸剖分的点在多边形内的高效判定 |
| 李静; 王文成; 吴恩华
|
| 2007
|
| 发表期刊 | 自然科学进展
 |
| ISSN | 1002-008X
|
| 卷号 | 17期号:7页码:995-1000 |
| 摘要 | 提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算. |
| 关键词 | 点
多边形
包容性检测
加速
凸剖分
凸多边形
判定算法
二叉树
多边形剖分
组织管理
奇异情况
空间需求
计算
预处理
新方法
复杂度
运算
|
| 部门归属 | 中国科学院软件研究所计算机科学国家重点实验室,北京100080;中国科学院研究生院,北京100039;中国科学院软件研究所计算机科学国家重点实验室,北京100080;中国科学院软件研究所计算机科学国家重点实验室,北京100080;澳门大学科技学院计算机与信息科学系,澳门
|
| 语种 | 中文
|
| 内容类型 | 期刊论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/11286
|
| 专题 | 基础软件与系统重点实验室
|
推荐引用方式
GB/T 7714 |
李静,王文成,吴恩华. 基于凸剖分的点在多边形内的高效判定[J]. 自然科学进展,2007,17(7):995-1000.
|
| APA |
李静,王文成,&吴恩华.(2007).基于凸剖分的点在多边形内的高效判定.自然科学进展,17(7),995-1000.
|
| MLA |
李静,et al."基于凸剖分的点在多边形内的高效判定".自然科学进展 17.7(2007):995-1000.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论