基于网格的多点在多边形内高效判定方法
Efficient determination of multiple points inside a polygon based on grid
谢少菲 1高铁军 1魏恋欢1
作者信息
- 1. 东北大学 资源与土木工程学院,辽宁 沈阳 110819
- 折叠
摘要
提出一种基于网格的点(多点)在多边形内高效判定方法.预处理阶段使用数值微分法(DDA)结合边界代数法,快速识别边界网格并分割出多边形边片段,同时标记网格左下角点位置属性;当待判定点位于非边界网格内时,根据预处理结果直接判定;位于边界网格时,对边界网格分块后再判定.实验结果表明,该预处理方法高效快速且边界网格分块法有效缩减了判定时间.此方法适用于凹凸多边形、自相交多边形以及环状多边形,相较现有算法优势明显,100万个点在28 012条边的多边形中判定用时约0.04 s.
Abstract
A grid-based method suitable for large sets of points was proposed to determine whether or not points lied inside or outside of a polygon.The pretreatment used digital differential analyzer(DDA)algorithm to identify the boundary mesh and split the polygon edge into segments.The boundary algebra method was applied to identify the inner or outer position attribute of grid lower-left corners which was related to the polygon.When a point was located in a non-boundary grid,the inner or outer position attribute of the point was given directly according to the lower-left corner position attribute of the grid.If a point was located in a boundary grid,the boundary grid was divided into blocks to support directly determining the inner or outer position attribute of pending points.Experimental results show that the proposed method effectively reduces the computing time and it is applicable for concave-convex polygons,self-intersecting polygons and ring polygons.The proposed algorithm outperforms the existing algorithms.It took about 0.04 s to determine the position attribute of 1 million points when the polygon is composed of 28 012 edges.
关键词
网格/点/多边形/点在多边形/数值微分法/边界代数法/网格分块Key words
grid/point/polygon/point in polygon/DDA/boundary algebraic method/grid partition引用本文复制引用
基金项目
国家自然科学基金项目(42071453)
中央高校基本科研业务费国家项目培育基金项目(N2001027)
出版年
2024
NETL
NSTL
万方数据