针对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 low-efficient, 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.
[1] Wang W, Li J, Sun H, et al. Layer-Based Representation of Polyhedrons for Point Containment Tests[J]. IEEE Trans Vis Comput Graph, 2008, 14(1):73-83.
[2] Arens C, Stoter J E, Oosterom P V. Modelling 3D spatial objects in a geo-DBMS using a 3D primitive[C]//IEEE International Conference on Computational Intelligence in Robotics and Automation. IEEE Press, 2009:441-444.
[3] Penninga F, Oosterom P V. A simplicial complex-based DBMS approach to 3D topographic data modelling[J]. International Journal of Geographical Information Science, 2008, 22(7):751-779.
[4] Gomboš I M, ?alik B. Point-in-polygon tests for geometric buffers ☆[J]. Computers & Geosciences, 2005, 31(10):1201-1212.
[5] Chazelle B, Dobkin D P. Detection is easier than computation (Extended Abstract)[C]//12th ACM Symposium on Theory of Computing. ACM, 1980:146-153.
[6] Dietzfelbinger M, Karlin A, Mehlhorn K, et al. Dynamic perfect hashing:upper and lower bounds[C]//Foundations of Computer Science, 1988. Symposium on. IEEE, 1994:524-531.
[7] Bajaj C L, Dey T K. Convex Decomposition of Polyhedra and Robustness[J]. Siam Journal on Computing, 2006, 21(2):339-364.
[8] Cui S, Fu X. Point in polyhedra test with direct handling of degeneracies[C]//The Joint Isprs Workshop on 3D City Modelling & Applications,the 6th 3D Geoinfo Conference, 2011:91-97.
[9] Lane J, Magedson B, Rarick M. An efficient point in polyhedron algorithm[J]. Computer Vision Graphics & Image Processing, 1984, 26(1):118-125.
[10] Feito F R, Torres J C. Inclusion test for general polyhedra[J]. Computers & Graphics, 1997, 21(1):23-30.
[11] Ogayar C J, Segura R J, Feito F R. Point in solid strategies[J]. Computers & Graphics, 2005, 29(4):616-624.
[12] Kalay Y E. Determining the spatial containment of a point in general polyhedra[J]. Computer Graphics & Image Processing, 1982, 19(4):303-334.
[13] Zhang S, Zhang J. Theoretical analytics of stereographic projection on 3D objects' intersection predicate[J]. International Journal of Geographical Information Science, 2010, 24(1):25-46.
[14] 李新友. 一种实用的点/多面体分类算法[J]. 计算机辅助设计与图形学学报,1991,3(3):25-28,24.
[15] Khamayseh A, Kuprat A. Deterministic point inclusion methods for computational applications with complex geometry[J]. Computational Science & Discovery, 2008, 1(1):015004.
[16] Kai H, Agathos A. The point in polygon problem for arbitrary polygons[J]. Computational Geometry, 2001, 20(3):131-144.
[17] 王文成, 吴恩华. 判断检测点是否在多边形或多面体内的新方法[J]. 软件学报, 2000, 11(12):1614-1619.
[18] 李维诗, 李江雄. 平面多边形方向及内外点判断的新方法[J]. 计算机辅助设计与图形学学报, 2000, 12(6):405-407.
[19] 王志强, 肖立瑾, 洪嘉振,等. 多边形的简单性、方向及内外点的判别算法[J]. 计算机学报, 1998, 21(2):183-187.
