摘要
在分析向量代数的几何意义的基础上,提出了利用向量叉积的几何性质来判断点与多边形的拓扑关系,通过判断点生成一个水平向量,通过该向量和多边形各边的向量叉乘运算,利用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.
出处
《大地测量与地球动力学》
CSCD
北大核心
2011年第2期89-93,共5页
Journal of Geodesy and Geodynamics
基金
国家自然科学基金(40971234
40761017
40730527)
国家863计划课题(2007AA12Z207)
关键词
拓扑关系
向量代数
叉积
点
多边形
topological relationship
vector algebra
cross product
point
polygon
