点与多边形或多面体的拓扑关系判断  

Judgment of topological relation between point and polygon or polyhedron

作　　者：翟艳[1] 徐卫亚[1] 张强[1] 

机构地区：[1]河海大学岩土力学与堤坝工程教育部重点实验室,江苏南京210098

出　　处：《计算机工程与设计》2015年第4期972-976,共5页Computer Engineering and Design

基　　金：国家973重点基础研究发展计划基金项目(2011CB013504);"十二五"国家科技支撑计划基金项目(2012BAK03B04)

摘　　要：为快速有效判断出点与多边形和多面体的拓扑关系,针对传统射线法不能准确判断点与复杂多边形拓扑关系的缺点,提出通过引入虚交点的概念对传统射线法进行改进的方法,实现点与复杂多边形拓扑关系的快速判断。利用实例对该算法的正确性进行验算,验算结果正确。对于点与多面体拓扑关系的判断,运用切割剖面法将点与复杂多面体的拓扑关系判断转化为点与复杂多边形的判断。实例验算结果表明,该算法快速有效,易于编程实现。To judge the relationship between a point and a complicated polygon correctly and rapidly while the traditional ray method fals to give a correct result,a concept of virtual inter point to modify the traditional method of radial was introduced and some typical examples to prove the correction of the method were clemonstrated.As to the relationship of a point and a complicated polyhedron,a section method was used to transfer the judgment of the relationship between a point and a complicated polyhedron to that of the relationship between a point and a complicated polygon.The verification of examples shows that the modified algorithm is fast and efficient.It can also be realized by programming easily.

关 键 词：拓扑关系 射线法 多边形 多面体 虚交点 

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