基于网格的多点在多边形内高效判定方法

作     者：谢少菲 高铁军 魏恋欢 XIE Shao-fei;GAO Tie-jun;WEI Lian-huan

作者机构：东北大学资源与土木工程学院辽宁沈阳110819 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2024年第45卷第1期

页      面：139-145页

学科分类：081203[工学-计算机应用技术] 08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(42071453) 中央高校基本科研业务费国家项目培育基金项目(N2001027) 

主　　题：网格 点 多边形 点在多边形 数值微分法 边界代数法 网格分块 

摘      要：提出一种基于网格的点(多点)在多边形内高效判定方法。预处理阶段使用数值微分法(DDA)结合边界代数法,快速识别边界网格并分割出多边形边片段,同时标记网格左下角点位置属性;当待判定点位于非边界网格内时,根据预处理结果直接判定;位于边界网格时,对边界网格分块后再判定。实验结果表明,该预处理方法高效快速且边界网格分块法有效缩减了判定时间。此方法适用于凹凸多边形、自相交多边形以及环状多边形,相较现有算法优势明显,100万个点在28012条边的多边形中判定用时约0.04 s。