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.
WEI Yansheng
,
ZHANG Shuqing
,
LI Huapeng
,
DING Xiaohui
,
LIU Zhao
. High efficient 2D/3D point inclusion test approach based on point circle theory[J]. Journal of University of Chinese Academy of Sciences, 2018
, 35(3)
: 353
-361
.
DOI: 10.7523/j.issn.2095-6134.2018.03.010
[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.
