一种判断点与多边形关系的快速算法

陈瑞卿; 周健; 虞烈

您当前的位置：

首页 >

文章列表页 >

一种判断点与多边形关系的快速算法

专题研究 | 更新时间：2025-12-08

- 一种判断点与多边形关系的快速算法
- Fast Method to Determine Spatial Relationship between Point and Polygon
- 西安交通大学学报 2007年41卷第1期页码：59-63
- 作者机构：
  
  西安交通大学机械电子及信息系统研究所,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  中图分类号： TP391
- 网络首发：2007-01-10，
  
  纸质出版：2007
- 稿件说明：
移动端阅览
陈瑞卿, 周健, 虞烈. 一种判断点与多边形关系的快速算法[J]. 西安交通大学学报, 2007,41(1):59-63.

陈瑞卿, 周健, 虞烈. Fast Method to Determine Spatial Relationship between Point and Polygon[J]. 2007, 41(1): 59-63.
陈瑞卿, 周健, 虞烈. 一种判断点与多边形关系的快速算法[J]. 西安交通大学学报, 2007,41(1):59-63. DOI：

陈瑞卿, 周健, 虞烈. Fast Method to Determine Spatial Relationship between Point and Polygon[J]. 2007, 41(1): 59-63. DOI：

摘要

采用对多边形各边赋权值的方法

分析射线与多边形相交的不同情况

给出了使用结构化查询语言实现交点个数求解的快速解决方案.结合数据库管理系统提供的优化查询机制

通过执行一次查询求得射线与多边形的交点个数

从而快速地判断出点与多边形的位置关系.与其他改进方法相比

该方法易于理解

计算简单

对于具有多顶点的复杂多边形

其优越性显得更为突出.

Abstract

To analyze the different locations of the intersection of a ray and a polygon quickly

a scheme of calculating the number for the intersection point is established based on the structure query language(SQL)and the method of weighting each side of the polygon. Combined with the optimized query mechanism of database management system

the amount of the intersections can be calculated by running the SQL once

and the spatial relationship between the point and polygon is confirmed rapidly. It is verified that the method is simpler and more understandable than the competing methods

especially for the complicated multi-vertex polygons.

关键词

Keywords

references

Feito F R, Torres J C, Urena L A. Orientation simplicity and inclusion test for planar polygons[J].Computer & Graphics, 1995, 19(4):595-600.

王文成, 吴恩华. 判断检测点是否在多边形或多面体内的新方法[J]. 软件学报, 2000, 11(12):1614-1619.

Wang Wencheng, Wu Enhua. A new method deciding whether a point is in a polygon or a polyhedron[J]. Journal of Software, 2000, 11(12):1614-1619.

胡景松, 张丽芬,王晓华,等. 点与简单多边形关系的新算法[J]. 计算机工程, 2004, 30(20):86-88.

Hu Jingsong,Zhang Lifen,Wang Xiaohua,et al. New algorithm for simple polygon and point[J]. Computer Engineering, 2004, 30(20):86-88.

李维诗, 李江雄, 柯映林. 平面多边形方向及内外点判断的新方法[J]. 计算机辅助设计与图形学学报, 2000, 12(6):405-407.

Li Weishi, Li Jiangxiong, Ke Yinglin. Orientation and point inclusion test for planar polygon [J]. Journal of Computer-Aided Design Computer Graphics, 2000, 12(6):405-407.

吴坚, 姜虹, 王小椿. 快速判断点是否在自交多边形内的方法[J]. 系统仿真学报, 2003, 15(11):1592- 1594.

Wu Jian, Jiang Hong, Wang Xiaochun. A method for the decision of a point whether in or not in self-intersected polygon[J]. Journal of System Simulation, 2003, 15(11):1592-1594.

张宁宁, 张树有, 谭建荣. 映射相关边概念的多边形内外点判别算法[J]. 计算机辅助设计与图形学学报,2004, 16(7):935-938.

Zhang Ningning, Zhang Shuyou, Tan Jianrong. Point inclusion test for simple polygons by the nearest relevant edge [J]. Journal of Computer-Aided Design Computer Graphics, 2004, 16(7): 935-938.

王晨, 池建斌,冯桂珍. 一种判定点和多边形包含关系的有效方法[J]. 计算机应用与软件, 2005, 22(4): 110-112.

Wang Chen, Chi Jianbin, Feng Guizhen. A method of judging the relationship between point and polygon[J]. Computer Applications and Software, 2005, 22(4):110-112.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

张角凹坑气膜孔对双层壁气膜冷却特性的影响

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究

面向高海拔空冷发电机防晕性能演化规律的电热耦合研究

隧道内燃料电池汽车氢气泄漏扩散特性及影响因素