基于向量代数的点与多边形拓扑关系的推理  

DETERMINATION OF TOPOLOGICAL RELATIONSHIP BETWEEN POINT AND POLYGON BASED ON VECTOR ALGEBRA

作　　者：刘德儿[1,2] 王永君[1] 闾国年[1] 

机构地区：[1]南京师范大学地理信息科学江苏省重点实验室,南京210046 [2]江西理工大学建筑与测绘工程学院,赣州341000

出　　处：《大地测量与地球动力学》2011年第2期89-93,共5页Journal of Geodesy and Geodynamics

基　　金：国家自然科学基金(40971234;40761017;40730527);国家863计划课题(2007AA12Z207)

摘　　要：在分析向量代数的几何意义的基础上,提出了利用向量叉积的几何性质来判断点与多边形的拓扑关系,通过判断点生成一个水平向量,通过该向量和多边形各边的向量叉乘运算,利用k分量的符号来判断两向量的位置关系,并对各种位置关系赋予相应的权重值,最后根据权重值之和的奇偶性来判断点与多边形的位置关系。该算法无需计算出实际的交点,同时,还对某些特殊位置关系作了几何等价处理。从程序运行效果来看,该算法具有稳定性高、运行速度快等优点。Through the analysis of the geometric sense of vector algebra,vector cross-product is used to determine the topological relationship between point and polygon.A horizontal vector is made based on the determination of point and then the cross multiplication between it and each vector of the polygon is made.Futhermore,the signal of k-component is employed to determine the spatial relationship between point and polygon.An appropriate weight value is given to a bare possibility.The parity of the weight sum is to decide the spatial relationship between point and polygon.The intersectant point is avoided to be computed,and some special cases are resolved with geometric equivalence.Software implementation verifies the high robustness and efficiency of this algorithm.

关 键 词：拓扑关系 向量代数 叉积 点 多边形 

分 类 号：P208[天文地球—地图制图学与地理信息工程]