基于点圆理论的2D/3D点包含高效判定  

High efficient 2D/3D point inclusion test approach based on point circle theory

作　　者：魏延生 张树清[1] 李华朋[1] 丁小辉[1,2] 刘照 WEI Yansheng;ZHANG Shuqing;LI Huapeng;DING Xiaohui;LIU Zhao(Northeast Institute of Geography and Agroecology, Chinese Academy of Sciences, Changchun 130102, China;University of Chinese Academy of Sciences, Beijing 100049, China;Harbin Institute of Geotechnical Investigation and Surverying, Harbin 150010. China)

机构地区：[1]中国科学院东北地理与农业生态研究所,长春130102 [2]中国科学院大学,北京100049 [3]哈尔滨市勘察测绘研究院,哈尔滨150010

出　　处：《中国科学院大学学报（中英文）》2018年第3期353-361,共9页Journal of University of Chinese Academy of Sciences

基　　金：国家自然科学基金(41671397)资助

摘　　要：针对2D/3D点包含判定方法的复杂和低效问题,提出基于点圆理论的方法:分类描述奇异情形在点圆中的投影、叠加特征及判定方法,将3D点包含测试转换为与2D点包含测试一致的算法(除子平面方程系数计算外)。筛选和累加与射线相交的射线以上或以下的线段,据此奇偶性判定3D或2D点包含;解析2D射线与多边形相交连续线段内节点的几何特征,即y坐标要么都大于、要么都小于测试点,构建高效2D点包含增量筛选射线法。实验结果表明所建2D/3D点包含方法高效、稳定,可用于处理任意奇异性,适合于任意多面体(流形、非流形、表面为平面或曲面等)或多边形。According to the problem that 2D/3D point inclusion test approach is complex and lowefficient,we propose a new method based on point circle theory. Projections of different types of singular points and their overlay properties on point circle are geometrically analyzed,and their determinations are proposed. 3D point inclusion test is transformed to 2D point inclusion test,except for the calculation of the plane equation coefficients. Based on the filter and accumulation of edges intersecting with and lying above or below the ray shooting from the test point,the point inclusion can be determined according to the odd/even property of the edges. Common geometric characteristics of the consecutive edges of a polygon lying above or below the 2D ray are recognized,i. e.,their y-coordinate values either collectively larger or smaller than that of the test point. A high efficient 2D point inclusion algorithm named increment filter crossing number（IFCN） method is thus established. The experiment results show that the proposed 2D/3D point inclusion algorithms are highly reliable and efficient.They are capable of treating any singularities and suitable for any polyhedrons（manifold,non-manifold,planar-faced or curved-faced surface,etc.）or any polygons.

关 键 词：射线法 点包含 点圆投影 增量筛选法 径向分界点 

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