-
题名点与简单多边形关系的新算法
被引量：11
- 1
-
-
作者
胡景松
张丽芬
王晓华
宋维佳
龙斌
-
机构
北京理工大学计算机系
-
出处
《计算机工程》
CAS
CSCD
北大核心
2004年第20期86-88,共3页
-
文摘
提出一种检测点与多边形关系的新算法,通过扫描建立适合查找的多边形层次结构。检测时,运用二分查找,找到与检测点相关的边,通过该点与相关边的关系判断出点与多边形的关系。实验结果表明,该方法简单有效,有较高的检测速度。
-
关键词
点
简单多边形
包含检测
-
Keywords
Point
simple polygon
inclusion test
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
-
题名有向回路法和网格法:多边形内外点判别的新算法
被引量：8
- 2
-
-
作者
郭雷
王洵
王晓蒲
-
机构
中国科学技术大学天文与应用物理系
中国科学技术大学计算机科学与技术系
-
出处
《计算机工程与应用》
CSCD
北大核心
2002年第19期119-122,共4页
-
文摘
该文把简单多边形视作一个有向回路,利用多边形的环绕方向和区域划分提出了两种判别内外点的新算法:有向回路法和网格法。有向回路法利用了多边形的方向性,在某些情况下可以不必遍历多边形的所有边。该算法程序简单,时间复杂度为O(n),平均性能优于复杂度为Θ(n)的射线法和标号法,但只能处理凸多边形。网格法是有向回路法的改进算法,利用了多边形的方向性和区域划分。网格法将n边形的包围盒划分为(n-1)×(n-1)个网格:如果待处理的点在某个网格内,则仅根据经过该网格的所有边就可以判断该点的内外性。网格法可以处理任意简单多边形,包括带孔的多边形;最坏情况下的时间复杂度为O(lgn),空间复杂度为Θ(n2)。
-
关键词
有向回路法
网格法
计算机图形学
多边形内外点判别算法
-
Keywords
computer graphics,simple polygon,inclusion test
-
分类号
TP391.41
[自动化与计算机技术—计算机应用技术]
-
-
题名一种判定点和多边形包含关系的有效方法
被引量：14
- 3
-
-
作者
王晨
池建斌
冯桂珍
-
机构
石家庄铁道学院机械工程分院
-
出处
《计算机应用与软件》
CSCD
北大核心
2005年第4期110-112,共3页
-
文摘
在分析现有点与多边形包含关系的判定方法的基础上,提出了将判断点绕多边形的一个适当顶点为中心逆时针旋转,根据判断点依次旋转到该顶点前后两边时两个旋转角的大小关系来判定点的位置的思想,并以此为基础提出了一种判定点与多边形的包含关系的有效方法。
-
关键词
包含关系
有效方法
多边形
定点
判定方法
大小关系
旋转角
基础
顶点
断点
-
Keywords
computer graphics Relationship between point and polygon Algorithm inclusion test
-
分类号
TP391.41
[自动化与计算机技术—计算机应用技术]
O174.52
[理学—基础数学]
-
-
题名快速判断点是否在自交多边形内的方法
被引量：8
- 4
-
-
作者
吴坚
姜虹
王小椿
-
机构
西安交通大学机械工程学院数控研究所
-
出处
《系统仿真学报》
CAS
CSCD
2003年第11期1592-1594,共3页
-
文摘
提出一种新方法,检测一个点是否在多边形和环内。此方法从检测点发出一条射线,根据边与射线的位置关系,定义了边相对于射线的位置函数,然后计算出所有边的位置函数之和,据此判断检测点是否在多边形和环内。该方法不仅能够检测简单多边形,还可用于检测自交多边形,并能同时检测多个多边形。实验结果表明,该方法简单,可靠,检测速度快。
-
关键词
多边形
简单多边形
自交多边形
包含检测
-
Keywords
polygon
simple polygon
self-intersected polygon
inclusion test
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名基于斜率的多边形内外点快速判别算法
- 5
-
-
作者
洪志强
-
机构
江苏科技大学计算机科学与工程学院
-
出处
《计算机与现代化》
2013年第1期53-56,60,共5页
-
文摘
多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法。该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别。该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别。经测试,该算法快速有效。
-
关键词
计算机图形
斜率
简单多边形
内外点判别
-
Keywords
computer graphics
slope
simple polygon
point in polygon test
-
分类号
TP301.6
[自动化与计算机技术—计算机系统结构]
-
