点在多边形内测试的新算法

被引：14

作者：

刘润涛 ^{[1
]}

刘玉珍 ^{[2
]}

机构：

[1] 哈尔滨理工大学信息与科学计算技术研究所

[2] 哈尔滨理工大学应用科学学院

来源：

工程图学学报 | 2008年 / 02期

关键词：

计算机应用; 射线交叉法; 简单多边形; 内外点判别;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

摘要：

判断点在多边形内是诸多领域的一个基本问题。分析了解决这一问题的一些传统算法,改进了射线交叉法。避免了射线与多边形的一条边重合、射线经过多边形顶点这两种临界情况的处理和求交点运算。算法的时间复杂度为4n次减法,3n次乘法,6n次比较(n为多边形顶点数)。程序简单易行,计算量较小。

引用

页码：89 / 93

页数：5

共 7 条

[1]

再论映射相关边概念的多边形内外点判别算法 [J].

赵京东 .

计算机辅助设计与图形学学报, 2007, (01) :69-72

[2]

判定检测点是否在多边形内的新方法 [J].

陈树强 ;

陈学工 ;

王丽青 .

微电子学与计算机, 2006, (08) :194-195+199

[3]

有向回路法和网格法:多边形内外点判别的新算法 [J].

郭雷 ;

王洵 ;

王晓蒲 .

计算机工程与应用, 2002, (19) :119-122

[4]

平面多边形方向及内外点判断的新方法 [J].

李维诗 ;

李江雄 ;

柯映林 .

计算机辅助设计与图形学学报, 2000, (06) :405-407

[5]

点在多边形内的测试 [J].

张保钢 ;

朱凌 .

测绘通报, 1996, (01)

[6]

计算机图形学.[M].孙家广;杨长贵编著.清华大学出版社.1995,

[7]

ORIENTATION, SIMPLICITY, AND INCLUSION TEST FOR PLANAR POLYGONS [J].

FEITO, F ;

TORRES, JC ;

URENA, A .

COMPUTERS & GRAPHICS, 1995, 19 (04) :595-600

← 1 →