Institutional Repository
| 基于凸剖分的点在多边形内的高效判定 | |
| 李静; 王文成; 吴恩华 | |
| 2007 | |
| Source | 自然科学进展
 |
| ISSN | 1002-008X |
| Volume | 17Issue:7Pages:995-1000 |
| English Abstract | 提出一种点在多边形内的快速判定算法.与这方面已知的最快算法相比,新方法在预处理时间、空间需求和判定计算等方面,均达到了相同的复杂度,且没有奇异情况,能运算更快,甚至快一倍多.其步骤是:将一个多边形剖分成一些凸多边形,并进行二叉树的组织管理;然后,判断一个点是否在该多边形内时,先根据二叉树找到最可能包含该点的凸多边形,再判断该点是否位于该凸多边形内,就可完成判定计算. |
| Keyword | 点 多边形 包容性检测 加速 凸剖分 凸多边形 判定算法 二叉树 多边形剖分 组织管理 奇异情况 空间需求 计算 预处理 新方法 复杂度 运算 |
| Department | 中国科学院软件研究所计算机科学国家重点实验室,北京100080;中国科学院研究生院,北京100039;中国科学院软件研究所计算机科学国家重点实验室,北京100080;中国科学院软件研究所计算机科学国家重点实验室,北京100080;澳门大学科技学院计算机与信息科学系,澳门 |
| Language | 中文 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/11286 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | 李静,王文成,吴恩华. 基于凸剖分的点在多边形内的高效判定[J]. 自然科学进展,2007,17(7):995-1000. |
| APA | 李静,王文成,&吴恩华.(2007).基于凸剖分的点在多边形内的高效判定.自然科学进展,17(7),995-1000. |
| MLA | 李静,et al."基于凸剖分的点在多边形内的高效判定".自然科学进展 17.7(2007):995-1000. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 基于凸剖分的点在多边形内的高效判定.pd（446KB） | 开放获取 | -- | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment