基于线性方程的凸多边形内外点判别算法研究  

Test Method of Point Inclusion Based on Linear Equation

作　　者：廖雪花[1] 包秋兰 张秀娟 刘美 LIAO Xuehua;BAO Qiulan;ZHANG Xiujuan;LIU Mei(School of Computer Science,Sichuan Normal University,Chengdu 610101,Sichuan;School of Physics and Electronic Engineering,Sichuan Normal University,Chengdu 610101,Sichuan)

机构地区：[1]四川师范大学计算机科学学院,四川成都610101 [2]四川师范大学物理与电子工程学院,四川成都610101

出　　处：《四川师范大学学报（自然科学版）》2023年第4期560-568,共9页Journal of Sichuan Normal University（Natural Science）

基　　金：国家社会科学基金一般项目(20BMZ092)。

摘　　要：多边形内外点判断算法是多个领域相关研究的基础,主要用于检测某点位于给定多边形内部或外部.针对传统射线法的奇异性问题以及角度和法、面积和法误差大、精度要求高等缺点,提出一种基于线性方程的多边形内外点判别新算法.该算法借助求解线性方程的思想,将点与多边形的位置关系判别问题转换为点与直线的位置关系判别问题.经过实验仿真,证明该算法能够正确判别点与凸多边形的位置关系,且能正确处理高精度的地理坐标数据.Point inclusion test is a basic algorithm of related research in many fields.It is mainly used to detect whether a point is inside or outside a given polygon.Aiming at the singularity of traditional ray method,requirements for the large error and high precision of methods base on the angle sum and area sum,this paper proposes a new algorithm for point inclusion test based on the linear equa-tion.With the help of the idea of solving linear equations,the algorithm transforms the problem of determing the position relationship between point and polygon into the problem of determine the position relationship between point and line.The experimental results show that the algorithm can correctly distinguish the position relationship between point and convex polygon,and can correctly process geo-graphic coordinate data with high-precision.

关 键 词：凸多边形 线性方程 高精度 点包含测试 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]