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

摘要

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.%在分析向量代数的几何意义的基础上,提出了利用向量叉积的几何性质来判断点与多边形的拓扑关系,通过判断点生成一个水平向量,通过该向量和多边形各边的向量叉乘运算,利用k分量的符号来判断两向量的位置关系,并对各种位置关系赋予相应的权重值,最后根据权重值之和的奇偶性来判断点与多边形的位置关系.该算法无需计算出实际的交点,同时,还对某些特殊位置关系作了几何等价处理.从程序运行效果来看,该算法具有稳定性高、运行速度快等优点.